(57)【特許請求の範囲】
【請求項１】
複数のクライアントと、資源を提供するコンピューティングデバイスのレプリカである複数の論理的レプリカとを備えたシステムであって、それぞれの前記論理的レプリカは、前記複数のクライアントのうちの１つのクライアントと、他のクライアントに該論理レプリカの資源へのアクセス許可を与えることができないことを示す排他的関連づけがされるように構成され、それぞれの前記論理的レプリカは、クライアントから受信した資源へのアクセスを求める要求を格納するキューを含む、システムにおいて、
それぞれの前記論理的レプリカが、第１のクライアントから、該論理的レプリカに対応するコンピューティングシステムが提供する資源へのアクセスを求める要求を受信するステップと、
それぞれの前記論理的レプリカが、該論理的レプリカに排他的に関連づけられているクライアントを示す値を含む、前記要求に対する応答を前記複数のクライアントに送信するステップと、
前記要求を受信した論理的レプリカが第２のクライアントと排他的に関連づけられている場合に、該論理的レプリカが、該論理的レプリカのキューに前記要求を格納するステップと、
移譲（Yield）メッセージを受信した論理的レプリカが、該論理的レプリカとの排他的関連付けを解放させるための移譲メッセージに応答して、該論理的レプリカのキューに格納されたこれまでの要求に基づいて、別の応答を送信するステップであって、前記移譲メッセージは、それぞれの前記クライアントが、前記複数の論理的レプリカから前記要求に対する複数の応答を受信し、前記複数の応答から、前記複数のクライアントクライアントのうちの１つに資源へのアクセスが許可されるどうかを判定することによって前記複数のクライアントのいずれも許可されないと判定される場合に、排他的に関連づけられているクライアントとして自身を示す値を含む応答を受信したクライアントによって、該応答を送信した論理的レプリカに送信される、ステップ
を含むことを特徴とする方法。
【請求項２】
前記第１のクライアントは、前記第１のクライアントが前記複数の論理的レプリカのうちの所定数の論理的レプリカと排他的に関連づけられる場合に許可されることを特徴とする請求項１に記載の方法。
【請求項３】
前記第１のクライアントが許可されない場合に、前記第１のクライアントは、資源へのアクセスを求める要求を再送しないことを特徴とする請求項１に記載の方法。
【請求項４】
前記複数の資源が、分散ハッシュテーブル（ＤＨＴ）を用いて分割され、
前記ＤＨＴが、前記複数の資源のそれぞれを複数のバケットのそれぞれのバケットに分割し、
前記複数のバケットが、ピアツーピアネットワーク内の複数のコンピューティングデバイスによって提供される
ことを特徴とする請求項１に記載の方法。
【請求項５】
それぞれの前記バケットを提供する１つの前記コンピューティングデバイスが前記クライアントにとって利用可能でない場合、該バケットが別の前記コンピューティングデバイスによって利用可能にされるように、前記複数のコンピューティングデバイスがフェイルオーバ（障害迂回）機能を備えたことを特徴とする請求項４に記載の方法。
【請求項６】
コンピュータ実行可能命令を含む１つまたは複数のコンピュータ可読記録媒体において、コンピュータ上で実行される時に、該コンピュータに、請求項１に記載の方法を実行させることを特徴とするコンピュータ可読記録媒体。
【請求項７】
複数のクライアントと、資源を提供するコンピューティングデバイスのレプリカである複数の論理的レプリカとを備えたシステムであって、それぞれの前記論理的レプリカは、前記複数のクライアントのうちの１つのクライアントと、他のクライアントに該論理レプリカの資源へのアクセス許可を与えることができないことを示す排他的関連づけがされるように構成され、前記論理的レプリカが別のクライアントと排他的に関連づけられる場合に、該論理的レプリカに対応するコンピューティングデバイスが提供する資源へのアクセスを求めるクライアントからの要求を格納するためのキューを含む、システムにおいて、
第１のクライアントが、複数の論理的レプリカに、特定の論理的レプリカに対応するコンピューティングデバイスが提供する資源へのアクセスを求める要求を送信するステップと、
前記第１のクライアントが、前記複数の論理的レプリカから前記要求に対する複数の応答を受信するステップであって、それぞれの前記応答は、該応答を送信した論理的レプリカに排他的に関連づけられているクライアントを示す値を含む、ステップと、
前記第１のクライアントが、前記複数の応答から、前記第１のクライアントによる前記特定の論理的レプリカに対応するコンピューティングデバイスが提供する資源へのアクセスが許可されるかどうかを判定するステップと
を含み、前記第１のクライアントが許可されない場合に、前記第１のクライアントは、資源へのアクセスを求める要求を再送しないことを特徴とする方法。
【請求項８】
前記複数のクライアントのいずれも許可されない場合、排他的に関連づけられているクライアントとして自身を示す値を含む応答を受信したクライアントが、該応答を送信した論理的レプリカに、該論理的レプリカとの排他的関連付けを解放させるための移譲メッセージを送信し、
前記移譲メッセージを受信した論理的レプリカが、該論理的レプリカのキューに格納されたこれまでの要求に基づいて別の応答を送信することを特徴とする請求項７に記載の方法。
【請求項９】
前記第１のクライアントは、前記第１のクライアントが前記複数の論理的レプリカのうちの所定数の論理的レプリカと排他的に関連づけられる場合に許可されることを特徴とする請求項７に記載の方法。
【請求項１０】
ＤＨＴが、前記複数の資源を複数のバケットに分割し、
前記複数のバケットが、ピアツーピアネットワーク内の複数のコンピューティングデバイスによって提供され、
それぞれの前記バケットを提供する１つの前記コンピューティングデバイスが前記複数のクライアントにとって利用可能でない場合、該バケットが別の前記コンピューティングデバイスによって利用可能にされるように、前記複数のコンピューティングデバイスがフェイルオーバ機能を提供する
ことを特徴とする請求項７に記載の方法。
【請求項１１】
前記キュー内のそれぞれの前記要求は、該要求がそれぞれの前記論理的レプリカによっていつ受信されたかに従って編成されることを特徴とする請求項７に記載の方法。
【請求項１２】
コンピュータ実行可能命令を含む１つまたは複数のコンピュータ可読記録媒体において、コンピュータ上で実行される時に、該コンピュータに、請求項７に記載の方法を実行させることを特徴とするコンピュータ可読記録媒体。
【請求項１３】
複数のクライアントと、資源を提供するコンピューティングデバイスのレプリカである複数の論理的レプリカとを備えたシステムであって、それぞれの前記論理的レプリカは、前記複数のクライアントのうちの１つのクライアントと、他のクライアントに該論理レプリカの資源へのアクセス許可を与えることができないことを示す排他的関連づけがされるように構成され、それぞれの前記論理的レプリカは、クライアントから受信した資源へのアクセスを求める要求を格納するキューを含む、システムにおいて、
複数のクライアントのそれぞれが、複数の論理的レプリカに、特定の論理的レプリカに対応するコンピューティングデバイスが提供する資源へのアクセスを求める要求を送信するステップと、
前記複数のクライアントが、前記複数の論理的レプリカから前記要求に対する複数の応答を受信するステップであって、それぞれの前記応答は、該応答を送信した論理的レプリカに排他的に関連づけられているクライアントを示す値を含む、ステップと、
それぞれの前記クライアントが、前記複数の応答を用いて、前記複数のクライアントのうちの１つに資源へのアクセスが許可されるかどうかを判定するステップと、
前記複数のクライアントのいずれも前記１つの資源へのアクセスが許可されない場合、排他的に関連づけられているクライアントとして自身を示す値を含む応答を受信したクライアントが、該応答を送信した１つまたは複数の論理的レプリカに、該論理的レプリカとの排他的関連付けを解放させるための移譲メッセージを送信するステップと
を含み、前記移譲メッセージを受信した論理的レプリカが、該論理的レプリカのキューに格納されたこれまでの要求に基づいて別の応答を送信することを特徴とする方法。
【請求項１４】
前記キュー内のそれぞれの前記前の要求は、該前の要求がそれぞれの前記論理的レプリカによっていつ受信されたかに従って編成され、
前記移譲メッセージが、前記１つまたは複数の論理的レプリカに、それぞれの前記キュー内の最先の要求に基づいて前記別の応答を送信させる
ことを特徴とする請求項１３に記載の方法。
【請求項１５】
前記移譲メッセージは、前記１つまたは複数の論理的レプリカに、前記それぞれのキューに基づいて、前記移譲メッセージを送信したクライアントとは異なるクライアントを、排他的に関連づけられているクライアントとして選択させることを特徴とする請求項１３に記載の方法。
【請求項１６】
前記資源へのアクセスは、前記複数の論理的レプリカのうちの所定数の論理的レプリカと排他的に関連づけられる前記複数のクライアントのうちの１つに許可されることを特徴とする請求項１３に記載の方法。
【請求項１７】
前記資源へのアクセスが許可されない１つまたは複数の他の前記クライアントは、資源へのアクセスを求める要求を再送しないことを特徴とする請求項１３に記載の方法。
【請求項１８】
前記複数の資源が、分散ハッシュテーブル（ＤＨＴ）を用いて分割され、
前記ＤＨＴが、前記複数の資源を複数のバケットに分割し、
前記複数のバケットが、ピアツーピアネットワーク内の複数のコンピューティングデバイスによって提供され、
それぞれの前記バケットを提供する１つの前記コンピューティングデバイスが前記複数のクライアントにとって利用可能でない場合、該バケットが別の前記コンピューティングデバイスによって利用可能にされるように、前記複数のコンピューティングデバイスがフェイルオーバ機能を備えた
ことを特徴とする請求項１３に記載の方法。
【請求項１９】
コンピュータ実行可能命令を含む１つまたは複数のコンピュータ可読記録媒体において、コンピュータ上で実行される時に、該コンピュータに、請求項１３に記載の方法を実行させることを特徴とするコンピュータ可読記録媒体。
【請求項２０】
ネットワークと、
前記ネットワークに通信可能に結合した複数のクライアントと、
前記ネットワークに通信可能に結合し、資源を提供するコンピューティングデバイスのレプリカである複数の論理的レプリカを含む複数のコンピューティングデバイスと
を備えたシステムにおいて、それぞれの前記論理的レプリカが、
前記複数のクライアントのうちの１つのクライアントと、他のクライアントに該論理レプリカの資源へのアクセス許可を与えることができないことを示す排他的関連づけがされるように構成され、
前記論理的レプリカが別のクライアントと排他的に関連づけられる場合に、該論理的レプリカに対応するコンピューティングデバイスが提供する資源へのアクセスを求めるクライアントからの要求を格納するためのキューを含み、
該論理的レプリカに排他的に関連づけられているクライアントを示す値を含む、前記要求に対する応答を送信するように構成され、
それぞれの前記クライアントは、
複数の論理的レプリカに、該論理的レプリカの資源へのアクセスを求める要求を送信するように構成され、
前記複数の論理的レプリカから前記要求に対する複数の応答を受信するように構成され、
前記複数の応答から、該クライアントによる資源へのアクセスが許可されるどうかを判定し、該クライアントが許可されない場合に、資源へのアクセスを求める要求を再送しないように構成される
ことを特徴とするシステム。
【請求項２１】
それぞれの前記クライアントは、前記複数の論理的レプリカのうちの所定数の論理的レプリカと排他的に関連づけられる場合に許可されることを特徴とする請求項２０に記載のシステム。
【請求項２２】
それぞれの前記クライアントは、前記複数の応答から、前記複数のクライアントのうちの１つによる１つの資源へのアクセスが許可されるかどうかを判定するように構成され、
前記複数のクライアントのいずれも許可されない場合、排他的に関連づけられているクライアントとして自身を示す値を含む応答を受信したクライアントが、該応答を送信した論理的レプリカに、該論理的レプリカとの排他的関連付けを解放させるための移譲メッセージを送信するように構成され、
前記移譲メッセージを受信した論理的レプリカは、該論理的レプリカのキューに格納されたこれまでの要求に基づいて別の応答を送信するように構成される
ことを特徴とする請求項２０に記載のシステム。
【請求項２３】
分散ハッシュテーブルが、前記複数の資源を複数のバケットに分割し、
前記複数のバケットが、ピアツーピアネットワーク内の前記複数のコンピューティングデバイスによって提供され、
それぞれの前記バケットを提供する１つの前記コンピューティングデバイスが前記複数のクライアントにとって利用可能でない場合、該バケットが別の前記コンピューティングデバイスによって利用可能にされるように、前記複数のコンピューティングデバイスがフェイルオーバ機能を備えるように構成される
ことを特徴とする請求項２０に記載のシステム。
【請求項２４】
それぞれの前記論理的レプリカが、応答を受信するための予想待機時間を提供するインフォームドバックオフメカニズムを使用するように構成され、
前記予想待機時間は、それぞれの前記要求を再送する前に前記クライアントが待機すべき時間の長さを定める
ことを特徴とする請求項２０に記載のシステム。
【請求項２５】
前記論理的レプリカは、コーラムコンセンサスプロトコルを用いて資源へのアクセスを許可するように構成されることを特徴とする請求項２３に記載のシステム。
【請求項２６】
それぞれの前記論理的レプリカが、前記複数のコンピューティングデバイスのうちの１つまたは複数によって実行可能なピアであることを特徴とする請求項２０に記載のシステム。
【請求項２７】
前記コーラムコンセンサスプロトコルが、前記複数の論理的レプリカのうちの所定数の論理的レプリカと排他的に関連づけられたクライアントから資源へのアクセスを許可することを特徴とする請求項２０に記載のシステム。
【請求項２８】
資源へのアクセスを求める複数の要求を送信する手段と、
前記送信する手段を通信可能な結合でネットワーキングする手段と、
前記ネットワーキングする手段に通信可能に結合し、資源を提供する手段のレプリカである複数の論理的レプリカ手段を含む、資源を提供する手段と
を備えたシステムにおいて、それぞれの該論理的レプリカ手段は、
前記複数の要求を送信する手段のうちの１つの送信する手段と、他の送信する手段に該論理レプリカ手段の資源へのアクセス許可を与えることができないことを示す排他的関連づけがされるように構成され、
前記論理的レプリカ手段が別の送信する手段と排他的に関連づけられる場合に、該論理的レプリカ手段に対応する提供する手段が提供する資源へのアクセスを求める送信する手段からの要求を格納するためのキューを含み、
該論理的レプリカ手段に排他的に関連づけられている前記送信する手段を示す値を含む、前記複数の要求のそれぞれに対する応答を送信するように構成され、
該論理的レプリカ手段との排他的関連付けを解放させるための移譲（Yield）メッセージに応答して、該論理的レプリカ手段のキューに格納されたこれまでの要求に基づいて別の応答を送信するように構成され、
それぞれの前記送信する手段は、
複数の論理的レプリカ手段に、該論理的レプリカ手段の資源へのアクセスを求める要求を送信するように構成され、
前記複数の論理的レプリカ手段から前記要求に対する複数の応答を受信するように構成され、
前記複数の応答から、前記複数の送信する手段のうちの１つに資源へのアクセスが許可されるどうかを判定するように構成され、
前記複数の送信する手段のいずれも許可されない場合に、排他的に関連づけられている送信する手段として自身を示す値を含む応答を送信した論理的レプリカ手段に、前記移譲メッセージを送信するように構成される
ことを特徴とするシステム。
【請求項２９】
前記提供する手段が、
ピアツーピアネットワークを形成するように通信可能に結合した複数のコンピューティングデバイスと、
分散ハッシュテーブルと
を含み、
前記送信する手段が、複数のクライアントを含む
ことを特徴とする請求項２８に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはピアツーピア（peer-to-peer）ネットワークに関し、より詳細には、動的ピアツーピア環境における相互排除技法(mutual exclusion technique)に関する。
【背景技術】
【０００２】
最近、ピアツーピアネットワークが産学双方においてますます注目を集めている。ピアツーピアネットワークは、適応、自己組織化、負荷分散、フォールトトレランス(耐故障性)、低コスト、高可用性、スケーラビリティ（拡張可能性）等の多くの望ましい特徴を備え、大規模な資源（リソース）のプール（集まり）を提供するように構成することができる。ピアツーピアネットワークは、ピアツーピアウェブサイトを通じてのダウンロードのために利用可能なものとして参照される楽曲をピアがダウンロードすること等によって、大量のデータを共有するための人気のある方法として出現した。
【０００３】
複数のクライアントによる使用のために資源を提供する場合、２つ以上のクライアントが特定の資源へのアクセスを希望する状況が生じることがある。これは「衝突（コリジョン）」とも呼ばれる。相互排除技法とは、特定の資源へのアクセスを希望する相異なるクライアントが衝突して望ましくない相互作用を引き起こすことがないように、資源を共有するために用いられ得る技法のことである。相互排除技法を用いることにより、クライアントは、使われている特定の相互排除技法によって指定されるところに従って、資源にアクセスする「権利」を取得することができる。
【０００４】
相互排除技法の一例として、セマフォ（semaphore）の利用がある。セマフォは、各クライアントがチェックしてから変更することができる値である。見出される値に応じて、クライアントは、資源を使用することができる場合もあり、あるいは、既に使用中であることを知り再試行する場合もある。通常、セマフォを使用するクライアントは、その値をチェックして、他のクライアントが資源を使用していない場合、その資源がそのクライアントによって使用されていることを反映するようにその値を変更し、その特定の資源が使用中であることを後のクライアントが「知る」ようにする。こうして、セマフォは、複数のクライアントが、特定のファイルへのアクセスを共有する場合のように、同一資源に対して競合するアクティビティ（活動）を調整し同期させるための技法を提供する。
【０００５】
【非特許文献１】I. Clarke, B. Wiley, O. Sanberg, and T. Hong 「Freenet: A Distributed Anonymous Information Storage and Retrieval System」（Proc. Int. Workshop on Design Issues in Anonymity and Unobservability, Springer Verlag, LNCS 2009, 2001）
【非特許文献２】I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, H. Balakrishnan 「Chord A Scalable Peer-to-peer Lookup Service for Internet Applications」（Proc. ACM SIGCOMM'0l, San Diego, California, USA, 2001）
【非特許文献３】S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker 「A Scalable Content-Addressable Network」（Proc. ACM SIGCOMM'0l, San Diego, California, USA, 2001）
【非特許文献４】A. Rowstron and P. Druschel 「Pastry: Scalable, Decentralized Object Location and Routing for Large-Scale Peer-to-Peer Systems」（IFIP/ACM Int. Conf. Distributed Systems Platforms (Middleware), 2001）
【非特許文献５】Tapestry。B. Y. Zhao, J. Kubiatowicz, and A. D. Joseph 「Tapestry: An Infrastructure for Fault-tolerant Wide-Area Location and Routing」（Technical Report No. UCB/CSD-01-1141, Univ. of California, Berkeley）。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかし、従来の相互排除技法では、特定の資源の利用を希望するクライアント間の衝突によって引き起こされる問題が、クライアントの「貪欲な」挙動によって拡大してしまう。例えば、複数のクライアントがある資源へのアクセスを希望し、相互排除技法の使用により１つのクライアントのみがその資源にアクセスする権利を「勝ち取る」場合を考える。その場合、資源にアクセスする権利が得られなかった「敗者の」クライアントは、要求を継続的に再送することによって権利を獲得しようと再試行する。要求の反復再送は、資源を提供するピアと、資源へのアクセスを取得しようとするクライアントのハードウェアおよびソフトウェアの資源を浪費する。また、反復再送は、クライアントとピアの間のネットワーク帯域幅も浪費する。この問題は、同じ資源へのアクセスを希望するクライアントの数が増大するにつれてさらに拡大し、一層非効率になるという結果を招いていた。
【０００７】
さらに、ピアツーピアネットワーク内の複数のクライアントと複数のピアとの間の通信は、互いに異なる通信遅延を受けることがある。例えば、複数のクライアントから受信される、特定の資源にアクセスすることを求める要求は、クライアントとピアの間の通信遅延の変動により、異なる時刻に異なるピアに到達することがある。
【０００８】
したがって、動的ピアツーピア環境において使用するための相互排除技法の必要性が引き続き存在している。
【課題を解決するための手段】
【０００９】
動的ピアツーピア環境において使用するための相互排除技法が記載される。一例では、相互排除技法はクライアントとピアの間の通信遅延の変動を解決するために、キュー（queue:待行列）を利用する。ピアが、要求がいつ受信されたかについての一貫したビュー（一覧）を得ることにより、キューに基づいて資源へのアクセスを与えることができるように、要求を格納するために、ピアによってキューは利用されることが可能である。別の例では、クライアントが資源にアクセスすることを求める要求を継続的に再送しようとしないように、キューに要求を格納することによって、キューの使用によりクライアントの「貪欲な」挙動を低減する。
【００１０】
一実施態様では、本発明の方法は、複数の論理的レプリカ（logical replica）のそれぞれにおいて、クライアントから要求を受信することを含む。それぞれの論理的レプリカ(複製)はキューを含み、１つのクライアントと排他的に関連づけられる。要求は、複数の資源のうちの１つにアクセスすることを求める要求である。論理的レプリカのうちの特定の１つが別の１つのクライアントと排他的に関連づけられていると、要求は、その特定の論理的レプリカのキューに格納される。
【００１１】
さらなる実施態様では、本発明の方法は、複数の論理的レプリカへの通信のためにクライアントが要求を形成することを含む。要求は、複数の資源のうちの１つの資源に対する要求である。クライアントは、複数の論理的レプリカから複数の応答を受信し、クライアントが上記１つの資源の利用を許可されるのかどうかを判断する。クライアントは、別のクライアントが上記１つの資源の利用を許可されている場合には、別の要求を送信することなく、別の複数の応答を待機する。
【００１２】
別の実施態様では、本発明の方法は、複数のクライアントのそれぞれにおいて、複数の論理的レプリカへの通信のために、複数の資源のうちの１つの資源を求める要求を形成することを含む。複数の応答が、複数の論理的レプリカから複数のクライアントで受信される。それぞれのクライアントは、上記複数の応答を使用することによって、複数のクライアントのうちの１つが上記１つの資源の利用を許可されているかどうかを判断する。複数のクライアントのいずれも上記１つの資源の利用を許可されていない場合には、複数の論理的レプリカのうちの１つまたは複数への通信のために、移譲メッセージ（yield message）が、少なくとも１つのクライアントによって形成される。移譲メッセージにより、１つまたは複数の論理的レプリカのそれぞれは、１つまたは複数のクライアントから受信されたこれまでの要求を格納するそれぞれのキューから別の応答を形成する。
【００１３】
さらに別の実施態様では、ピアツーピアネットワークは、コーラムコンセンサス(quorum consensus：定足数合意)プロトコルを用いて資源アクセスを許可する論理的レプリカを含む。
【００１４】
さらに別の実施態様では、本発明のシステムは、ネットワーク、複数のクライアント、およびネットワークに通信可能に結合した複数のコンピューティングデバイスを含む。複数のコンピューティングデバイスは、複数の論理的レプリカを含む。それぞれの論理的レプリカは、任意の一特定時刻において複数のクライアントのうちの１つのクライアントと排他的に関連づけられるように構成される。また、それぞれの論理的レプリカは、その論理的レプリカが別のクライアントと排他的に関連づけられる時に資源にアクセスするために、１つのクライアントからの要求を格納するためのキューも含む。
【００１５】
明細書および図面の全体を通じて、同一番号は同一のコンポーネントおよび特徴部を参照するために用いられる。
【発明を実施するための最良の形態】
【００１６】
［概要］
動的ピアツーピア環境において使用するための相互排除技法が記載される。一例では、相互排除技法はクライアントとピアの間の通信遅延の変動を解決するためにキューを利用する。既に述べたように、複数のクライアントから受信される、特定の資源にアクセスすることを求める要求は、クライアントとピアの間の通信遅延の変動により、異なる時刻に異なるピアに到達することがある。したがって、ピアは、資源へのアクセスを要求しているクライアントについて、それぞれのクライアントがそのようなアクセスを要求した場合等には、一貫したビューを有しないことがある。キューは、ピアが、要求がいつ受信されたかについての一貫したビューを得ることにより、キューに基づいて資源へのアクセスを提供することができるように、要求を格納するためにピアによって利用されることが可能である。
【００１７】
さらに、キューは、クライアントの「貪欲な」挙動を低減する。例えば、クライアントが資源にアクセスすることを求める要求を継続的に再送しようとしないように、クライアントからの要求を格納するためにキューを利用することができる。したがって、クライアントは、要求に対するピアからの応答を待機する「アクティブウェイティング（稼動中待機）」の状態にあるとみなしてもよい。要求に対する応答が、規定期間（specified period）後に受信されない場合にクライアントが要求を再送することができるように、インフォームドバックオフメカニズム(informed backoff mechanism：情報に基づく一時退避機構)を使用してもよい。
【００１８】
［例示的環境］
図１は、ピアツーピアネットワークを提供するように構成された環境１００を示す例示的実施態様の図である。環境１００は、複数のクライアント１０２（ａ）を含む。ここでａは１からＡまでの任意の整数をとり得る。複数のクライアント１０２（ａ）は、ネットワーク１０６を通じて複数のコンピューティングデバイス１０４（１）〜１０４（Ｂ）に通信可能に接続する。この実施態様では、複数のクライアント１０２（ａ）および複数のコンピューティングデバイス１０４（１）〜１０４（Ｂ）はそれぞれ、ネットワーク１０６内のノードを表す。ノードは、他のノードにデータを提供する再配信ポイント、および／または、データの宛先および／またはソースであるエンドポイントのような、データを送信するための接続ポイントとみなしてもよい。
【００１９】
複数のクライアント１０２（ａ）および複数のコンピューティングデバイス１０４（１）〜１０４（Ｂ）は、さまざまな方法で構成され得る。例えば、クライアント１０２（ａ）およびコンピューティングデバイス１０４（１）〜１０４（Ｂ）は、無線電話機（例えばコンピューティングデバイス１０４（１））、タブレットコンピュータ（例えばコンピューティングデバイス１０４（２））、ノートブックコンピュータ（例えばコンピューティングデバイス１０４（３））、デスクトップコンピュータ（例えばコンピューティングデバイス１０４（４））、サーバ（例えばコンピューティングデバイス１０４（５）〜１０４（６））、メインフレームコンピュータ（例えばコンピューティングデバイス１０４（Ｂ））、ならびに移動局、娯楽機器、セットトップボックス等の他のコンピューティングデバイスのように、ネットワーク１０６を通じて通信可能なコンピュータとして構成されてもよい。例示的なコンピューティングデバイスについては、さらに図７に関して説明される。したがって、複数のクライアント１０２（ａ）およびコンピューティングデバイス１０４（１）〜１０４（Ｂ）は、大量のメモリおよびプロセッサ資源を有するフル資源デバイス（例えば、パーソナルコンピュータ、ハードディスク付きテレビレコーダ）から、メモリおよび／またはプロセッサ資源が限定された低資源デバイス（例えば従来のセットトップボックス）までさまざまであり得る。また、クライアント１０２（ａ）は、そのクライアントを操作する人および／またはエンティティに関係していてもよい。すなわち、クライアント１０２（ａ）は、ユーザおよび／またはマシンを含む論理クライアントを記述するものであってもよい。
【００２０】
ネットワーク１０６は、ピアツーピアネットワークとして構成される。ピアツーピアネットワークにより、ネットワーク１０６のノードは、それぞれのノード、すなわち、複数のクライアント１０２（ａ）および複数のコンピューティングデバイス１０４（１）〜１０４（Ｂ）に配置された共有資源にアクセスすることができる。これまでに知られ、使用されているピアツーピアネットワークの例としては以下のものがある。
【００２１】
・フリーネット（Feenet；草の根ネット、無料ネット）、非特許文献１に記載。
・コード(Chord)、         非特許文献２に記載。
・キャン(CAN)、           非特許文献３に記載。
・ペストリー(Pastry)、    非特許文献４に記載。
・タペストリー(Tapestry)、非特許文献５に記載。
【００２２】
ピアツーピアネットワークは、冗長性およびフォールトトレランス（耐故障性）のようなさまざまな特徴を備えることができる。例えば、ピアツーピアネットワークに格納されたデータは、データがピアツーピアネットワークのノードによって複製されるにつれて徐々に拡散し得る。したがって、ピアツーピアネットワークにおいてデータは高度に冗長となるため、データの信頼性および可用性を向上させることができる。
【００２３】
ピアツーピアネットワークを用いて、データ、処理サイクル、データストレージ等のようなさまざまな資源（リソース）を交換することができる。したがって、ピアツーピアネットワークを利用して、複数のクライアント１０２（ａ）および複数のコンピューティングデバイス１０４（１）〜１０４（Ｂ）の集団パワーを活用することができる。ピアツーピアは、各ピアすなわち「メンバ」が、別のメンバと直接に、および／または介在するサーバを通じて、通信することができる通信モデルである。
【００２４】
ネットワーク１０６は、クライアント１０２（ａ）と複数のコンピューティングデバイス１０４（１）〜１０４（Ｂ）の間でメッセージをルーティングするためのインタフェースとして作用する分散ハッシュテーブル（ＤＨＴ）１０８を含む。ＤＨＴ１０８は、（key(キー)，value(値)）の対を格納するハッシュテーブルデータ構造の分散バージョンとみなすことができる。例えば、キーはファイル名に対応し、値はファイルの内容に対応するとしてよい。ネットワーク１０６内の各ピア、例えばコンピューティングデバイス１０４（１）〜１０４（Ｂ）は、（key，value）の対のペアのサブセットを格納する。こうして、ＤＨＴ１０８は、対応するキーを受け持つノードを見つけるために利用される。すなわち、ＤＨＴ１０８は、クライアント１０２（ａ）と複数のコンピューティングデバイス１０４（１）〜１０４（Ｂ）の間でメッセージをルーティングするために、キーをノードにマッピングする。ＤＨＴ１０８の「上（on-top）」に、ファイル共有サービス、アーカイブ(archival)ストレージサービス（例えばウェブアーカイビング）、データベース、名前付けサービス、サービスディスカバリ、アプリケーション層マルチキャスト、イベント通知、チャットサービス、ランデブー方式の通信、問合せと索引付け、データ公開／サブスクリプション等のようなさまざまなサービスを構築することができる。
【００２５】
ＤＨＴ１０８は、複数のコンピューティングデバイス１０４（１）〜１０４（Ｂ）によって提供される資源を複数のバケット１１０（１）〜１１０（８）に分割する。複数のバケット１１０（１）〜１１０（８）のそれぞれは、資源のゾーンとみなすことができる。例えば、前述のように、ＤＨＴ１０８は資源をキーと関連づける。キーは、ＤＨＴ１０８を用いて複数のバケット１１０（１）〜１１０（８）のうちの特定の１つを見つけるためにハッシュされる。複数のバケット１１０（１）〜１１０（８）は、さまざまな方法で提供され得る。例えば、図１では、バケット１１０（１）は、コンピューティングデバイス１０４（１）によって提供されるものとして図示されている。同様に、バケット１１０（２）、１１０（３）、１１０（４）、１１０（５）、１１０（６）はそれぞれ、コンピューティングデバイス１０４（２）、１０４（３）、１０４（４）、１０４（５）、１０４（６）によって提供される。さらに、１つのコンピューティングデバイスが複数のバケットを提供してもよい。これについて、図１では、バケット１１０（７）、１１０（８）がコンピューティングデバイス１０４（Ｂ）によって提供されるものとして図示されている。
【００２６】
環境１００は、ＤＨＴ１０８を使用するピアツーピアネットワークとして構成される場合、参加するピアを構成員とする仮想空間を提供する。この仮想空間は、メンバシップ（会員）変更中の過渡的期間中を除いて、「穴」がないように提供することができる。例えば、コンピューティングデバイス１０４（６）が、ハードウェア、ソフトウェア、および／またはネットワークのエラー等により利用不能となった場合、コンピューティングデバイス１０４（６）によって提供されるバケット１１０（６）は、別のコンピューティングデバイス、例えばコンピューティングデバイス１０４（Ｂ）によって提供され得る。このように、ネットワーク１０６は動的であるため、ネットワークを途絶させることなくノードがネットワークに出入りすることができる。
【００２７】
ＤＨＴ１０８を用いると、複数のコンピューティングデバイス１０４（１）〜１０４（Ｂ）から集合的に、穴のない論理空間を形成することができるので、論理的レプリカ１１２（１）〜１１２（４）（レプリカ）のセットを実装することができる。例えば、与えられた資源Ｒに対して、それに関連づけられたコンピューティングデバイスＣＳ（Ｒ）は〈論理的〉であることが可能である。例として、「／ｆｏｏ／ｂａｒ：ｉ」という名前のｎ個のレプリカがあるとする。ここで、ｉ∈［１．．ｎ］である。これらの名前をハッシュしてキーを導出し、各キーのホスティングノードをレプリカとすることができる。名前付けと実際のコンピューティングデバイスの分離により、「仮想コンピューティングデバイス」が提供される。この仮想コンピューティングデバイスは、「always〈常時〉」利用可能とみなせるが、ランダムな時点でメモリ喪失を被る可能性がある。さらに、後で図３および図６に関してさらに詳細に説明するように、複数のレプリカの導入は、クライアントとこれらのレプリカの間の遅延が変動することにより、パフォーマンスに影響を及ぼし得ることを意味する。
【００２８】
このように、クライアント１０２（ａ）の視点から見ると、レプリカ１１２（１）〜１１２（４）は常時利用可能、例えば「オンライン」である。しかし、前に述べたように、レプリカ１１２（１）〜１１２（４）のいずれも、時に完全なメモリ喪失を被る可能性がある。例えば、レプリカ１１２（１）〜１１２（４）のうちの特定の１つを提供するコンピューティングデバイス１０４（１）〜１０４（Ｂ）のうちの１つが利用不能となり、コンピューティングデバイス１０４（１）〜１０４（Ｂ）のうちの別のコンピューティングデバイスで置き換えられると、ランダムなリセットが起こることがある。
【００２９】
また、レプリカ１１２（１）〜１１２（４）は、複数のクライアントが同一資源にアクセスしようとする時に、その複数のクライアント１０２（ａ）のうちの２つ以上の間の衝突を管理するためのメカニズムを提供してもよい。例えば、レプリカ１１２（１）〜１１２（４）は、同一資源へのアクセスを希望する複数のクライアントのうちの１つにアクセスを許可するために用いられるコーラム（quorum）コンセンサスプロトコルを使用する相互排除技法を利用してもよい。この状況は、以下の説明の一部では「クリティカルセクション(critical section:重要域)」とも呼ばれ、数式および図面では「ＣＳ」と記載される。レプリカ１１２（１）〜１１２（４）は、クライアント１０２（ａ）がクリティカル（重要）な資源へのアクセスをシリアライズする（順番に並べる）のを助けるプロセスとみなしてもよい。レプリカは、〈仮想名〉によって識別され、これは環境１００全体に既知であるとしてもよい。レプリカが環境１００を離脱した場合（例えばクラッシュした場合）、「新規な」レプリカが古いレプリカを置き換え、同じ仮想名をとる。実際には、このような仮想名は、ドメインネームサーバによって、あるいはピアツーピアシステム内のＤＨＴ１０８等によって、実装することができる。このような仮想名前付けメカニズムのため、システム内のレプリカの数は、システムの寿命を通じて固定することができる。相互排除技法の実行については、図３〜図５に関してさらに説明される。
【００３０】
このように、環境１００は、クライアント１０２（ａ）によって「常時」利用可能とみなされるレプリカ１１２（１）〜１１２（４）を提供することができる。しかし、論理的レプリカ１１２（１）〜１１２（４）の内部状態は、ランダムにリセットされ得る。さらに、環境１００内のクライアント１０２（ａ）の数は予測不能であっても、非常に大きくてもよい。
【００３１】
クライアント１０２（ａ）およびレプリカ１１２（１）〜１１２（４）は、要求および応答のようなメッセージを用いることによって、ネットワーク１０６を通じて通信することができる。これについては、図６に関してさらに説明される。一実施態様では、クライアント１０２（ａ）およびレプリカ１１２（１）〜１１２（４）を通信可能に結合するネットワーク１０６は、信頼できなくてもよい。すなわち、メッセージが複製および／または喪失される可能性がある。以下の説明との関連では、クライアント１０２（ａ）およびレプリカ１１２（１）〜１１２（４）は両方ともＤＨＴ１０８内のピアである。しかし、別の実施態様では、レプリカ１１２（１）〜１１２（４）のみがＤＨＴ１０８内のピアとして認識される。
【００３２】
レプリカ１１２（１）〜１１２（４）は、さまざまな方法でコンピューティングデバイス１０４（１）〜１０４（Ｂ）によって提供される資源へのアクセスを許可するために利用することができる。例えば、それぞれのレプリカ１１２（１）〜１１２（４）が、「擬似先着順」で特定の資源へのアクセスの許可を与えることができる。例として、各レプリカ１１２（１）〜１１２（４）は、要求がクライアント１０２（ａ）からレプリカ１１２（１）〜１１２（４）によって受信された順序に基づいて、その特定の資源へのアクセスの許可を与えることができる。レプリカがクライアントに許可を与えた（すなわち投票した）場合、そのクライアントはそのレプリカの〈オーナ〉(owner)と呼ばれる。すなわち、レプリカは、そのように所有されている間は、別のクライアントによって所有されることができないように、そのクライアントと排他的に関連づけられる。レプリカのオーナシップ（所有権）の過半数を集めたクライアントは、相互排除プロトコルのその実行の〈勝者〉(winner)であるといい、それにより資源へのアクセスが許可される。応答の使用によるレプリカのオーナシップおよび投票については、図３および図６に関してさらに説明される。
【００３３】
７個のコンピューティングデバイス１０４（１）〜１０４（Ｂ）が図示されているが、多様なコンピューティングデバイスを環境内に実装することができる。さらに、複数のクライアント１０２（ａ）がピアツーピアネットワーク内の「ピア」として構成されてもよい。
【００３４】
［相互排除］
相互排除は、ピアツーピアＤＨＴを使用するように構成されたネットワーク環境の上に一般的なシステムおよびアプリケーションを実装するための基本的プリミティブ（primitive）の１つである。このようなプリミティブは、必要な時に１つまたは複数の任意の資源を保護するためにピアツーピアＤＨＴの上で実行されるアプリケーションが利用するための基本的サービスも提供することができる。例えば、相互排除は、ミュータブル（mutable:易変）分散ファイルシステムのための並行処理制御メカニズムを提供することができる。ノードの追加および／または削除のような図１の環境１００における変化をサポートするため、このようなプリミティブは、ピアツーピアＤＨＴの〈内部〉に実装される。したがって、相互排除プロトコルの実装は分散していてもよい。
【００３５】
ピアツーピア環境、例えば図１の環境１００のオープンで動的な性質は、さまざまな課題をもたらす。例えば、従来の相互排除プロトコルでは、ノード数が比較的少なく、一定である閉じた（クローズド）システムを仮定していることが多い。このような従来のシステム内のノードは、コンセンサス（合意）に達するために相互に通信する。しかし、この解決法は、クライアント数が予測不能の場合、および／または多数のクライアントを含む場合には、用いることができない。以下では、協調的ストラテジ（方策、戦略）を用いて遅延変動およびコンテンション（競合）を回避することによってクライアントとレプリカの間の高いネットワーク遅延変動を解決し、それによりスケーラビリティ（拡張可能性）およびロバスト性（堅牢性、信頼性）を達成する相互排除技法について説明する。また、レプリカの状態をインテリジェント（知的）に再構築することにより、レプリカのランダムなリセットに対処する〈インフォームドバックオフ〉メカニズムについて説明する。
【００３６】
［例示的プロトコル］
特定の資源に対する衝突する要求を解決するために利用可能な相互排除プロトコルについて説明する。例えば、クリティカルセクション（ＣＳ）（例えば特定の資源）の利用を希望している複数のクライアント１０２（ａ）のうちの２つ以上が、それぞれのレプリカ１１２（１）〜１１２（４）に要求を送信し、応答を待機する。それぞれのレプリカ１１２（１）〜１１２（４）は、それが他のクライアントによって所有されていない場合、リース（賃貸）を与える。それ以外の場合、それぞれのレプリカ１１２（１）〜１１２（４）は、要求を拒絶し、（拒絶された）要求側クライアントに対して、どのクライアント１０２（ａ）が現在のオーナであるかを通知する。ｎ個のレプリカのうちのｍ個を所有するクライアント１０２（ａ）がこのラウンドの勝者であり、したがってクリティカルセクション（ＣＳ）へのアクセスが許可されるように、コーラムコンセンサス技法を使用することができる。ここで、ｍはコーラムの数であり、ｎはレプリカの数である。コーラムは、ｍ＞ｎ／２等のさまざまな方法で決定することができる。従来、ＣＳへのアクセスが許可されないクライアント、すなわちそのラウンドの「敗者」は、獲得した票（もしあれば）を解放し、バックオフ（後退）し、要求を再試行していた。
【００３７】
しかし、レプリカ１１２（１）〜１１２（４）はランダムなリセットを被った後、過去の決定を忘却し、新たな要求を受けることがある。この「心変わり」の結果、相互排除が破れる可能性がある。例えば、ノードの平均寿命がＴであると仮定すると、ノードが期間ｔの間にクラッシュする確率はｔ／Ｔである。ｍ個の投票されたレプリカのうちの任意のｋ個がリセットする確率は次のとおりであることが示される。
【００３８】
【数１】
0004837929.tif 000002
【００３９】
上式で示されるように、ｔの間に２ｍ−ｎ回以上のリセットが起こる場合に安全性が破れる。その確率は次のように表される。
【００４０】
【数２】
0004837929.tif 000003
【００４１】
したがって、ｋ個までのレプリカのリセットを許容するには、ｎ＝３ｋ＋１およびｍ＝２ｋ＋１であるのが望ましい。そこで、設計上の選択事項として、ｍの値を大きくしてもよい。
【００４２】
図２は、図１のクライアント１０２（ａ）およびレプリカ１１２（ｉ）のアーキテクチャを示すシステム２００の例示的実施態様をさらに詳細に示す図である。ここで、ｉは１からＩまでの任意の整数をとり得る。クライアント１０２（ａ）は、クライアントＩＤ２０２および応答配列２０４を含むように示されている。クライアントＩＤ２０２は、レプリカ１１２（１）がクライアント１０２（ａ）を識別するためのものである。応答配列２０４は、図１の複数のレプリカ１１２（１）〜１１２（４）からの複数の応答２０６（ｉ）を格納するように構成される。例えば、応答２０６（ｉ）は、「ｉ番目」のレプリカ、すなわちレプリカ１１２（ｉ）から得られる応答を格納するために利用されることが可能であり、対応するレプリカのオーナ２０８（ｉ）を示すデータと、形成された応答２０６（ｉ）の元になった要求をレプリカが受信した時を示す関連するタイムスタンプ２１０（ｉ）を含む。
【００４３】
レプリカ１１２（ｉ）は、複数のクライアント１０２（ａ）のうちの（もしあれば）いずれのクライアントがレプリカ１１２（ｉ）を所有しているかを示すためのオーナシップフィールド２１２（ｉ）を保持する。オーナシップフィールド２１２（ｉ）は、図２に示すように「Ｃｏｗｎｅｒ」とも表される。オーナシップフィールド２１２（ｉ）の値が「ｎｉｌ」であることは、レプリカ１１２（ｉ）がクライアント１０２（ａ）のいずれかに対して投票していないことを意味する。すなわち、レプリカ１１２（ｉ）は、現在、クライアントと排他的に関連づけられていない。タイムスタンプフィールド２１２（ｉ）「Ｔｏｗｎｅｒ」は、要求がレプリカ１１２（ｉ）によって受信された時のタイムスタンプを格納する。
【００４４】
レプリカ１１２（ｉ）は、複数のクライアント１０２（ａ）から受信された要求２１６（ａ）を格納するキュー２１４（ｉ）を含む。キューに格納される各要求２１６（ａ）は、複数のクライアント１０２（ａ）の１つに対応することができる。キュー２１４（ｉ）は、それぞれの要求２１６（ａ）が受信された順序で要求２１６（ａ）を格納するように構成され得る。例えば、キュー２１４（ｉ）は、ランポート(Lamport)の論理クロックのようなクロックを利用して、それぞれの要求２１６（ａ）に対するタイムスタンプ（時刻印）２１８（ａ）を生成することができる。そして、キュー２１４（ｉ）は、それぞれのタイムスタンプ２１８（ａ）に基づいて、要求２１６（ａ）を編成することができる。別の例として、各要求は、クライアント１０２（ａ）自身によってタイムスタンプが付けられてもよい。図１のクライアント１０２（ａ）および複数のレプリカ１１２（１）〜１１２（４）のオペレーションの一例は、以下の実施態様に示される。
【００４５】
［例示的手続き］
以下では、前述のアーキテクチャを利用して実施され得る相互排除技法について説明する。各手続きの態様は、ハードウェア、ファームウェア、もしくはソフトウェア、またはそれらの組合せのいずれで実施してもよい。手続きは、１つまたは複数のデバイスによって実行されるオペレーションを指定するブロックのセットとして示される。
【００４６】
図３は、図１のクライアント１０２（ａ）がピアツーピアネットワーク内の複数のピアのうちの１つまたは複数によって提供される資源へのアクセスを要求する例示的実施態様における手続き３００を示す流れ図である。ブロック３０２で、クライアント１０２（ａ）は、要求３０４を形成し、複数のレプリカ１１２（１）〜１１２（４）のそれぞれに伝達する。複数のレプリカ１１２（１）〜１１２（４）のそれぞれがクライアント１０２（ａ）を互いに区別することができるように、要求３０４は、ピアツーピア環境において提供される複数の資源のうちの特定の１つを識別し、図２のクライアントＩＤ２０２を含む。
【００４７】
ブロック３０６で、レプリカ１１２（１）〜１１２（４）はオーナシップを判定する。例えば、それぞれのレプリカ１１２（１）〜１１２（４）が、それぞれのオーナシップフィールド２１２（１）〜２１２（４）について問い合わせてもよい。オーナシップフィールド２１２（１）〜２１２（４）の値は、どのクライアント（もしあれば）がそれぞれのレプリカ１１２（１）〜１１２（４）を所有するかを示す。例えば、レプリカ１１２（１）のオーナシップフィールド２１２（１）は仮想線で「ｎｉｌ（空）」であるように示されているが、これは、レプリカ１１２（１）が現在クライアントによって所有されていないことを示す。同様に、それぞれのレプリカ１１２（２）、１１２（３）のオーナシップフィールド２１２（２）、２１２（３）もまた、それぞれ「ｎｉｌ」値であるように示されている。したがって、レプリカ１１２（１）〜１１２（３）は、特定のクライアントによるオーナシップの「投票」がなされていない。
【００４８】
これに対して、レプリカ１１２（４）のオーナシップフィールド２１２（４）は、レプリカ１１２（４）がクライアント１０２（１）によって所有されていることを示す値を含むように示されている。このオーナシップの判定に基づいて、レプリカ１１２（４）はキュー２１４（４）に要求３０４を格納するので、クライアント１０２（ａ）は要求を再送する必要がない。これについては、図５に関してさらに詳細に説明する。
【００４９】
ブロック３０８で、それぞれのレプリカ１１２（１）〜１１２（４）が、それぞれの応答３１０〜３１６を形成し、クライアント１０２（ａ）に伝達する。それぞれの応答３１０〜３１６は、それぞれのレプリカ１１２（１）〜１１２（４）のオーナシップの指示を含む。例えば、それぞれの応答３１０〜３１６は、それぞれのレプリカ１１２（１）〜１１２（４）からのオーナシップフィールド（Ｃｏｗｎｅｒ）の値を含んでもよい。
【００５０】
ブロック３１８で、クライアント１０２（ａ）は、応答３１０〜３１６に基づいて資源へのアクセスが許可されるかどうかを判定する。例えば、レプリカ１１２（１）からの応答３１０は、レプリカ１１２（１）が別のクライアントによって所有されなかったことを示すブロック３０６での判定結果を含んでもよい。そのため、レプリカ１１２（１）は今度クライアント１０２（ａ）によって所有される。そのことは、ブロック３１８では、応答３１０に点線ボックスとクライアント１０２（ａ）を記述するテキストが含まれることで示されている。同様に、それぞれのレプリカ１１２（２）、１１２（３）からの応答３１２、３１４もまた、ブロック３０６でのそれぞれの判定結果を含む。例えば、応答３１２、３１４の両方とも、それぞれのレプリカ１１２（２）、１１２（３）が別のクライアントによって所有されなかったことを示しているので、両方のレプリカ１１２（２）、１１２（３）は今度クライアント１０２（ａ）によって所有される。しかし、応答３１６は、対応するレプリカ１１２（４）が別のクライアント、例えばクライアント１０２（１）によって所有されていることを示すブロック３０６での判定結果を含む。
【００５１】
クライアント１０２（ａ）は、応答３１０〜３１６に基づいて資源の利用が許可されるかどうかを判断するためにさまざまな相互排除技法を利用することができる。例えば、クライアント１０２（ａ）は、クライアント１０２（ａ）がｎ個のレプリカ１１２（１）〜１１２（４）のうちのｍ個のオーナシップを取得した場合に資源の利用が許可されるというコーラムコンセンサスプロトコルを使用してもよい。ここで、ｍはコーラムの数であり、ｎはレプリカの数である。すなわち、それぞれのレプリカ１１２（１）〜１１２（４）は、一度にいずれか１つの特定のクライアントと排他的に関連づけられるように構成される。この排他的関連づけを利用することにより、各レプリカは、現在の排他的関連づけが当該特定のクライアントのオーナシップフィールド（Ｃｏｗｎｅｒ）で示されるクライアントに「投票」することができる。
【００５２】
コーラムは、ｍ＞ｎ／２等のさまざまな方法で決定することができる。したがって、クライアント１０２（ａ）は、要求３０４に対するそれぞれの応答３１０〜３１６で示されるレプリカ１１２（１）〜１１２（４）のオーナシップに基づいて、特定の資源へのアクセスが許可されるかどうかを判定することができる。ブロック３０８に示した例では、ｍが３以下である場合、クライアント１０２（ａ）はレプリカ１１２（１）〜１１２（４）のオーナシップのコーラムを有するので、資源の利用が許可される。別の例として、ｍが４に等しい場合、クライアント１０２（ａ）は資源へのアクセスが許可されない。しかし、クライアント１０２（ａ）は、直ちに要求３０４を再送するのではなく、別の応答の受信を待機することができる。というのは、ブロック３０６で要求はキュー２１２（４）に格納されているからである。したがって、クライアント１０２（ａ）が勝っていない場合、クライアントは、レプリカ１１２（１）〜１１２（４）から次の応答を待機する「アクティブウェイティング」の状態に置かれる。キューの利用およびアクティブウェイティングについては、図４および図５に関してさらに説明される。
【００５３】
こうして、例示的手続き３００に示したように、相互排除技法は、応答間を調整するためにレプリカ１１２（１）〜１１２（４）が相互に通信しないように構成され得る。例えば、各レプリカは、自己のローカルな状態のみに基づいてクライアントへ自己の応答を送信することができる。これにより、レプリカ間での調整にかかる時間が節約されるので、クライアントがクリティカルセクションへのアクセスを許可される機会がより高速に提供される。したがって、クライアントは、レプリカからの決定を受動的に待機するのではなく、クライアント選択プロセスに能動的（アクティブ）に関わることができる。
【００５４】
図４は、複数の資源のうちの特定の１つの利用が許可されるかどうかをクライアントが判断する例示的実施態様における手続き４００を示す流れ図である。ブロック４０２で、クライアントは、複数の資源のうちの特定の１つを利用することを求める要求を形成する。要求は、クロック（例えばランポートの論理クロック）から得られるタイムスタンプと、クライアントのＩＤ（例えば図２のクライアントＩＤ２０２）を含む。ブロック４０４で、クライアントは、特定の資源と関連づけられた複数のレプリカのそれぞれに要求を送信し、それにより、それぞれのレプリカが要求のうちの１つを受信する（ブロック４０６）ようにする。
【００５５】
判断ブロック４０８で、それぞれのレプリカは、対応するオーナシップフィールド値が「ｎｉｌ」値であるかどうか、すなわち、そのレプリカが前のクライアントと排他的に関連づけられていないかどうかを判定する。オーナシップフィールド値がｎｉｌである場合、ブロック４１０で、要求からのクライアントＩＤをレプリカのオーナシップフィールド（例えばＣｏｗｎｅｒ）内の値として格納する。さらに、要求内のタイムスタンプの値をレプリカのタイムスタンプフィールド（例えばＴｏｗｎｅｒ）に格納する。ブロック４０８でオーナシップフィールド値が「ｎｉｌ」でない場合、要求は、クライアントＩＤおよびタイムスタンプを含めて、それぞれのレプリカのキューに挿入される。ブロック４１０またはブロック４１２に記載のアクションを実行した後、手続き４００はブロック４１４に進む。
【００５６】
ブロック４１４で、オーナシップフィールドおよびタイムスタンプフィールドのそれぞれの値を含む応答が、それぞれのレプリカによって形成される。ブロック４１６で、レプリカはクライアントへ応答を送信する。例えば、それぞれのレプリカは、図１のネットワーク１０６を通じて応答を通信してもよい。ブロック４１８で、クライアントは、図２の応答配列２０４のような応答配列に応答を格納する。判断ブロック４２０で、勝者を計算するのに十分な応答を受信したかどうかを判定する。この判定はさまざまな方法で実行することができる。例えば、クライアントは、コーラムを形成するのに十分な応答を受信したかどうか、あるいは、要求を受信したそれぞれのレプリカから応答が受信されたかどうか、等を判定することができる。
【００５７】
十分な応答を受信した場合（ブロック４２０）、クライアントは勝者を計算する（ブロック４２２）。勝者はさまざまな方法で計算することができる。例えば、前述のように、クライアントは、ｎ個のレプリカのうちのｍ個のように、クライアントがレプリカのコーラムのオーナシップを取得したかどうかを判定してもよい。
【００５８】
判断ブロック４２４で、クライアントは、勝者が当該クライアントであるかどうかを判定する。勝者が当該クライアントである場合（ブロック４２４）、成功メッセージを当該クライアントへ送信し（ブロック４２６）、特定の資源へのアクセスが許可されたことを当該クライアントが「知る」ようにする。勝者が当該クライアントでない場合（ブロック４２４）、手続き４００は判断ブロック４２８に進む。
【００５９】
判断ブロック４２８で、勝者が別のクライアントであるかどうかを判定する。勝者が別のクライアントである場合、手続きはブロック４３０に進む。ブロック４３０で、クライアントは別の応答を待機し、手続き４００はブロック４１８に戻る。このようにして、クライアントは、前に求めた要求を再送する必要がないような「アクティブウェイティング」の状態に置かれるため、クライアントと論理的レプリカを提供するコンピューティングデバイスのハードウェアおよびソフトウェアの資源、ならびにクライアントとコンピューティングデバイスの間の通信のためのネットワーク資源が節約される。
【００６０】
勝者が別のクライアントでない場合（ブロック４２８）、勝者は今回の「ラウンド」では見つけることができない。例えば、ｊｓａｍｅ＋ｎ−ｊ＜ｍ（ここで、ｊは返された応答の数であり、ｊが同じ項目の最大数がｊｓａｍｅである）である場合、特定の資源へのアクセスを要求するクライアントのうちには、その資源へのアクセスの許可を「勝ち取る」ものはない。したがって、ブロック４３２で、クライアントは、勝者が見つかるように、クライアントによって所有されているそれぞれのレプリカへ移譲メッセージ（yield message）を送信するための移譲オペレーション(yield operation)を開始する。その例については、以下の実施態様でさらに詳細に説明する。
【００６１】
図５は、図４の移譲オペレーションの実行が示される例示的実施態様５００における手続きを示す流れ図である。ブロック５０２で、クライアントを指定するオーナシップフィールド値を有するそれぞれの応答について、その応答を形成し発信した対応するレプリカへ移譲メッセージを送信する。例えば、図３のブロック３１８で、クライアント１０２（ａ）は、クライアント１０２（ａ）がそれぞれのレプリカ１１２（１）〜１１２（３）を所有する（すなわち、それらのレプリカと排他的に関連づけられる）ことを示す対応する応答３１０〜３１４を送信したレプリカ１１２（１）〜１１２（３）へ、移譲メッセージを送信してもよい。
【００６２】
ブロック５０４で、クライアントによって所有されているレプリカが移譲メッセージを受信する。移譲メッセージは、その移譲メッセージを送信したクライアントを識別するためのクライアントＩＤを含む。判断ブロック５０６で、それぞれのレプリカは、クライアントＩＤがそれぞれのレプリカのオーナシップフィールド（Ｃｏｗｎｅｒ）の値に等しいかどうかを判定する。クライアントによって所有されているレプリカにのみ移譲メッセージが送信される実施態様では、判断ブロック５０６は、エラーをチェックする役割を果たし得る。例えば、クライアントＩＤがオーナシップフィールドの値に一致しない場合、エラーがクライアントへ送信される（ブロック５０８）。別の実施態様として、移譲メッセージはすべてのレプリカへ送信されてもよく、その場合、判断ブロック５０６の実行は、それぞれのレプリカによって、移譲メッセージが当該レプリカに「関連性がある」かどうかを判定するために利用され得る。
【００６３】
クライアントＩＤがオーナシップフィールドの値に等しい場合（ブロック５０６）、ブロック５１０で、オーナシップフィールド値およびタイムスタンプフィールド値をキューに挿入する。例えば、オーナシップフィールド値およびタイムスタンプフィールド値をキューにコピーしてもよい。次に、ブロック５１２で、レプリカのオーナシップフィールド値およびタイムスタンプフィールド値をキューの「前」からリセットし、それらの値をセットするために用いられている対応するエントリをキューから削除する。例えば、キューは、最も古いエントリがキューの「前」に位置する（例えば、読み出される最初のエントリとなる）ように、タイムスタンプに従ってキュー内のエントリを編成することにより、例えば擬似的な「先着順」メカニズムを提供してもよい。したがって、ブロック５１０、５１２で、キューからの最新から最も遠い（すなわち最も古い）エントリを用いてオーナシップフィールドおよびタイムスタンプフィールドの値をリセットし、オーナシップフィールドおよびタイムスタンプフィールドの前の値をキューに挿入する。
【００６４】
ブロック５１４で、それぞれのレプリカが、オーナシップフィールドおよびタイムスタンプフィールドのそれぞれの値を含む応答を形成する。ブロック５１６で、応答がレプリカによってクライアントへ送信される。このように、移譲オペレーションの実行は本質的に協調的である。移譲オペレーションの意味は、レプリカが別のクライアントによる所有のために解放され、要求がキューに挿入されるという点で、「解放＋要求」とみなすことができる。解放および要求のオペレーションについては、図６に関してさらに詳細に説明される。こうして、レプリカは、移譲メッセージを受信すると、勝者の地位からクライアントを（すなわち、オーナシップフィールド（Ｃｏｗｎｅｒ）の値を）削除し、それをキューに挿入する。そして、レプリカは、キューから最先のクライアントを選択し、その勝者に通知する。
【００６５】
移譲機能の結果、キューの入れ替えが起こる。例えば、図４でどのクライアントも「勝者」でないことは、クライアントの間にコンテンション（競合）が起きたことを示している。このことは、キューはできているが、ネットワーク遅延等のため、勝者が不適切であるかもしれないことも意味する。移譲メッセージを発行することによって、クライアントは、レプリカに対して、互いに一貫したビューを作ることにより勝者を選択する機会を提供する。手続き５００は、勝者が計算されるまで複数回繰り返してもよい。
【００６６】
［例示的な相互排除プロトコルのアーキテクチャ］
図６は、図４および図５に関して説明したように、図２のクライアント１０２（ａ）およびレプリカ１１２（ｉ）により実行される相互排除プロトコルの一実施態様のアーキテクチャ６００を示すブロック図である。アーキテクチャ６００は、矢印を用いて、図１のクライアント１０２（ａ）とレプリカ１１２（ｉ）の間のメッセージの交換を示している。アーキテクチャ６００は、クライアント１０２（ａ）およびレプリカ１１２（ｉ）のそれぞれのメッセージハンドラを用いて記述することができる。それぞれの例示的オペレーションは、それぞれのデバイスにより実行される例示的な擬似コードに関連して説明される。１つまたは複数のオペレーションが独立に、および／または他のオペレーションの内部に示されているが、オペレーションは、さまざまな方法で組み合わせ、再配置することが可能である。
【００６７】
クライアント１０２（ａ）およびレプリカ１１２（ｉ）はそれぞれ、前述の相互排除を提供するさまざまなオペレーションをサポートすることができる。以下では、クライアント１０２（ａ）とレプリカ１１２（ｉ）の間の通信が、クライアントまたはレプリカ１１２（ｉ）により実行可能なメッセージハンドラを用いて示されるように、オペレーションの実行およびメッセージの交換の例示的順序を説明する。
【００６８】
クライアント１０２（ａ）は、以下の状態変数をサポートする。すなわち、ｉｄは、クライアント１０２（ａ）の識別子（例えば、図２のクライアントＩＤ２０２）であり、ｒｅｓｐ［］は、図２の応答配列２０４のように、レプリカからの応答を格納するために利用される。クライアント１０２（ａ）は、request（要求）６０２オペレーションを開始することにより、資源へのアクセスを制御するために利用されるそれぞれのレプリカに対する要求を形成する。これは、次の擬似コードの実行を通じて実行することができる。
【００６９】
Request(CS) {
timestamp := GetLogicalClock(); // ランポートのクロック
for each R[i] of CS
SendRequest(R[i], id, timestamp);
}
【００７０】
クライアント１０２（ａ）は、複数の資源のうちの特定の１つへのアクセスを希望している。これは、擬似コードにおいて、「ＣＳ」、すなわちクリティカルセクションとして表されている。Ｒ［ｉ］は、クリティカルセクションへのアクセスを許可するために利用される複数のレプリカ、例えばレプリカ１１２（ｉ）のそれぞれを表すために用いられる。「SendRequest」６０４オペレーションは、request６０２オペレーションの「サブオペレーション」として示されているが、各レプリカＲ［ｉ］へ要求を送信するために実行され、クライアント「ｉｄ」およびクロックからのタイムスタンプを含む。
【００７１】
レプリカ１１２（ｉ）は、前述のとおり、以下の状態変数をサポートする。すなわち、Ｃｏｗｎｅｒは、クライアントのオーナであり、Ｔｏｗｎｅｒは、Ｃｏｗｎｅｒ値に対するタイムスタンプである。要求を格納するためにキューが用いられる。クライアント１０２（ａ）から要求を受信すると、レプリカ１１２（ｉ）は、OnRequest６０６オペレーションを実行する。その例示的な擬似コードは次のように表される。
【００７２】
OnRequest(C, timestamp) {
if (Cowner = nil) {
Cowner := C;
Towner := timestamp;
}
else
Queue.Insert(C, timestamp);
SendResponse(C, Cowner, Towner);
}
【００７３】
擬似コードに示したように、レプリカ１１２（ｉ）は、「Ｃ」として表されるクライアントＩＤと、クライアント１０２（ａ）からの要求のタイムスタンプを含む要求を受信する。次に、OnRequest６０６オペレーションは、レプリカオーナシップフィールドＣｏｗｎｅｒが空であるかどうかを判定し、空である場合、クライアントＩＤをオーナシップフィールドに格納し、タイムスタンプをタイムスタンプフィールドＴｏｗｎｅｒに格納する。レプリカオーナシップフィールドがｎｉｌでない場合、キュー(queue)オペレーション６１０のinsert（挿入）６０８オペレーションを実行することによって、クライアントＩＤ「Ｃ」およびタイムスタンプがキューに挿入される。OnRequest６０６オペレーションおよび／またはinsert６０８オペレーションの実行後、レプリカ１１２（ｉ）は、SendResponse６１２オペレーションを実行することにより、クライアント１０２（ａ）「Ｃ」へ、オーナシップフィールドおよびタイムスタンプフィールドの値（ＣｏｗｎｅｒおよびＴｏｗｎｅｒ）を送信する。
【００７４】
レプリカ１１２（ｉ）から１つまたは複数の応答を受信すると、クライアント１０２（ａ）は、OnResponse６１４オペレーションを開始する。これは次のように表すことができる。
【００７５】
OnResponse(R[i], owner, timestamp) {
resp[i].owner := owner;
resp[i].timestamp := timestamp;
【００７６】
擬似コードに示したように、OnResponse６１４オペレーションは、それぞれのレプリカ１１２（ｉ）に対応するそれぞれの配列内の位置に、応答および応答内のタイムスタンプを格納することができる。
【００７７】
続いて、OnResponse６１４オペレーションの実行は、次の擬似コードに示すように、勝者を計算する。
【００７８】
if (enough responses received) {
winner := ComputeWinner();
if (winner = self)  // 場合１
return success;
【００７９】
図４に関して前述し、擬似コードに示したように、クライアント１０２（ａ）は、まず、クライアント１０２（ａ）が資源へのアクセスの許可を「勝ち取った」かどうかを計算することができる。勝ち取った場合、クライアント１０２（ａ）はそのように通知される。そうでない場合、OnResponse６１４オペレーションの実行は以下に示すように続く。
【００８０】
else if (winner = nil) {  // 場合３
for each resp[i].owner is self {
SendYield(R[i], id);
Clear(resp[i]);       // 状態をリセット
}
}
// 場合２：他が勝った場合、待機
}
}
【００８１】
図４および図５に関して前述したように、特定の資源、すなわちクリティカルセクション（ＣＳ）へのアクセスの許可を勝ち取ったクライアントがない場合、クライアント１０２（ａ）は、SendYield６１６オペレーションを開始することにより、クライアント１０２（ａ）によって所有されているそれぞれのレプリカ１１２（ｉ）へ移譲メッセージを送信する。クライアント１０２（ａ）は、別のクライアントが勝者である場合、待機する。そして、クライアント１０２（ａ）は、次の応答を受信するために、自己の状態をリセットする。
【００８２】
レプリカ１１２（ｉ）は、移譲メッセージに応答して、OnYield６１８オペレーションを実行する。これは次のように表すことができる。
【００８３】
OnYield(C) {
if (C = Cowner) {
Queue.Insert(C, Towner);
RespQueue();
}
}
RespQueue() {  // ヘルパルーチン
<Cowner, Towner> := Queue.Front();
SendReponse(Cowner, Cowner, Towner);
Queue.Remove(Cowner);
}
【００８４】
擬似コードに示したように、レプリカ１１２（ｉ）がクライアント１０２（ａ）によって所有されている場合、オーナシップフィールドおよびタイムスタンプフィールドからの値がキューに挿入され、新たな勝者が計算される。OnYield６１８オペレーションは、キューオペレーション６１０のコレクションを利用するRespQueueオペレーションを開始してもよい。例えば、QueueFront６２０オペレーションをまず実行し、キュー内で最も古いエントリを、例えばそれぞれのエントリのタイムスタンプを調べることによって、判定する。次に、SendResponse６１２オペレーションを実行して、QueueFront６２０オペレーションからのキューから選択されるクライアントを指定する別の応答を送信する。そして、remove６２２オペレーションを実行して、レプリカ１１２（ｉ）のＣｏｗｎｅｒフィールドおよびＴｏｗｎｅｒフィールドに入れるために、選択されたクライアントをキューから削除する。
【００８５】
また、クライアントは、release（解放）６２４オペレーションも含む。これは、次の擬似コードを用いて表すことができる。
【００８６】
Release(CS) {
for all R[i] of CS
SendRelease(R[i], id);
}
【００８７】
release６２４オペレーションは、レプリカのオーナシップを放棄するため、またはクライアントによって形成され送信された対応する要求をキューから削除するために実行される。例えば、レプリカは、releaseメッセージを受信した後、OnRelease６２８オペレーションを実行してもよい。これは次のように表される。
【００８８】
OnRelease(C) {
if (C = Cowner) {
Cowner := nil;
if (not Queue.Empty())
RespQueue();
}
else if (Queue.Contains(C))
Queue.Remove(C);
}
【００８９】
擬似コードに示したように、レプリカ１１２（ｉ）がクライアント１０２（ａ）によって所有されている場合、クライアント１０２（ａ）は、ＣｏｗｎｅｒフィールドおよびＴｏｗｎｅｒフィールドから削除される。さらに、QueueEmpty６３０オペレーションを実行して、キューが空であるかどうかを判定する。QueueContains６３２オペレーションは、クライアント１０２（ａ）がレプリカ１１２（ｉ）の現在のオーナでない場合に、キューがクライアント１０２（ａ）からの要求を含むかどうかを判定するために実行される。含む場合、QueueRemove６２２オペレーションを実行して、要求（例えば、クライアントＩＤおよびタイムスタンプ）をキューから削除する。
【００９０】
レプリカは、利用可能な資源の対応するシェアに対して投票するように構成されてもよい。例えば、すべてのコーラムメンバがＤＨＴを形成する場合、各メンバは、代わりに、自己の空間〈シェア〉に投票することができる。そこで、コンセンサスに達するのは、クライアントが全空間のうちｆ＝ｍ／ｎの全〈割合〉を集めた場合である。したがって、動的メンバシップ変化に適応するために同じ性質を保ちながら、レプリカが一定数であることを要しない。
【００９１】
［環境における障害］
上記の相互排除プロトコルは、図１の環境１００における障害を解決するためにも利用可能である。例えば、レプリカは、前のクライアントに既に投票していたかもしれないが、それにもかかわらず、クラッシュ後に、新たなクライアントに投票（すなわち、新たな応答を発行）してもよい。そこで、安全性を破る確率を下げるために、ｍ／ｎの比を高くしてもよい。別の例として、キュー内の各エントリが失われるかもしれないが、その場合、クライアントが、来ることのない応答を待機することになる可能性がある。この例に対処するため、次のセクションで説明する〈インフォームドバックオフ〉メカニズムを利用して、レプリカのメモリを再構築することができる。さらに別の例として、特定の資源（すなわちＣＳ）を現在利用中のクライアントが終了前にクラッシュすることにより、レプリカが「身動きがとれなく」なってしまうことがある。そこで、レプリカは、更新可能なリース付きでクライアントに許可を与えてもよい。リースが満期になると、レプリカは、キュー内の次のクライアント（もしあれば）に許可を与える。さらに別の例として、クライアントとレプリカの間の信頼できない通信チャネルもまた同様の問題が生じる。
【００９２】
［インフォームドバックオフ］
〈インフォームドバックオフ〉は、再起動されなかった他のレプリカに過負荷をかけることなく、再起動されたレプリカの状態を再構築するために利用可能なメカニズムである。要求があると、レプリカは、予想待機時間Ｔｗを予測し、それをクライアントに伝達する。予想待機時間は、次の再試行、すなわち要求再送の前に、その時間だけ待機するようにクライアントに通知する。例えば、Ｔｗの経験的計算式は、Ｔｗ＝ＴＣＳ×（Ｐ＋１／２）である。ここで、Ｐはキュー内のクライアントの位置であり、ＴＣＳは、任意の２つの連続する解放オペレーションの間の時間間隔についてレプリカによって観測される平均のＣＳ継続時間である。式中の１／２は、レプリカの現在のオーナを考慮に入れるために用いられている。一実施態様では、Ｔｗは、再試行の受信ごとに更新される。
【００９３】
インフォームドバックオフメカニズムの使用は、クライアントとレプリカの「正常な」オペレーションを妨げないように構成されることも可能である。例えば、レプリカがクラッシュしていないと仮定する。クライアントが、予定された再試行の前に応答を受信すれば、最小限の追加資源がそのクライアントによって利用される。さらに、クライアントが再試行、すなわち要求再送をしない場合、通知されるＴｗは正確でない可能性がある。そのような場合、クライアントは、再試行のためにＴｗを更新してもよい。そこで、レプリカが実際にリセットすれば、キューは、もとの順序と類似の順序で再構成される。
【００９４】
［例示的なコンピューティングデバイス］
本明細書に記載される種々のコンポーネントおよび機能は、いくつかのコンピュータを用いて実施される。図７は、参照番号７０２で示すコンピュータを含む、コンピュータ環境７００の典型例のコンポーネントを示している。コンピュータ７０２は、図１の複数のクライアント１０２（ａ）および複数のコンピューティングデバイス１０４（１）〜１０４（Ｂ）と同一であっても異なっていてもよい。図７に示すコンポーネントは単なる例であり、本発明の機能の範囲に関するいかなる限定を示唆することも意図していない。本発明は、必ずしも、図７に示す特徴に依存しない。
【００９５】
一般的に、さまざまな汎用または専用のコンピューティングシステム構成が使用可能である。本発明とともに使用するのに好適であり得る周知のコンピューティングシステム、環境、および／または構成の例としては、以下のものに限定されないが、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルド型またはラップトップ型デバイス、マルチプロセッサシステム、マイクロプロセッサ方式のシステム、セットトップボックス、プログラム可能な消費者電子機器、ネットワークＰＣ、ネットワーク対応デバイス、ミニコンピュータ、メインフレームコンピュータ、そして、上記のシステムまたはデバイスのいずれかを含む分散コンピューティング環境等がある。
【００９６】
コンピュータの機能は、多くの場合、コンピュータによって実行されるソフトウェアコンポーネントのようなコンピュータ実行可能命令によって具現化される。一般的に、ソフトウェアコンポーネントは、特定のタスクを実行し、または特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造等を含む。タスクは、通信ネットワークを通じてリンクされたリモート処理デバイスによって実行されてもよい。分散コンピューティング環境では、ソフトウェアコンポーネントは、図１および図６に関して前述したように、ローカルおよびリモートの両方のコンピュータ記憶媒体に配置されてもよい。
【００９７】
命令および／またはソフトウェアコンポーネントは、コンピュータの一部であるか、またはコンピュータによって読み取り可能な種々のコンピュータ可読媒体に、さまざまな時に格納される。通常、プログラムは、例えばフロッピー（登録商標）ディスク、ＣＤ−ＲＯＭ、ＤＶＤ、または変調信号のような何らかの形態の通信媒体で配布される。そこから、プログラムはコンピュータの二次メモリにインストールまたはロードされる。実行時に、プログラムはコンピュータの一次電子メモリに少なくとも部分的にロードされる。
【００９８】
説明の目的上、本明細書では、オペレーティングシステムのようなプログラムおよびその他の実行可能プログラムコンポーネントは、個別のブロックとして示される。ただし、このようなプログラムおよびコンポーネントは、種々の時にコンピュータのさまざまな記憶コンポーネントに存在し、コンピュータのデータプロセッサ（複数可）によって実行されると認められる。
【００９９】
図７を参照すると、コンピュータ７０２のコンポーネントとしては、処理ユニット７０４、システムメモリ７０６、およびシステムメモリを含む種々のシステムコンポーネントを処理ユニット７０４に結合するシステムバス７０８が挙げられるが、これらには限定されない。システムバス７０８は、さまざまなバスアーキテクチャのいずれかを使用するメモリバスまたはメモリコントローラ、周辺バス、およびローカルバスを含む、いくつかのタイプのバス構造のいずれでもよい。
【０１００】
コンピュータ７０２は通常、さまざまなコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータ７０２がアクセスすることができるいかなる利用可能な媒体であってもよく、揮発性および不揮発性媒体、リムーバブルおよび非リムーバブル媒体の両方がある。例として、限定ではないが、コンピュータ可読媒体としては、コンピュータ記憶媒体および通信媒体が挙げられる。「コンピュータ記憶媒体」としては、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータのような情報の記憶のための任意の方法または技術で実現された揮発性および不揮発性、リムーバブルおよび非リムーバブル媒体がある。コンピュータ記憶媒体としては、以下のものに限定されないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ等のメモリ技術、ＣＤ−ＲＯＭ、ディジタルビデオディスク（ＤＶＤ）等の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ等の磁気記憶デバイス、または所望の情報を記憶するために使用可能でありコンピュータ７０２によりアクセス可能な任意の他の媒体がある。通信媒体は通常、キャリア波等の変調データ信号または他のトランスポートメカニズムでコンピュータ可読命令、データ構造、プログラムモジュールまたは他のデータを具現化し、いかなる情報配信媒体も含む。「変調データ信号」という用語は、信号中に情報を符号化するように１つまたは複数の信号の特性が設定または変更された信号を意味する。例として、限定ではないが、通信媒体としては、有線ネットワークまたは直接有線コネクションのような有線媒体、および音響、ＲＦ、赤外線等の無線媒体のような無線媒体がある。上記のいずれかの組合せもまた、コンピュータ可読媒体の範囲内に含まれるべきである。
【０１０１】
システムメモリ７０６は、読み出し専用メモリ（ＲＯＭ）７１０およびランダムアクセスメモリ（ＲＡＭ）７１２のような揮発性および／または不揮発性メモリの形態のコンピュータ記憶媒体を含む。起動中等にコンピュータ７０２内の要素間で情報を転送するのに役立つ基本ルーチンを含む基本入出力システム７１４（ＢＩＯＳ）が通常ＲＯＭ７１０に記憶される。ＲＡＭ７１２は通常、処理ユニット７０４から直ちにアクセス可能な、および／または処理ユニット７０４が現在作用しているデータおよび／またはソフトウェアコンポーネントを含む。例として、限定ではないが、図７は、オペレーティングシステム７１６、アプリケーション７１８、ソフトウェアコンポーネント７２０、およびプログラムデータ７２２を示している。
【０１０２】
また、コンピュータ７０２は、他のリムーバブル／非リムーバブル、揮発性／不揮発性のコンピュータ記憶媒体を含んでもよい。単なる例として、図７は、非リムーバブル不揮発性磁気媒体の読み書きを行うハードディスクドライブ７２４、リムーバブル不揮発性磁気ディスク７２８の読み書きを行う磁気ディスクドライブ７２６、およびＣＤ−ＲＯＭ等の光媒体のようなリムーバブル不揮発性光ディスク７３２の読み書きを行う光ディスクドライブ７３０を示している。例示的オペレーティング環境で使用可能な他のリムーバブル／非リムーバブル、揮発性／不揮発性のコンピュータ記憶媒体としては、以下のものに限定されないが、磁気テープカセット、フラッシュメモリカード、ディジタル多用途ディスク、ディジタルビデオテープ、固体ＲＡＭ、固体ＲＯＭ等がある。ハードディスクドライブ７２４は通常、データメディアインタフェース７３４のような非リムーバブルメモリインタフェースを通じてシステムバス７０８に接続され、磁気ディスクドライブ７２６および光ディスクドライブ７３０は通常、リムーバブルメモリインタフェースによりシステムバス７０８に接続される。
【０１０３】
前述し図７に示したドライブおよびそれらに関連するコンピュータ記憶媒体は、コンピュータ７０２のためのコンピュータ可読命令、データ構造、ソフトウェアコンポーネント、および他のデータの記憶を行う。例えば図７において、ハードディスクドライブ７２４は、オペレーティングシステム７１６′、アプリケーション７１８′、ソフトウェアコンポーネント７２０′、およびプログラムデータ７２２′を記憶するように示されている。なお、これらのコンポーネントは、オペレーティングシステム７１６、アプリケーション７１８、ソフトウェアコンポーネント７２０、およびプログラムデータ７２２と同じでも異なってもよいことに留意されたい。オペレーティングシステム７１６′、アプリケーション７１８′、ソフトウェアコンポーネント７２０′、およびプログラムデータ７２２′は、それらが少なくとも別のコピーであることを示すためにここでは異なる番号が与えられている。ユーザは、キーボード７３６、およびマウス、トラックボール、またはタッチパッドと一般的に呼ばれるポインティングデバイス（図示せず）のような入力デバイスを通じてコンピュータ７０２にコマンドおよび情報を入力することができる。他の入力デバイスとしては、ソースデバイス（ストリーミングデータを提供するマイクロフォン７４０やカメラ７３８等）、ジョイスティック、ゲームパッド、サテライトディッシュ、スキャナ等が挙げられる。これらおよび他の入力デバイスは、システムバスに結合した入出力（Ｉ／Ｏ）インタフェース７４２を通じて処理ユニット７０２に接続されることが多いが、パラレルポート、ゲームポート、またはユニバーサルシリアルバス（ＵＳＢ）等の他のインタフェースおよびバス構造により接続されてもよい。モニタ７４４または他のタイプのディスプレイデバイスもまた、ビデオアダプタ７４６のようなインタフェース経由でシステムバス７０８に接続される。モニタ７４４に加えて、コンピュータは、他のレンダリングデバイス（例えばスピーカ）や１つまたは複数のプリンタを含んでもよく、これらはＩ／Ｏインタフェース７４２を通じて接続され得る。
【０１０４】
コンピュータは、リモートデバイス７５０のような１つまたは複数のリモートコンピュータへの論理コネクションを用いたネットワーク環境で動作し得る。リモートデバイス７５０は、パーソナルコンピュータ、ネットワーク対応デバイス、サーバ、ルータ、ネットワークＰＣ、ピアデバイスまたは他の一般的なネットワークノードであってよく、通常、コンピュータ７０２に関して前述した要素の多くまたはすべてを含む。図７に示す論理コネクションは、ローカルエリアネットワーク（ＬＡＮ）７５２および広域ネットワーク（ＷＡＮ）７５４を含む。図７に示すＷＡＮ７５４はインターネットであるが、ＷＡＮ７５４は他のネットワークを含んでもよい。このようなネットワーキング環境は、オフィス、企業規模のコンピュータネットワーク、イントラネット等で一般的である。
【０１０５】
ＬＡＮネットワーキング環境で使用される場合、コンピュータ７０２はネットワークインタフェースすなわちアダプタ７５６を通じてＬＡＮ７５２に接続される。ＷＡＮネットワーキング環境で使用される場合、コンピュータ７０２は通常、インターネット７５４を通じて通信を確立するためのモデム７５８等の手段を含む。モデム７５８は、内蔵でも外付けでもよいが、Ｉ／Ｏインタフェース７４２、または他の適当なメカニズムを通じてシステムバス７０８に接続され得る。ネットワーク環境では、コンピュータ７０２に関して図示したプログラムモジュールまたはその部分は、リモートメデバイス７５０に記憶されてもよい。例として、限定ではないが、図７は、リモートソフトウェアコンポーネント７６０がリモートデバイス７５０上に存在するように示している。図示したネットワークコネクションは例示であり、コンピュータ間に通信リンクを確立する他の手段を使用してもよいことが理解されるであろう。
【０１０６】
［結論］
ピアツーピアネットワークにおけるシステムダイナミズムを扱うために、論理的レプリカおよびコーラムコンセンサスを利用し得る相互排除技法について説明した。本明細書に記載の技法によって提供されるクライアントとレプリカの間の準一貫性および協調を利用して、ネットワーク遅延変動およびコンテンションを回避することができる。また、相互排除技法は、インフォームドバックオフを利用する等によって、障害にも対処する。
【０１０７】
以上、本発明は、構造的な特徴および／または方法上の行為に固有の用語で説明されているが、添付の特許請求の範囲に規定される本発明は、必ずしも上記の具体的な特徴または行為に限定されないことが理解されるべきである。むしろ、これら具体的な特徴および行為は、特許請求の範囲に記載の発明を実施するための例示的形態として開示されているものである。
【図面の簡単な説明】
【０１０８】
【図１】ピアツーピアネットワークを提供するように構成された環境を示す例示的実施態様の図である。
【図２】図１のクライアントおよびレプリカのアーキテクチャをさらに詳細に示すシステムの例示的実施態様の図である。
【図３】図１のクライアントがピアツーピアネットワークにおける複数のピアのうちの１つまたは複数によって提供される資源へのアクセスを要求する例示的実施態様における手続きを示す流れ図である。
【図４】複数の資源のうちの特定の１つの利用が許可されるかどうかをクライアントが判断する例示的実施態様における手続きを示す流れ図である。
【図５】図４の移譲オペレーションの実行を示す例示的実施態様における手続きを示す流れ図である。
【図６】図４および図５に関連して説明される、図２のクライアントおよびレプリカにより実行される相互排除プロトコルの一実施態様のアーキテクチャを示すブロック図である。
【図７】例示的なコンピューティングデバイスの図である。
【符号の説明】
【０１０９】
１００  環境
１０２  クライアント
１０４  コンピューティングデバイス
１０６  ネットワーク
１０８  分散ハッシュテーブル（ＤＨＴ）
１１０  バケット
１１２  論理的レプリカ
２０２  クライアントＩＤ
２０４  応答配列
２０６  応答
２０８  オーナ
２１０  タイムスタンプ
２１２  オーナシップフィールド
２１４  キュー
２１６  要求
２１８  タイムスタンプ
３０４  要求
３１０〜３１６  応答
６０２  request（要求）オペレーション
６０４  SendRequestオペレーション
６０６  OnRequestオペレーション
６０８  insert（挿入）オペレーション
６１０  キューオペレーション
６１２  SendResponseオペレーション
６１４  OnResponseオペレーション
６１６  SendYieldオペレーション
６１８  OnYieldオペレーション
６２０  QueueFrontオペレーション
６２２  remove（移動）オペレーション
６２４  release（解除）オペレーション
６２８  OnReleaseオペレーション
６３０  QueueEmptyオペレーション
６３２  QueueContainsオペレーション
７００  コンピュータ環境
７０２  コンピュータ
７０４  処理ユニット
７０６  システムメモリ
７０８  システムバス
７１０  読み出し専用メモリ（ＲＯＭ）
７１２  ランダムアクセスメモリ（ＲＡＭ）
７１４  基本入出力システム（ＢＩＯＳ）
７１６，７１６′  オペレーティングシステム
７１８，７１８′  アプリケーション
７２０，７２０′  ソフトウェアコンポーネント
７２２，７２２′  プログラムデータ
７２４  ハードディスクドライブ
７２６  磁気ディスクドライブ
７２８  リムーバブル不揮発性磁気ディスク
７３０  光ディスクドライブ
７３２  リムーバブル不揮発性光ディスク
７３４  データメディアインタフェース
７３６  キーボード
７３８  カメラ
７４０  マイクロフォン
７４２  入出力（Ｉ／Ｏ）インタフェース
７４４  モニタ
７４６  ビデオアダプタ
７５０  リモートデバイス
７５２  ローカルエリアネットワーク（ＬＡＮ）
７５４  広域ネットワーク（ＷＡＮ）
７５６  ネットワークインタフェース
７５８  モデム
７６０  リモートソフトウェアコンポーネント
【図１】
0004837929.tif 000004
【図２】
0004837929.tif 000005
【図３】
0004837929.tif 000006
【図４】
0004837929.tif 000007
【図５】
0004837929.tif 000008
【図６】
0004837929.tif 000009
【図７】
0004837929.tif 000010