(57)【特許請求の範囲】
【請求項１】
誘導者ノードが新入者ノードを分散型コンピューターシステムに導入するためにコンピューターで実施される方法であって、
前記分散型コンピューターシステムへの前記新入者ノードの導入を完了するために必要な情報を含む導入タスクを生成すること、
コンピューターネットワークを介して、前記新入者ノードに前記導入タスクを送ること、
前記新入者ノードを識別する情報、及び、前記新入者ノードとの通信を可能にするに足る情報を含むメンバーシップ要求を、前記新入者ノードから前記ネットワークを介して受け取ること、
誘導者ノード及び新入者ノードの役割を定義するブートストラップメンバーシップを生成し、前記ブートストラップメンバーシップを配置し、前記新入者ノードに対してブートストラップメンバーシップレディメッセージを送ること、
生成された前記ブートストラップメンバーシップを参照する決定論的な状態マシンを生成すること、及び
前記新入者ノードが対応するブートストラップメンバーシップを生成したというアクナレッジメントを受信すること
を備える方法。
【請求項２】
前記導入タスクの生成は、前記導入タスクが少なくとも１つの導入チケットを含むように実行される
請求項１に記載のコンピューターで実施される方法。
【請求項３】
前記導入チケットは、暗号化されたファイルとして構成される
請求項２に記載のコンピューターで実施される方法。
【請求項４】
前記導入タスクは、少なくとも１つの導入後タスクを含む
請求項２に記載のコンピューターで実施される方法。
【請求項５】
前記新入者ノードから受信された前記メンバーシップ要求を認証すること、及び
前記メンバーシップ要求が無効であったら、前記導入を終了させること
をさらに備える請求項１に記載のコンピューターで実施される方法。
【請求項６】
前記ブートストラップメンバーシップはさらに、
決定論的に生成されたメンバーシップ識別、及び
前記誘導者ノード及び前記新入者ノードの役割を含む
請求項１に記載のコンピューターで実施される方法。
【請求項７】
前記新入者ノードが気付くべき少なくとも１つのノード及びロケーションを前記新入者ノードに対して送ること
をさらに備える請求項１に記載のコンピューターで実施される方法。
【請求項８】
前記導入タスクは、少なくとも前記誘導者ノードの再起動の間持続する
請求項１に記載のコンピューターで実施される方法。
【請求項９】
メモリと、
プロセッサとを備える計算装置であって、
前記プロセッサは、分散型コンピューターシステムに新入者ノードを導入するよう構成された誘導者ノードとして前記計算装置を実行するために前記メモリ内に記憶される命令を実行するよう構成され、
記憶される前記命令は、前記プロセッサに
前記分散型コンピューターシステムへの前記新入者ノードの導入を完了するために必要な情報を含む導入タスクを生成すること、
コンピューターネットワークを介して、前記新入者ノードに前記導入タスクを送ること、
前記新入者ノードを識別する情報、及び、前記新入者ノードとの通信を可能にするに足る情報を含むメンバーシップ要求を、前記新入者ノードから前記ネットワークを介して受け取ること、
誘導者ノード及び新入者ノードの役割を定義するブートストラップメンバーシップを生成し、前記ブートストラップメンバーシップを配置し、前記新入者ノードに対してブートストラップメンバーシップレディメッセージを送ること、
生成された前記ブートストラップメンバーシップを参照する決定論的な状態マシンを生成すること、及び
前記新入者ノードが対応するブートストラップメンバーシップを生成したというアクナレッジメントを受信すること
を実行させるよう構成される計算装置。
【請求項１０】
分散型コンピューターシステムに新入者ノードを導入するよう構成された誘導者ノードとして計算装置を構成するデータ及び命令を記憶する有形のデータ記憶メディアであって、
記憶される前記データ及び命令は、前記計算装置に、
前記分散型コンピューターシステムへの前記新入者ノードの導入を完了するために必要な情報を含む導入タスクを生成すること、
コンピューターネットワークを介して、前記新入者ノードに前記導入タスクを送ること、
前記新入者ノードを識別する情報、及び、前記新入者ノードとの通信を可能にするに足る情報を含むメンバーシップ要求を、前記新入者ノードから前記ネットワークを介して受け取ること、
誘導者ノード及び新入者ノードの役割を定義するブートストラップメンバーシップを生成し、前記ブートストラップメンバーシップを配置し、前記新入者ノードに対してブートストラップメンバーシップレディメッセージを送ること、
生成された前記ブートストラップメンバーシップを参照する決定論的な状態マシンを生成すること、及び
前記新入者ノードが対応するブートストラップメンバーシップを生成したというアクナレッジメントを受信すること
を実行させるよう構成されるデータ記憶メディア。
【請求項１１】
新入者ノードが誘導者ノードによって分散型コンピューターシステム内に導入されるためにコンピューターで実施される方法であって、
導入チケットを少なくとも含む導入タスクの受領を待機すること、
コンピューターネットワークを介して前記導入タスク及び前記導入チケットを受け取り、前記導入チケット内の情報を用いてアプリケーションプラットホームを設定すること、
前記誘導者ノードに対して前記新入者ノードが導入を開始していることを通知するように構成されたブートストラップメンバーシップ要求を、前記誘導者ノードに対し、前記コンピューターネットワークを介して送ること、
前記誘導者ノードからブートストラップメンバーシップレディメッセージを受け取り、ブートストラップメンバーシップを生成及び配置し、前記ブートストラップメンバーシップを参照する決定論的な状態マシンを生成するとともに、前記誘導者ノードに対して前記ブートストラップメンバーシップを生成したというアクナレッジメントを知らせること
を備える方法。
【請求項１２】
送信することは、受領された前記導入タスクの識別、及び、前記新入者ノードとの通信を可能にする情報を含む前記ブートストラップメンバーシップ要求を用いて行われる
請求項１１に記載のコンピューターで実施される方法。
【請求項１３】
前記決定論的な状態マシンが、前記誘導者ノードから、前記新入者ノードが気付くべきロケーション及びノードのリストを受領すること
をさらに備える請求項１１に記載のコンピューターで実施される方法。
【請求項１４】
前記決定論的な状態マシンが、前記誘導者ノードから、前記新入者ノードが気付くべきロケーション及びノードのリストを含む提案を受領すること
をさらに備える請求項１１に記載のコンピューターで実施される方法。
【請求項１５】
受領された前記導入チケットを認証すること
をさらに備える請求項１１に記載のコンピューターで実施される方法。
【請求項１６】
前記ブートストラップメンバーシップ要求は、前記導入タスクの識別、ノード、ロケーション、前記新入者ノードのホストネーム及びポートのうちの少なくとも１つを含む
請求項１１に記載のコンピューターで実施される方法。
【請求項１７】
前記ブートストラップメンバーシップを生成することは、決定論的に生成されたメンバーシップ識別と、前記誘導者ノード及び前記新入者ノードの役割とを用いて前記ブートストラップメンバーシップを生成することを含む
請求項１１に記載のコンピューターで実施される方法。
【請求項１８】
受領された前記導入タスク内に特定されるタスクを実行すること
をさらに備える請求項１１に記載のコンピューターで実施される方法。
【請求項１９】
メモリと、
プロセッサとを備える計算装置であって、
前記プロセッサは、誘導者ノードによって分散型コンピューターシステム内に導入される新入者ノードとして前記計算装置を構成するために前記メモリ内に記憶される命令を実行するよう構成され、
記憶される前記命令は、前記プロセッサに
導入チケットを含む導入タスクの受領を待機すること、
コンピューターネットワークを介して前記導入タスク及び前記導入チケットを受け取り、前記導入チケット内の情報を用いてアプリケーションプラットホームを設定すること、
前記誘導者ノードに対して前記新入者ノードが導入を開始していることを通知するように構成されたブートストラップメンバーシップ要求を、前記誘導者ノードに対し、前記コンピューターネットワークを介して送ること、
前記誘導者ノードからブートストラップメンバーシップレディメッセージを受け取り、ブートストラップメンバーシップを生成及び配置し、前記ブートストラップメンバーシップを参照する決定論的な状態マシンを生成するとともに、前記誘導者ノードに対して前記ブートストラップメンバーシップを生成したというアクナレッジメントを知らせること
を実行させるよう構成される計算装置。
【請求項２０】
誘導者ノードによって分散型コンピューターシステム内に導入される新入者ノードとして計算装置を構成するデータ及び命令を記憶する有形のデータ記憶メディアであって、
記憶される前記命令は、前記計算装置に、
導入チケットを含む導入タスクの受領を待機すること、
コンピューターネットワークを介して前記導入タスク及び前記導入チケットを受け取り、前記導入チケット内の情報を用いてアプリケーションプラットホームを設定すること、
前記誘導者ノードに対して前記新入者ノードが導入を開始していることを通知するように構成されたブートストラップメンバーシップ要求を、前記誘導者ノードに対し、前記コンピューターネットワークを介して送ること、
前記誘導者ノードからブートストラップメンバーシップレディメッセージを受け取り、ブートストラップメンバーシップを生成及び配置し、前記ブートストラップメンバーシップを参照する決定論的な状態マシンを生成するとともに、前記誘導者ノードに対して前記ブートストラップメンバーシップを生成したというアクナレッジメントを知らせること
を実行させるよう構成されるデータ記憶メディア。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、２０１２年１２月２８日に出願された米国仮出願Ｎｏ．６１／７４６，８６７及び２０１３年３月１５日に出願された米国出願Ｎｏ．１３／８３５，８８８の利益を主張する。
【背景技術】
【０００２】
共同プロジェクト、それはしばしばグローバルに分離した複数のリソースの間で並列に進められるもの（すなわち、マルチサイト共同プロジェクト）であるが、は様々な種類のプロジェクトで当たり前のこととなっている。そのようなプロジェクトの例には、限定されるものではないが、ソフトウェアの開発、ジェット旅客機の設計、自動車の設計が含まれる。人的資源利用の最適化及びグローバル資源のスキルセットの活用を通じてプロジェクトのタイムラインを加速するために分散されたリソースに依存することは、有利な結果を提供するものであると証明されてきた。
【０００３】
マルチサイト共同プロジェクトを進める際に用いられる分散型コンピューターソリューションを、ここでは分散型マルチサイト共同コンピューターソリューションと称することにする。しかしながら、分散型マルチサイト共同コンピューターソリューションは、分散型コンピューターソリューションの一例にすぎない。ひとつの例では、分散型コンピューターソリューションには、自動車を操作するコンピューターのネットワークが含まれる。他の例では、分散型コンピューターソリューションには、１つの地理的なロケーション（データセンター）におけるコンピューターのネットワークが含まれる。さらに他の例では、分散型コンピューターソリューションは、１つのルータに接続された複数のコンピューターである（すなわち、サブネット）。
【０００４】
従来から分散型コンピューターソリューションは存在しているものの、それらは、自身の有効性、信頼性、有用性、拡張性、透明性、及び／又は、セキュリティに悪影響を与える限定なしではいられない。特に、従来型の分散型マルチサイト共同コンピューターソリューションについては、グローバルに分散した開発基地からの仕事をリアルタイムかつフォールトトレラントに同期させる能力に限界がある。この限界は、ソフトウェアの開発及び納入手続において、しばしば遅れを引き起こしかつリスクを増大させる変更を余儀なくさせる。したがって、従来型の分散型コンピューターソリューションを利用して共同プロジェクトを実行することによって実現されるはずのコスト削減及び生産性向上は、完全には実現されない。
【０００５】
従来型の分散型マルチサイト共同コンピューターソリューションは、望ましくない形で、ユーザに開発手順の変更を強いる。例えば、リアルタイムな情報管理能力に関連する有利な機能を欠く従来型の分散型マルチサイト共同コンピューターソリューションは、ローカルとリモートのコンカレント・バージョンズ・システム（ＣＶＳ）リポジトリが任意の時点で同期状態にあることを保証できないという根本的な問題を有する。これは、異なるサイトの開発者が、気付くことなくお互いの仕事を上書きし、また衝突させる可能性が高いことを意味する。そのような上書きや衝突の危険を防ぐため、従来型の分散型マルチサイト共同コンピューターソリューションは、過度の及び／又は間違いを起こしやすいソースコードの分岐や手動でのファイルの結合を、開発プロセスの一部として必要とする。このことは、実際上、タイムゾーンに基づいて開発事業を分割することを強制し、分散された開発チーム間の協調を、不可能ではないとしても非常に困難なものにする。
【０００６】
複製状態マシンは、分散型コンピューターソリューションを好適に実現したものである。また、分散型コンピューターソリューションのいくつかの可能な例の中のひとつは、複製情報リポジトリである。したがって、複製状態マシンは、より具体的には、複製情報リポジトリを好適に実現したものである。また、複製情報リポジトリのいくつかの可能なアプリケーションの中のひとつは、分散型マルチサイト共同コンピューターソリューションである。したがって、複製状態マシンは、より具体的には、分散型マルチサイト共同コンピューターソリューションを好適に実現したものである。
【０００７】
したがって、分散型コンピューターソリューションは、しばしば複製状態マシン又は複製情報リポジトリ、或いはこれらの両方に依存する。複製状態マシン及び複製情報リポジトリ又はそのいずれかは、コンカレントな情報の生成、操作、管理を提供し、そしてそれゆえ、ほとんどの分散型コンピューターソリューションの重要な一面である。しかしながら、状態マシンの複製を促進するとともに情報リポジトリの複製を促進する既知の手法には、欠陥がないわけではない。
【０００８】
状態マシンの複製を促進する従来の実装は、その有効性を制限する１つ以上の欠陥を有している。そのような欠陥のひとつは、合意プロトコルにおいて提案側に繰り返しプリエンプトが発生する傾向があるということであり、これは拡張性に悪影響を及ぼす。そのような欠陥の他のひとつは、ウイークリーダーオプティマイゼーション(weak leader optimization)の実行がリーダーの選挙を必要とすることであり、このことは、そのような最適化が複雑さ、スピード、拡張性に悪影響を及ぼす原因となり、さらに、同意ごとにひとつ以上のメッセージを必要とする（例えば、３つの代わりに４つ）ことであり、このことは、スピード及び拡張性に悪影響を及ぼす。そのような欠陥の他のひとつは、合意が順番に到達されなければならないということであり、これはスピードと拡張性に悪影響を及ぼす。そのような欠陥の他のひとつは、固定ストレージの再利用には限界があるということであり、もしこの欠陥が少しでも存在するならば、これは配置に大変な負担を課すことになる。なぜならば、そのような配置のための記憶装置のニーズは、継続的、潜在的、かつ限度なく成長するであろうからである。そのような欠陥の他のひとつは、大きな提案と多数の小さな提案の効果的なハンドリングに限界があるということであり、もしこの欠陥が少しでも存在するならば、拡張性に悪影響を及ぼす。そのような欠陥の他のひとつは、状態マシンの複製を促進するには比較的多数のメッセージが通信されなければならないことであり、これは拡張性と広域ネットワークの互換性に悪影響を及ぼす。他の限界は、通信メッセージの遅延が拡張性に悪影響を及ぼすということである。そのような欠陥の他のひとつは、複製状態マシンにおいて参加者を動的に変更する（例えば、必要に応じて加入及び除外する）ことによるアドレッシングの失敗シナリオが、複雑さ及び拡張性に悪影響を及ぼすということである。
【０００９】
情報リポジトリの複製を促進する従来の実装は、その有効性を制限する１つ以上の欠陥を有している。そのような欠陥のひとつは、いくつかの従来型のマルチサイト共同コンピューターソリューションが、集中的に調整された情報リポジトリの複製を促進するために単一の中央調整者を必要とすることである。中央調整者は、情報リポジトリに対するすべての更新が単一の中央調整者経由で届けられなければならなくなることから、望ましくない形で、拡張性に悪影響を及ぼす。さらに、そのような実装は、単一の中央調整者の障害によって情報リポジトリの任意の複製の更新が停止してしまうことから、高い有用性を有しない。そのような欠陥の他のひとつは、ログの再生に依存する情報リポジトリの複製の実行においては、情報リポジトリの複製が能動受動(active-passive)な方法で促進されるということである。したがって、どんなときでも１つの複製のみが更新され得る。そのため、他の複製は、アイドル状態となるか、又は、例えばデータマイニングアプリケーションのようなリードオンリーのアプリケーションを提供することしかできないので、リソースの利用は貧弱となる。そのような欠陥の他のひとつは、実装が、競合解決発見的問題解決法(conflict-resolution heuristics)及び／又はアプリケーション介在メカニズム(application-intervention mechanisms)に裏打ちされた弱く首尾一貫した複製(weakly consistent replication)に依存するときに生ずる。このタイプの情報リポジトリは、情報リポジトリの複製に対して競合する更新を許容し、情報リポジトリを利用するアプリケーションに、これらの競合の解決を求める。したがって、そのような実装は、アプリケーションに対する透明性に悪影響を与える。
【００１０】
情報リポジトリの複製を促進する従来の実装がそれらの有効性を制限する１つ以上の欠陥を有することをさらに参照すると、ディスクミラーリングソリューションに依存する実装は１つ以上の欠陥を有することが知られている。このタイプの実装は、能動受動(active-passive)な実装である。したがって、そのような欠陥のひとつは、どのようなときでも１つの複製のみがアプリケーションによって使用され得るということである。そのため、他の複製（すなわち、受動的なミラー）は、受動的なミラーとしての役割を担う間、読み出しも書き込みも不可能となるので、リソースの利用は貧弱となる。この特殊な実装の欠陥の他のひとつは、複製方法がアプリケーションのトランザクション限界を関知しないということである。そのため、失敗の時点で、そのミラーはトランザクションの部分的な結果を有しており、それゆえ利用できなくなるかもしれない。そのような欠陥の他のひとつは、複製方法が、情報に対する変更が生じたノードから他のすべてのノードに対して、その変更を伝播させることである。情報に対する変更のサイズはしばしば、その変更の原因となったコマンドのサイズよりも相当程度大きいので、そのような実装は、不必要に大きな帯域を必要とする。そのような欠陥の他のひとつは、もしマスターレポジトリ内の情報が何らかの理由で破損したとすると、その破損がそのリポジトリのすべての複製に伝播されるということである。そのため、情報リポジトリは、リカバリ不能となるか、又は、古いバックアップコピーからリカバリしなければならないこととなり、したがって更なる情報の喪失を引き起こす。
【００１１】
したがって、従来型の複製状態マシンに関連する欠点を克服する複製状態マシンが有用であり、有利である。より具体的には、そのような複製状態マシンを用いて構築された複製情報リポジトリは、従来型の複製情報リポジトリに比べて優れている。さらにいっそう具体的には、そのような複製状態マシンを用いて構築された複製ＣＶＳリポジトリは、従来型の複製ＣＶＳリポジトリに比べて優れている。
【００１２】
上で説明したような分散型コンピューターソリューションの使用は、それゆえ、物理的に分かれたロケーションや、論理的に分かれたロケーションなどの間で情報を共有する相対的に効果的かつ効率的な手段を提供するという点で、そのような共同プロジェクトの成功への鍵であった。そのようなロケーションのそれぞれに、分散型コンピューターシステムの１つ以上のコンピューターノードがあり得る。共同プロジェクトに参画しようとする新規ノードは、既存のノード群に参加するよう招待される必要があるとともに、そこから見ることができ、かつ、新たに招待されたノードがメッセージを交換すること及び相互に作用することを許されるロケーション及びノードについて知らされる必要がある。
【図面の簡単な説明】
【００１３】
【図１】一実施の形態に基づくマルチサイトコンピューターシステムアーキテクチャ内の要素の機能的な関係を示すブロック図である。
【００１４】
【図２】一実施の形態に基づくマルチサイトコンピューターシステムアーキテクチャを構成する要素の配置を示すハイレベルブロック図である。
【００１５】
【図３】一実施の形態に基づく複製状態マシンの機能的な構成要素を示すブロック図である。
【００１６】
【図４】一実施の形態によるローカルアプリケーションノードによって発行される提案を示すブロック図である。
【００１７】
【図５】図３に示した複製状態マシンのグローバルシーケンサーのエントリ構造を示すブロック図である。
【００１８】
【図６】図３に示した複製状態マシンのローカルシーケンサーのエントリ構造を示すブロック図である。
【００１９】
【図７】一実施の形態に基づくレプリケーターを示すブロック図である。
【００２０】
【図８】一実施の形態に基づくマルチサイトコンピューターシステムアーキテクチャを構成する要素の配置を示す詳細レベルのブロック図である。
【００２１】
【図９】一実施の形態によるノードのグループへのノードの安全かつ認証された導入を実現する装置、方法、及びシステムの一面を示す図である。
【００２２】
【図１０】それとともに実施の形態が実施され得る計算装置のブロック図である。
【発明を実施するための形態】
【００２３】
ここに開示されるのは、各種の分散型コンピューターシステムアーキテクチャ（例えば、分散型マルチサイト共同コンピューターシステムアーキテクチャ）における複製状態マシンの実用的な実装を促進する様々な態様である。当業者は、複製状態マシンの１つ以上の従来の実装を承知しているであろう。そのような状態マシンの従来の実装は、例えば、Ｆ．Ｂ．シュナイダー(F. B. Schneider)によって書かれ、１９９０年１２月にＡＣＭコンピューターサーベイ２２(ACM Computing Surveys 22)において発表された「状態マシンアプローチを用いてフォールトトレラントなサービスを実現すること：チュートリアル(Implementing fault-tolerant services using the state machine approach: A tutorial)」（２９９ページ〜３１９ページ）と題された刊行物の中に開示されている。この刊行物の内容は、本明細書の一部を構成するものとしてここに援用される。本実施の形態は、以下でより詳細に議論されるように、分散型アプリケーションシステムアーキテクチャ内の状態マシンの従来の実装に関して、拡張性、信頼性、可用性、及びフォールトトレランスの側面を高めるものである。
【００２４】
本実施の形態は、各種の分散型コンピューターシステムアーキテクチャ（例えば、分散型マルチサイト共同コンピューターシステムアーキテクチャ）内の複製状態マシンの実用的な実装を提供する。より具体的には、本実施の形態は、分散型コンピューターシステムアーキテクチャにおける複製状態マシン及び／又は複製情報リポジトリの拡張性、信頼性、可用性、及びフォールトトレランスを高める。したがって、本実施の形態は、分散型コンピューターシステムアーキテクチャにおける複製状態マシン及び／又は複製情報リポジトリを実行するための従来のアプローチに関連する１つ以上の欠点を有利に克服する。
【００２５】
一実施の形態では、複製状態マシンは、提案マネージャー、同意マネージャー、衝突／バックオフタイマー、及びストレージリクレーマーを備えることができる。提案マネージャーは、分散型アプリケーションのあるノードによって発行された提案に関して、その提案を実行する必要のある分散型アプリケーションのすべてのノードによってその提案が協調的に実行されるように、その管理を促進する。すべてのノードには、おそらく自分自身も含まれるが、必須ではない。同意マネージャーは、提案に対する同意を促進する。衝突／バックオフタイマーは、提案に対する同意を達成するための試みにおいて、ラウンドのプリエンプトが繰り返されることを排除する。ストレージリクレーマーは、提案の同意及び／又は提案を格納するために利用される固定ストレージを再利用する。
【００２６】
他の実施の形態では、分散型コンピューターシステムアーキテクチャは、ネットワークシステムと、このネットワークシステムを介して相互に接続された複数の分散型コンピューターシステムとを備えることができる。分散型コンピューターシステムのそれぞれは、各々の複製状態マシンと、各々の複製状態マシンに接続された各々のローカルアプリケーションノードとを含むことができる。複数の分散型コンピューターシステムそれぞれの複製状態マシンは、他のすべての分散型コンピューターシステムの分散型アプリケーションノードによる提案の協調的な実行を可能にするために提案の管理を促進し、提案の同意を促進し、提案に対する同意を達成するための試みにおいてラウンドのプリエンプトが繰り返されることを排除し、提案の同意及び提案の少なくとも一方を格納するために利用される固定ストレージを再利用する。
【００２７】
他の実施の形態では、方法は、複数のオペレーションを備える。あるオペレーションは、ローカルアプリケーションノードから受信される提案の合意を促進するために実行され得る。あるオペレーションは、提案に対する同意を達成するための試みにおいてラウンドのプリエンプトが繰り返されることを排除するために実行され得る。あるオペレーションは、提案の同意及び提案の少なくとも一方を格納するために利用される固定ストレージを再利用するために実行され得る。
【００２８】
少なくとも１つの実施の形態では、少なくとも提案の一部分は、分散型のアプリケーションのノードによって起動される情報更新の実行に対応する提案されたステップを含む。提案の発行順序は、提案に対するコンカレントな同意が進められる間、保存され得る。提案の一部は、各情報更新に対応する提案された書き込みステップであり得、提案マネージャーは、それら提案された書き込みステップのそれぞれにローカルな連続番号を割り当て、提案された書き込みステップを実行する分散型アプリケーションのすべてのノードが共通のシーケンスで提案された書き込みステップを実行できるよう、提案された書き込みステップのグローバルに一意なインターリービングを生成する。それぞれ複数の提案中の対応するものに関連付けられた複数のエントリを含むローカルシーケンサーが用意され得、同様に、それぞれローカルシーケンサーのエントリ中の対応するものを参照する複数のエントリを含むグローバルシーケンサーがあり得る。ローカルシーケンサーのエントリのそれぞれは、それに割り当てられた一意なローカル連続番号を有してもよいし、ローカルシーケンサーのエントリのそれぞれは、割り当てられた連続番号に対して順次配列されてもよい。そして、同意マネージャーが提案のうちのひとつの同意を進めた後、同意が進められたその提案に対応するエントリが、グローバルシーケンサー内でそのエントリが位置する位置を決定することに応じて、グローバルシーケンサー内に生成され得る。ストレージリクレーマーは、グローバルシーケンサー内のエントリの位置が決定され、すべてのノードに知れ渡った後、固定提案ストレージから提案のためのレコードを削除することによって、固定ストレージを再利用することができる。衝突／バックオフタイマーは、第１の提案者のためのラウンドのうちの現在のひとつが始まった後、第１の提案者のためのラウンドのうちの次のひとつが起動される前までに経過する時間として計算されたプリエンプト遅延の継続時間だけ待機するオペレーション、及び、第１の提案者のためのラウンドのうちの現在のひとつが始まった後、第２の提案者のためのラウンドのうちの次のひとつが起動される前までに経過する時間として計算された進行中ラウンド遅延の継続時間だけ待機するオペレーション、又はこれらのオペレーションのうちのいずれか一方を実行することにより、プリエンプトが繰り返されることを排除するよう構成され得る。
【００２９】
次に図面を参照すると、図１は、一実施の形態に基づくマルチサイトコンピューターシステムアーキテクチャ（すなわち、ここではマルチサイトコンピューターシステムアーキテクチャ１００と称される）が、ワイドエリアネットワーク（ＷＡＮ）１１０によって相互に接続された複数の分散型アプリケーションシステム１０５を含み得ることを示している。複数の分散型アプリケーションシステム１０５のそれぞれは、複数の分散型アプリケーションノード１１５（例えば、ワークステーション上で走るアプリケーション）、レプリケーター１２０、及びリポジトリレプリカ１２５を含んでもよい。各分散型アプリケーションシステム１０５のレプリケーター１２０は、ＷＡＮ１１０、各々の分散型アプリケーションシステム１０５の分散型アプリケーションノード１１５、及び、各々の分散型アプリケーションシステム１０５のリポジトリレプリカ１２５の間に接続され得る。
【００３０】
一実施の形態では、各リポジトリレプリカ１２５はコンカレント・バージョンズ・システム（ＣＶＳ）のリポジトリである。ＣＶＳは、システムのバージョンを管理する周知のオープンソースコードである。ＣＶＳは、多くの他のシステムをバージョニングするソースコードと同様、複数のＣＶＳクライアント（例えば、分散型アプリケーションノード１１５）が例えば通信制御プロトコル（ＴＣＰ）上のＣＶＳプロトコルを使って接続する中央サーバとして動作するようデザインされている。ＣＶＳサーバは、実行されるとき、クライアントコネクションごとにプロセスを分けて、各クライアントからのＣＶＳリクエストを取り扱う。したがって、レプリケーター１２０とリポジトリレプリカ１２５は、ＣＶＳリポジトリの複数のレプリカを許容する。ＣＶＳ情報リポジトリが一実施の形態に有用な情報リポジトリの一例である一方で、本開示の主題は、他のタイプの情報リポジトリの複製に有用である。データベースやファイルシステムは、そのような他のタイプの情報リポジトリの例である。したがって、実施の形態の有用性及び適用性は、特定のタイプの情報リポジトリに限定されない。
【００３１】
以下で詳しく議論されるように、各レプリケーター１２０は、各々の分散型アプリケーションシステム１０５から他の分散型アプリケーションシステム１０５それぞれのリポジトリレプリカ１２５に情報更新を書き込むように設定されてもよい。各レプリケーター１２０は、ＣＶＳクライアント（すなわち、それぞれの分散型アプリケーションシステム１０５）と既定のＣＶＳサーバ（すなわち、それぞれのリポジトリレプリカ１２５）との間でアプリケーションゲートウェイとして振舞う仲介者であってもよい。各レプリケーター１２０は、すべてのリポジトリレプリカ１２５が互いに同期した状態に留まることを保証するために、他の同等のレプリケーターと協調する。
【００３２】
従来のソリューションとは異なり、マルチサイトコンピューターシステムアーキテクチャ１００は、単一障害点として知られる中央トランザクション調整者に頼らない。マルチサイトコンピューターシステムアーキテクチャ１００は、リアルタイムかつ能動能動(active-active)な複製に向けてユニークなアプローチを提供し、分散型アプリケーションシステムのすべてのＣＶＳリポジトリレプリカに跨って１つの複製等価物、という原則に基づいて動作する。したがって、一実施の形態に基づくと、すべてのリポジトリレプリカは他のすべてのリポジトリレプリカとリアルタイムに同期し、したがって分散型アプリケーションシステムのすべてのノードにいるユーザ（例えば、同じコードベースからの情報に基づいて仕事をするプログラマー）は、常に、同じ情報ベースからの情報に基づいて仕事をしている。
【００３３】
レプリケーター１２０とそれぞれのリポジトリレプリカ１２５の統合を通して、各リポジトリレプリカは、自身のトランザクション調整者（すなわち、各々のレプリケーター１２０）とともにＷＡＮ１１０上でアクティブなノードとなる。各分散型トランザクション調整者は、ローカルな更新を受け入れ、それらをリアルタイムに他のすべてのリポジトリレプリカ１２５に伝える。したがって、マルチサイトコンピューターシステムアーキテクチャ１００内のすべてのユーザは、ロケーションに関わらず、同じレポジトリ情報（すなわち、単一のＣＶＳ情報リポジトリ）に基づいて効率的に仕事をしている。そのためにも、一実施の形態に基づくマルチサイトコンピューターシステムアーキテクチャは、グローバルに分散した開発チームの仕事をリアルタイムに同期する、費用効率が高く、フォールト・トレラントなソフトウェアコンフィグレーション管理（ＳＣＭ）ソリューションである。
【００３４】
ネットワークやサーバの障害が発生したとき、開発者は仕事を続けることができる。変更は、ローカルなレプリケーター１２０のトランザクションジャーナル内に記録される。トランザクションジャーナルは、機能において、データベースのリドゥーログに類似している。接続性が回復したとき、ローカルなレプリケーター１２０は、他の分散型アプリケーションシステム１０５のレプリケーター１２０に接触し、自身を最新の情報とするとともに、ネットワーク又はシステムがダウンしている間にローカルなトランザクションジャーナル内にキャプチャされた変更を適用する。リカバリは、ＣＶＳ管理者の仲介なく、自動的に実行され得る。この自己回復能力は、データの損失がゼロであること、及び、開発時間が失われないことを保証し、障害復旧シナリオにおけるヒューマンエラーのリスクを除去する。
【００３５】
本質的に同じリポジトリ情報に基づいて仕事をすることの利益は、開発が海外へ移転するときに開発手続きを変える必要がないこと、複数のサイトからの仕事が統合されるときに大きなビルドが完了するのを待つ間、遊んでいる必要がないこと、開発上の問題を早期に検出できること、及び、品質保証に割くリソースが小さくなること（例えば、冗長なリソースの利用を減らすこと）を含む。加えて、障害復旧は、統合された自己回復能力が障害回避を提供するので、問題とならない。システムがダウンしたときにも仕事が失われることはない。
【００３６】
上に開示したように、一実施の形態に基づく複製状態マシンの実装は、そのような複製状態マシンの拡張性、信頼性、有用性、及びフォールトトレランスに有利な影響を与える。拡張性、信頼性、有用性、及びフォールトトレランスに有利な影響を与えることにより、本実施の形態は、マルチサイトコンピューターシステムアーキテクチャ内に複製状態マシンを実装するための実用的なアプローチを提供する。一実施の形態にしたがう複製状態マシンの実装では、以下の目的の全部又は一部が満足され得る：複数のコンピューターからなる分散型コンピューターシステムのノードが協調しながらそれらの状態を進化させられるようにすること、コンピューターネットワーク、コンピューター、又はコンピューターリソースの任意の障害や部分的な障害に関わらず、複数のコンピューターからなる分散型システムの整合性が保存されるようにすること、分散型アプリケーションノードからなる信頼性のあるシステムが、控えめな信頼性を有するコンポーネントから生成できるようにすること、同意プロトコルの衝突に関わらず、漸近的に１に近づく時間の関数としての確率で同意プロトコルの終了を保証すること、通常の動作状態の下での同意プロトコルの衝突を撲滅すること、同意プロトコルの効率を改善すること、複製状態マシンのメモリ及びディスクの使用を低減し、抑制すること、複製状態マシンによるネットワークリソースの使用を減らすこと、複製状態マシンによって実現可能なステート遷移のスループットを増大すること、複製状態マシンによって支配される分散型アプリケーションによるメモリ及びディスクリソースのより効率的な管理を可能にすること。
【００３７】
図２に示されるように、一実施の形態に基づくマルチサイトコンピューター機能は、お互いに、かつ、ネットワークシステム２１０を通じてそれぞれのローカルアプリケーションノード２０５と情報のやり取りを行う複数の複製状態マシン２００によって促進される。好ましくは、必須ではないが、各ローカルアプリケーションノード２０５は、分散型アプリケーションのそれであり、時間内の任意の時点において、提案の提案者若しくは提案の受領者として機能することとしてもよい。一実施の形態では、ネットワークシステム２１０は、複製状態マシン２００の間に接続される広域ネットワーク（ＷＡＮ）と、各複製状態マシン２００と各々のローカルアプリケーションノード２０５との間に接続されるローカルエリアネットワーク（ＬＡＮ）とを含み得る。例えば、各複製状態マシン２００と各々のローカルアプリケーションノード２０５は、１つのマルチサイト共同コンピュータープロジェクトのための各々のサイトに位置する。ネットワークシステム２１０のＬＡＮ部分は、ローカル基準（すなわち、各複製状態マシン２００と各々のローカルアプリケーションノード２０５との間）での情報の共有を促進し、ネットワークシステム２１０のＷＡＮ部分は、グローバル基準（すなわち、複製状態マシン２００間）での情報の共有を促進する。ＬＡＮ、ＷＡＮ、又はこれらの両方は、一実施の形態に基づくネットワークシステムの構成要素である一方で、実施の形態はネットワークの特定の形態に限定されない。例えば、一実施の形態に基づくネットワークシステムの他の実施の形態は、自動車に埋め込まれたコンピューターを含むアドホックなネットワークシステム、データセンター内の複数のサブネットを含むネットワークシステム、データセンター内の１つのサブネットを含むネットワークシステムを含む。
【００３８】
図３は、図２に示される各複製状態マシン２００の機能的な構成要素を示すブロック図である。各複製状態マシン２００は、提案マネージャー２２０、固定提案ストレージ２３０、同意マネージャー２４０、同意ストア２４５、分散型ファイル転送プロトコル（ＤＦＴＰ）レイヤー２５０、衝突＆バックオフタイマー２６０、ローカルシーケンサー２７０、グローバルシーケンサー２８０、及びストレージリクレーマー２９０（すなわち、固定ストレージのガベージコレクター）を含み得る。提案マネージャー２２０、固定提案ストレージ２３０、同意マネージャー２４０、同意ストア２４５、分散型ファイル転送プロトコル（ＤＦＴＰ）レイヤー２５０、衝突＆バックオフタイマー２６０、ローカルシーケンサー２７０、グローバルシーケンサー２８０、及びストレージリクレーマー２９０は、それらの間の相互作用を可能にするために、互いの少なくとも一部分で相互に接続されている。以下の議論に見られるように、複製状態マシンの機能的な構成要素のそれぞれは、一実施の形態に基づき、有利な機能性をサポートする。
提案管理
【００３９】
各ローカルアプリケーションノード２０５は、それぞれの複製状態マシン２００に一連の提案を申し込む。それぞれのローカルノード６によって申し込まれた一連の提案は、それぞれのローカルノード２０５のローカルなシーケンスを構成し、このシーケンスは、各々の複製状態マシン２００のローカルシーケンサー２７０内に維持され得る。各複製状態マシン２００の提案マネージャー２２０は、各々の一連の提案を、それぞれに１つずつ設けられるグローバルな提案シーケンス内に加入させる。このグローバルな提案シーケンスは、各々の複製ステートマシン２００のグローバルシーケンサ２８０内に維持され得る。グローバルな提案シーケンスは、次の性質を有する：各ローカルシーケンスの各提案は、それぞれのグローバルシーケンスの中で厳密に１回発生し、ローカルシーケンス内における任意の２つの提案の相対的な順序は、オプションで、それぞれのグローバルシーケンス内で保存され、すべてのローカルアプリケーションノード２０５に関連するグローバルシーケンス（ローカルな順序が保存されても、されなくても）は同一である。
【００４０】
ローカルアプリケーションノード２０５のスレッドが各々の複製状態マシン２００に対して提案（例えば、書き込みステップ）を申し込んだ場合、複製状態マシン２００は、その提案にローカルな連続番号を割り当てる。複製状態マシン２００はその後、その提案のための同意番号を決定する。以下の議論から明らかになるように、同意番号は、グローバルシーケンス内におけるそれぞれの提案の位置を決定する。複製状態マシン２００はその後、自身の固定提案ストレージ２３０内に、その提案の記録を保存する。複製状態マシン２００はその後、ローカルアプリケーションノードのスレッドの制御をローカルアプリケーションノードに返す。したがって、そのスレッドは、同意プロトコルが実行される間、アイドル状態ではなく、ローカルアプリケーションによる使用のために利用可能とされ得る。複製状態マシンはその後、同意マネージャー２４０を介して、その提案のための同意プロトコルを起動する。同意プロトコルが終了すると、複製状態マシン２００は、同意プロトコルによって到達された同意と、提案中に含まれる提案された同意とを比較する。もし、同意マネージャー２４０によって到達された同意が提案のそれと同じであった場合、複製状態マシン２００は、提案の処理を終了する。さもなければ、複製状態マシン２００は、同意マネージャーによって到達された同意が提案のそれと同じになるまで、新しい同意番号を使用して、提案の同意を繰り返し試みる。同意の結論に達すると、各ローカルアプリケーションノード２０５は、提案に対して今同意されたものを、そのグローバルシーケンス内にキューイングする。その後、分散型アプリケーションの各ローカルアプリケーションノード２０５は、グローバルシーケンス内に含まれる提案をキューから取り出し、実行する。
【００４１】
図４は、一実施の形態に基づく提案の実施の形態を示している。この提案を、ここでは提案３００と称する。提案３００は、提案者識別子３２０（すなわち、ローカルアプリケーションノードの識別子）、ローカル連続番号（ＬＳＮ）３３０、グローバル連続番号（ＧＳＮ）３４０、同意番号３５０、及び提案内容３６０を含み得る。好ましくは、必ずしも必要ではないが、各ローカルアプリケーションノードによって発行される提案は、提案３００の構造を有する。
【００４２】
図５は、一実施の形態に基づくローカルシーケンスの実施の形態を示している。このローカルシーケンスを、ここではローカルシーケンス４００と称する。ローカルシーケンス４００は、各々のローカルアプリケーションノード２０５のための提案それぞれの内容を含むことができる。より具体的には、そのようなコンテンツは、提案者識別子、ローカル連続番号（ＬＳＮ）、グローバル連続番号（ＧＳＮ）、同意番号、及び提案内容を含む。好ましくは、必ずしも必要ではないが、各複製状態マシン２００に関連付けられたローカルシーケンスは、ローカルシーケンス４００の構造を有する。
【００４３】
図６は、一実施の形態に基づくグローバルシーケンスの実施の形態を示している。このグローバルシーケンスを、ここではグローバルシーケンス５００と称する。グローバルシーケンスは、一連の提案のためのグローバルな連続番号と、ローカルシーケンスハンドルとを含むことができる。一実施の形態では、ローカルシーケンスハンドルは、それぞれのローカルシーケンス（すなわち、描画されているように、ローカルシーケンス４００）へのポインタであってよい。他の実施の形態では、ローカルシーケンスハンドルは、ローカルシーケンスのテーブルへの鍵であってよい。好ましくは、必ずしも必要ではないが、各複製状態マシン２００に関連付けられたグローバルシーケンスは、グローバルシーケンス５００の構造を有する。
コンカレントな同意
【００４４】
図２及び図３に描画された複製状態マシン２００は、一実施の形態に基づく複製状態マシンであり、提案者が提案を提出した順序をオプションで保存しつつ、一提案者からの複数の提案に対する同意がコンカレントに進行することを許容するコンカレント同意メカニズムを含んでいる。一方、従来の複製状態マシンは、前の提案が同意に達した後、提案の同意を試みる。この従来の複製状態マシンの手法は、従来の複製状態マシンが提案のローカルな順序を保存することを保証する。したがって、もし提案者が初めに提案Ａを提案し、その後に提案Ｂを提案したとすると、従来の複製状態マシンは、提案Ｂと同時又は提案Ｂの前に、提案Ａが同意されることを保証する。しかしながら、一実施の形態に基づくバックオフメカニズムを実行する複製状態マシンとは異なり、この従来の手法は、提案Ａが同意に達するまで提案Ｂの同意が起動されないことから、従来の複製状態マシンの動作を減速させる。
【００４５】
一実施の形態の側面を参照すると、グローバルシーケンス内の各オブジェクト（すなわち、エントリ）は、連続してナンバリングされる。グローバルシーケンス内の１つのオブジェクトに関連付けられる番号は、そのグローバルシーケンス内の他のオブジェクトに対するそれ自身の位置を識別する。例えば、５とナンバリングされたオブジェクトは、６とナンバリングされたオブジェクトに先行し、かつ、４とナンバリングされたオブジェクトに先行される。さらに、グローバルシーケンス内の各オブジェクトは、図５に示されるローカルシーケンスハンドル４００のような、ローカルシーケンスへのハンドルを含む。もし、アプリケーションが提出順（すなわち、ソースから発行された順序）の保存を要求しなければ、グローバルシーケンス内の各オブジェクトは、提案それ自身を含む。このケースでは、提案は、ローカルシーケンスを介して間接的に、というよりむしろ、グローバルシーケンスから直接取得され得る。いくつかの可能な実施の形態のひとつでは、ローカルシーケンスに対するハンドルは、ローカルシーケンスに対するポインタであってよい。他の実施の形態では、ローカルシーケンスに対するハンドルは、ローカルシーケンスのテーブルへの鍵であってよい。
【００４６】
図２及び図３を参照すると、各ローカルシーケンスは、複製状態マシン２００の提案者の一人によって提案された複製状態マシン２００の提案を含む。複製状態マシン２００の各ローカルシーケンスノード２０５は、それぞれの複製状態マシン２００に関連付けられた提案者それぞれのローカルシーケンスを維持する。ローカルシーケンス内のオブジェクトは、連続的にナンバリングされる。ローカルシーケンス内のオブジェクトに関連付けられた番号は、そのローカルシーケンス内の他のオブジェクトに対するそれ自身の位置を識別する。例えば、５とナンバリングされたオブジェクトは、６とナンバリングされたオブジェクトに先行し、かつ、４とナンバリングされたオブジェクトに先行される。ローカルシーケンス内の各オブジェクトは、複製状態マシン２００の提案を含む。
【００４７】
複製状態マシン２００の各ローカルアプリケーションノード２０５では、提案に対して同意に到達した後、その提案がグローバルシーケンスに加えられ得る。提案者の識別（例えば、図４の提案者識別子３２０）は、ローカルシーケンスのテーブルから１つのローカルシーケンスを探すための鍵として用いられ得る。提案のローカル連続番号（ＬＳＮ）は、ローカルシーケンス内における提案の位置を決定する。提案はその後、ローカルシーケンス内の決定された位置に挿入され得る。提案の同意番号（例えば、図４の同意番号３５０）は、グローバルシーケンス内の提案の位置を決定する。ローカルシーケンスに対するハンドルは、グローバルシーケンス内の決定された位置に（すなわち、同意番号に基づいて）挿入され得る。ＧＳＮは、以下の段落で説明するように、提案が消費されるとき、その提案のグローバルシーケンス内の実際の位置を指定することを目的として、その提案に関連付けるためのオプショナルなブックキーピングフィールドである。
【００４８】
一実施の形態では、専用のスレッドがグローバルシーケンスを消費する。そのスレッドは、グローバルシーケンスの次の位置が追加されるまで待機する。次に、そのスレッドは、グローバルシーケンスのその位置にストアされているローカルシーケンスを復元する。その後、そのスレッドは、ローカルシーケンスの次の位置が追加されるまで待機する。そのスレッドはその後、ローカルシーケンスのその位置にストアされている複製状態マシン２００の提案を復元する。当業者は、提案は必ずしも同意番号の順序に基づいて復元されなくてもよいが、すべてのアプリケーションノードで全く同じ順序で復元されることを理解するであろう。この復元順序は、ＧＳＮフィールドにブックキーピングの便のために記録されてもよいが、さもなければ、複製状態マシン２００の動作にとって本質的ではない。例えば、アプリケーションノード（Ａ）がその最初の２つの提案を複製状態マシンに提出すると仮定する（ＬＳＮ１及びＬＳＮ２）。さらに、複製状態マシンが、ＬＳＮ１の同意に到達する前に、期せずしてＬＳＮ２の同意に到達したと仮定する。それゆえ、Ａ：１（アプリケーションノードＡからのＬＳＮ１）の同意番号が２７となり、ＬＳＮ２の同意番号が２６となったとする（すなわち、他のアプリケーションノードから全部で２５の先行する提案の同意があり、Ａ：１とＡ：２の間には他のアプリケーションノードからの提案の同意は介在していなかったとする）。上記の方法を用いると、Ａ：１は位置２６、Ａ：２は位置２７のグローバルシーケンスからそれぞれ復元される。このように、ＧＳＮはＬＳＮの順序を順守するが、同意番号は必ずしもそうする必要はない。この手法は、一実施の形態に基づく複製状態マシンが同時に複数の同意を処理することを可能にする。
【００４９】
スレッドはその後、複製状態マシン２００の提案を適用する。一実施の形態では、提案のアプリケーションは、複製状態マシン２００のアプリケーションによって登録されたコールバック機能を起動することによって達成され得る。
バックオフと衝突の回避
【００５０】
一実施の形態に基づく複製状態マシン（例えば、複製状態マシン２００）は、同意マネージャー２４０の同意プロトコルにおいて提案者のプリエンプトが繰り返されることを回避するためのバックオフメカニズムを含み得る。一方、従来型の複製状態マシンは、第１の提案者によって起動されたラウンドが第２の提案者によって起動されたラウンドに優先するとき、優先された提案者が、先行者のそれよりも高いラウンド番号で直ちに新しいラウンドを起動することを許容する。好ましくないことに、この従来型の手法は、ラウンドのプリエンプトが繰り返されることの土台を作り、同意プロトコルを受け入れがたいほど長時間にわたってバタつかせる。
【００５１】
一実施の形態に基づくバックオフの促進では、ラウンドがプリエンプトされるとき、提案者はプリエンプト遅延の継続時間を計算する。提案者はその後、次のラウンドを起動するための従来のアルゴリズムに従い、次のラウンドを起動する前に、計算した継続時間だけ待機する。
【００５２】
一実施の形態に基づく衝突回避の促進では、第２の提案者によってラウンドが起動されたことを第１の提案者が感知するとき、第１の提案者は進行中ラウンド遅延期間の継続時間を計算する。第１の提案者は、計算した遅延の継続時間が満了するまで、ラウンドを起動することを自制する。
【００５３】
一実施の形態では、与えられる遅延は、ラウンドの連続するプリエンプトとともに指数関数的に増加する。加えて、遅延はランダムに決定されることが好ましい。
【００５４】
与えられる遅延の継続時間を決定するために使うことのできる方法は、いくつか存在する。実行可能な方法のインスピレーションのひとつの源は、ノンスイッチドイーサネットのための搬送波感知多重アクセス/衝突検出（ＣＳＭＡ／ＣＤ）に関する文献である。ＣＳＭＡ／ＣＤプロトコルは、２つのネットワーク装置が同時にデータチャネルを使おうと試みるときに、ネットワーク装置がどのように応答するかを決定するルールのセットである。
【００５５】
いくつかの可能な実施の形態では、計算された遅延の継続時間は、次の方法により決定される。複製状態マシン２００を展開する管理者は、４つの数値を設定する。この実施の形態の描写の目的のために、これらの値はＡ，Ｕ，Ｒ，及びＸと称される。効果的な構成では、値Ｒは０より大きくかつ１より小さく、値Ａは０より大きく、値Ｘは１より大きく、値Ｕは値Ａより大きい。同意プロトコルの実行時間は推定され得る。同意プロトコルの実行時間のいくつかの可能な推定量のひとつは、同意プロトコルの過去の実行時間の移動平均である。この議論の目的のために、この推定された値はＥと称される。値Ｍは、ＡにＵを乗ずることによって得られる値である。２つの値Ａ，Ｅのうちの大きい方が選択される。この議論の目的のために、この選択された値はＦと称される。値Ｃは、ＦにＸを乗ずることによって得られる値である。ランダム値Ｖは、０とＲのＣ倍の間の一様分布から生成される。もしＣがＭより大きければ、ＶをＣから減ずることによってＤが算出される。さもなければ、ＶをＣに足すことによってＤが算出される。
【００５６】
計算された値Ｄは、進行中ラウンド遅延として用いることができる。また、同意プロトコルのインスタンスの実行中にローカルアプリケーションノード２０５が初めてプリエンプトされるときには、プリエンプト遅延としても用いることができる。同意プロトコルのインスタンスの実行中にローカルアプリケーションノード２０５が２回目以降にプリエンプトされるときには、上記方法の中で値Ａの代わりに古い値Ｄを用いて新しい値Ｄが算出される。新しい値Ｄは、プリエンプト遅延として用いられ得る。
固定ストレージの再利用
【００５７】
一実施の形態に基づく複製状態マシン（例えば、複製状態マシン２００）は、フォールトトレランスと高い有用性を保証するために使用された固定ストレージを再利用する。図２及び図３を参照すると、ストレージリクレーマー２９０は、複製状態マシン２００が提案された提案のグローバルシーケンス内における位置を決定し、すべてのアプリケーションノードにこの位置が通知された後、提案ストア２３０から、その提案された提案の記録を消去する。各ローカルアプリケーションノード２０５は、自身のグローバルシーケンスのコピーの中に連続して追加された位置のうち最も高位にあるものを示すメッセージを、定期的な間隔で、他のローカルノード２０５のそれぞれに対して送る。ストレージリクレーマー２９０は、定期的な間隔で、もはやローカルアプリケーションノードによって要求されることのない、連続して追加された位置のうち最も高位のまでのすべての同意を、グローバルシーケンスのすべてのコピーから消去する。このようにして、各複製状態マシン２００は固定ストレージを再利用する。
弱い予約
【００５８】
一実施の形態に基づく複製状態マシン（例えば、複製状態マシン２００）は、通常の動作状態の下で提案者のプリエンプトを終了させるために、弱い予約のメカニズムをオプションで提供する。図２及び図３を参照すると、それぞれの複製状態マシン２００をドライブする各提案者は、連続的にナンバリングされる。例えば、もし３人の提案者がいるとすると、彼らは１，２，３とナンバリングされる。提案者の番号は、各々の複製状態マシン２００のどの提案を、対応する提案者がドライブすることになるのかを決定する。もし提案者の番号がＭであり、Ｎ人の提案者がいるとすると、その提案者は、Ｍ＋（ｋ×Ｎ）（すなわち、Ｍ足すｋ掛けるＮ。ただし、ｋは０以上のすべての整数値）とナンバリングされた複数の提案をドライブすることになる。分配されたアプリケーションシステムのすべての提案者が応答可能でないときにもそのようなシステムが進展できるようにするために、もし複製状態マシンの提案が適時に決定されないとするならば、それぞれの複製状態マシン２００に関連付けられた任意の提案者は、その提案のために「ノーオペレーション」（すなわちｎｏ−ｏｐ）を提案することができる。この最適化を、分配されたアプリケーションに対して透明なものとするため、複製状態マシン２００は、分配されたアプリケーションのｎｏ−ｏｐ提案を配信しない。ノーオペレーションは、一般的には、何の効果も持たず、特に、関連する複製状態マシンの状態を変化させない計算ステップである。
区別されかつ公平なラウンド番号
【００５９】
一実施の形態に基づく複製状態マシンは、複数の競合する提案者の中の一人が、競合する提案者と同じラウンド番号を使っているときにプリエンプトされないことを保証する。一方、従来型の複製状態マシンは、複数の競合する提案者の中の一人が、競合する提案者と同じラウンド番号を使っているときにプリエンプトされないことを保証するメカニズムを含まない。そのような従来型の複製状態マシンにおけるラウンド番号は単調な値であり得、そのような値は、すべての提案者がプリエンプトされることを可能にする。
【００６０】
一実施の形態では、ラウンド番号は、単調成分に加えて区別成分を含むことができる。一実施の形態では、小さな区別できる整数が各複製状態マシン２００の各提案者に関連付けられてもよい。区別できる整数は、最も高い区別成分を有する提案者の有利となるように衝突を解決する役割を果たす。ラウンド番号は、単調成分及び区別成分に加えて、ランダム成分を含む。この種のラウンド番号は、複数の競合する提案者の中の一人が、競合する提案のために同じラウンド番号を使っているときにプリエンプトされないことを保証し、衝突解決が提案者の中の特定の一人を永久に優遇又は冷遇しないことを（すなわち、ラウンド番号のランダム成分を介して）保証する。
【００６１】
２つのラウンド番号を比較するメカニズムは、次のように動作する。より大きい単調成分を有するラウンド番号は、他よりも大きいとされる。もし２つのラウンド番号の単調成分が同じであるなら、より大きいランダム成分を有するラウンド番号が他よりも大きいとされる。これら２つの比較によってランダム番号が区別されない場合には、より大きい区別成分を有するラウンド番号が他よりも大きいとされる。これら３つの比較によってもランダム番号が区別されない場合には、２つのラウンド番号は等しいとされる。
効率的な固定ストレージの再利用
【００６２】
図３及び図４を参照すると、複製状態マシン２００の提案固定ストア２３０内の記録は、複数のグループによって構成されている。各グループは、提案された提案の記録を、連続的なローカル連続番号３３０とともに記憶する。例えば、ローカル連続番号＃１〜＃１００００のレコードはグループ１に属し、ローカル連続番号＃１０００１〜＃２００００のレコードはグループ２に属する、などである。
【００６３】
永続的な提案のグループを参照すると、各グループは、グループ全体によって使用されるストレージリソースが効率的に再利用されるような方法で記憶され得る。例えば、ファイルベースのストレージシステムでは、各グループはそれ自身のファイル又はファイルのセットを使用する。
【００６４】
さらに永続的な提案のグループを参照すると、ストレージリクレーマー２９０は個々のレコードの削除リクエストを監視しているが、リクエストの時点では個々のレコードを削除しない。個々のレコードの累積した削除リクエストがグループ内のすべてのレコードを含むとき、ストレージリクレーマー２９０は、そのグループで使用されていたストレージリソースを効率的に再利用する。例えば、ファイルベースのストレージシステムでは、そのグループによって使われていたファイル又はファイルセットが削除され得る。
【００６５】
複製状態マシン２００の同意ストア２４５内のレコードは、複数のグループによって構成されている。各グループは、同意プロトコルのインスタンスの記録を、連続的な同意インスタンス番号１５０とともに記憶する。例えば、同意インスタンス番号＃１〜＃１００００のレコードはグループ１に属し、同意インスタンス番号＃１０００１〜＃２００００のレコードはグループ２に属する、などである。
【００６６】
同意プロトコルのインスタンスのグループを参照すると、各グループは、グループ全体によって使用されるストレージリソースが効率的に再利用されるような方法で記憶され得る。例えば、ファイルベースのストレージシステムでは、各グループはそれ自身のファイル又はファイルのセットを使用する。
【００６７】
さらに同意プロトコルのインスタンスのグループを参照すると、ストレージリクレーマー２９０は個々のレコードの削除リクエストを監視しているが、リクエストの時点では個々のレコードを削除しない。個々のレコードの累積した削除リクエストがグループ内のすべてのレコードを含むとき、ストレージリクレーマー２９０は、そのグループで使用されていたストレージリソースを効率的に再利用する。例えば、ファイルベースのストレージシステムでは、そのグループによって使われていたファイル又はファイルセットが削除され得る。
小さな提案を効率的に利用すること
【００６８】
図３及び図４を参照すると、一実施の形態に基づく複製状態マシン（例えば、複製状態マシン２００）は、複製状態マシン２００に対して申し込まれた複数の提案の、複数のローカルアプリケーションノード２０５のうちの提案側から複数のローカルアプリケーションノード２０５のうちの受け取り側に対する送信を、バッチ処理により行う。このような実務は、複製状態マシンの提案のサイズが、複製状態マシンによって使用される下層のパケットベース通信プロトコルにおけるデータのパケットのサイズに比べて小さいという状況の下では、一実施の形態に基づく複製状態マシンが効率的にパケットベース通信プロトコルを利用することを可能にする。
【００６９】
一実施の形態では、そのような提案の束(batch)は、同意プロトコルによって単一の提案として取り扱われ得る。この態様によれば、各ローカルノード２０５において、それぞれの複製状態マシン２００が提案された提案の第１の束の同意番号３５０を決定する一方、それぞれのローカルアプリケーションノード２０５で提案された提案は、提案の第２の束に蓄積され得る。第１の束の同意番号１５０が決定されると、複製状態マシン２００は第２の束の同意インスタンス番号３５０の決定を起動し、ローカルアプリケーションノード２０５で提案された提案は第３の束に蓄積される、というように処理が続けられる。
大きな提案１１０を効率的に扱うこと
【００７０】
大きな提案のためのネットワーク帯域幅を削減するために行えることは、一実施の形態に基づく複製状態マシンが短い提案ｉｄ（例えば、１６バイトのグローバルにユニークなｉｄ）によって各提案をタグ付けできるようにすること、及び、ファイルベースの提案として参照されるフォーマットに提案をエンコードすること、又はこれらのうちのいずれか一方である。一方、大きな提案は、そのような大きな提案は従来型の複製状態マシンの同意プロトコルによってドライブされるときに本質的に複数回にわたって送信される、という問題を従来型の複製状態マシンに対して引き起こす。そのような複数回の送信は、大きい提案のサイズが数メガバイトやギガバイトにさえなり得ることから、好ましくない。
【００７１】
大きな提案を送信するとき、一実施の形態では、一旦実際の提案がネットワークのエンドポイントまで成功裏に送信された場合には、短い提案の識別子のみが送られる。ファイルベースの提案は、ファイル内の実際の提案内容がディスク上に保持されるのに対し、本質的に、メモリ上のファイルポインタを有している。そのようなファイルベースの提案をネットワーク上に運ぶとき、一実施の形態に基づく複製状態マシンは、効率のよいフォールトトレラントなファイルストリーミングプロトコルを使用する。そのような輸送は、複製状態マシン２００のＤＦＴＰレイヤー２５０によって扱われる（図３）。ＤＦＴＰレイヤー２５０は、対ファイルベースの提案とネットワークのエンドポイントを監視する。ＤＦＴＰレイヤー２５０は、ファイルベースのプロトコルがネットワークのエンドポイントまで一度だけ送信されることを保証する。部分的な転送につながる失敗イベントが発生した場合には、ファイルベースの提案は、そのファイルの要求された部分を有する任意の利用可能なエンドポイントから読み出される。
【００７２】
一実施の形態では、ＤＦＴＰの実装は、ネイティブな送信ファイル又はメモリにマップされたファイルを、もしオペレーティングシステムがこれらの特徴をサポートするならば、効率的なファイル転送のために使用する。もしファイルを要求するノードがオリジナルな発信者に到達できない場合には、そのノードは代わりの発信者、すなわちそのファイルをたまたま持っているシステム内の他のノードを探す。ＴＣＰプロトコル上で動作するとき、ＤＦＴＰは、高いレイテンシの対象ともなる高帯域コネクションの最適なアドバンテージを生かすため、複数のＴＣＰコネクションを利用する。加えて、高いレイテンシの対象ともなる高帯域コネクションの最適なアドバンテージを生かすため、ＴＣＰプロトコルのウインドウサイズが適切に及び／又は望ましく変更され得る。
【００７３】
情報リポジトリの拡張可能かつ能動的な複製の議論に移る。一実施の形態では、一実施の形態に基づくそのような複製の実装は、上述した複製状態マシンを利用する。より具体的には、一実施の形態に基づくそのような複製を提供することは、そのような複製状態マシンの拡張性、信頼性、及びフォールトトレランスに良い影響を与える。したがって、一実施の形態に基づく複製状態マシンの実行は、分散型コンピューターシステムアーキテクチャの中でそのような複製に良い影響を与える。一実施の形態による情報リポジトリの複製を実行する中で、以下の目的の全部又は一部が満たされるであろう：ＣＶＳリポジトリ、データベース、又は一般的な任意の情報リポジトリの複製を可能にすること、情報リポジトリの複製の、改変を含む同時利用を許容すること、レプリケーション基盤内で使用されるコンピューターネットワークの本質的に任意の障害又は部分的な障害にも関わらず、複製の首尾一貫性を保つこと、複製に関連するコンピューター又はコンピューター資源の本質的に任意の障害又は部分的な障害にも関わらず、複製の首尾一貫性を保つこと、上記した種類の重要な障害にも関わらず、情報リポジトリの連続的な有用性を保証すること、複製が互いにどれだけ離れているか（例えば、異なる大陸上）、又はどれだけ近いか（例えば、同じデータセンター内、さらには同じラック内）、という点で制約がないように複製の地理的な配置を許容すること、協働している情報リポジトリのすべてのレプリカがレポジトリの１つのインスタンスによって処理され得る量よりも高い負荷を処理できるようにすること、レプリカのワンコピーエクイバレンス(one-copy-equivalence)を維持すること、システム内に単一障害点を引き起こすことなく情報リポジトリの複製を可能にすること、情報リポジトリの実装を変更することなく情報リポジトリの複製を可能にすること、情報リポジトリのクライアントの実装を変更することなく情報リポジトリの複製を可能にすること、ＣＶＳリポジトリのクライアントに対し、レプリカのクォーラム(quorum)をローテーションすることを通じて、連結されたローカルなＣＶＳリポジトリの応答時間を提供すること、ＣＶＳリポジトリのクライアントと、遠く離れたＣＶＳリポジトリとの間でのネットワーク通信を、広域ネットワークの約３倍低減すること（例えば、約４．５ラウンドトリップに対して約１．５ラウンドトリップ）、機能しなくなった複製の遠隔復旧を、管理者の仲介を要求することなく自動的に行えるようにすること、そして、管理者の仲介を要求することなく自動的に、確実にすべての複製の分散状態のクリーンナップを行うこと。
【００７４】
図７を参照すると、一実施の形態に基づくレプリケーター１２０の一実施の形態が示されており、ここではレプリケーター６００として参照される。レプリケーター６００は、レプリケータークライアントインターフェイス６１０、プレクオリファイアー６２０、複製状態マシン６３０、スケジューラー６４０、レプリケーターリポジトリインターフェイス６５０、結果ハンドラ６６０、及び管理者コンソール６７０を含む複数の機能的なモジュールからなる。レプリケータークライアントインターフェイス６１０、プレクオリファイアー６２０、複製状態マシン６３０、スケジューラー６４０、レプリケーターリポジトリインターフェイス６５０、結果ハンドラ６６０、及び管理者コンソール６７０はそれぞれ、これらの間の相互作用を可能にするために少なくとも他のモジュールの一部と互いに接続されている。図２〜図６を参照して機能的に議論された複製状態マシン２００は、レプリケーター６００の複製状態マシン６３０の一例である。したがって、複製状態マシン６３０は、信頼性があり、有用であり、拡張性があり、フォールトトレラントである。
【００７５】
図８は、一実施の形態に基づくマルチサイトコンピューターキテクチャー内のレプリケーター６００の配置の実施の形態を示している。マルチサイトコンピューターキテクチャーは、複数の分散型アプリケーションシステム６０１を含み得る。各分散型アプリケーションシステム６０１は、複数のクライアント６８０、レプリケーター６００、リポジトリクライアントインターフェイス６９０、リポジトリ６９５（すなわち、情報リポジトリ）、及びネットワーク６９９を含み得る。ネットワーク６９９は、一般的に複数の分散型アプリケーションシステム６０１のうちの任意のひとつの構成要素である必要はないが、各分散型アプリケーションシステム６０１のクライアント６８０とそれぞれのレプリケーター６００の間、及び、各分散型アプリケーションシステム６０１のリポジトリクライアントインターフェイス６９０とそれぞれのレプリケーター６００の間に接続されていてよく、そうすることによって、各分散型アプリケーションシステム６０１のクライアント６８０、レプリケーター６００、リポジトリ６９５の相互作用を可能にするために、これらを相互に接続することが可能になる。ネットワークはまた、すべての分散型アプリケーションシステム６０１のレプリケーター６００の間に接続されていてもよく、そうすることによって、すべての分散型アプリケーションシステム６０１のレプリケーター６００の間で相互作用が可能になる。複数のネットワーク６９９は互いに分離されていてもよいが、そうである必要はない。例えば、同じネットワークによって、上で開示した３つの役割のすべてが満たされ得る。
【００７６】
図８に示すように、複数のリポジトリ６９５（すなわち、それぞれリポジトリ６９５を含む複数の分散型アプリケーションシステム６０１のシステム要素）それぞれの「近く」には、３つのクライアント６８０がある。近くということにより、複数のリポジトリ６９０の中の特定のひとつの近くにある複数のクライアント６８０の中の特定のひとつは、複数のリポジトリ６９０の中のその特定のひとつにアクセスすることを選ぶであろうということが意味される。或いは、複数のクライアント６８０の中のその特定のひとつは、任意の分散型アプリケーションシステム６０１の中のそのリポジトリ６９５に潜在的にアクセスすることがあり得る。
【００７７】
一実施の形態に基づく分散型コンピューターシステムのオペレーターは、クライアント６８０のユーザと、分散型アプリケーションシステム６０１の一人又は複数人の管理者を含む。クライアント６８０のユーザは、クライアントユーザ用マニュアルの指示に従う。実施の形態の多くの有利な側面はユーザに対してトランスペアレントであり得るので、ユーザは、一実施の形態に基づくレプリケーターを使っているという事実に気付かない可能性がある。管理者は、レポジトリ６９５自身を管理する標準的なタスクに加え、必要に応じて、そして、もしオペレーションのために必要であれば、適切にネットワークを設定するであろう。
【００７８】
各分散型アプリケーションシステム６０１の複製状態マシン６３０は、ネットワーク６９９を介して互いに通信を行う。各レプリケーターリポジトリインターフェイス６５０は、ネットワーク６９９を通じて、それぞれの分散型アプリケーションシステム６０１のレポジトリ６９５と相互作用する。クライアント６８０は、ネットワーク６９９を通じて、レプリケータークライアントインターフェイス６１０と相互作用する。オプションで、特定のクライアント６８０を含む特定の分散型アプリケーションシステム６０１が、特定の時点で、要求された機能を提供するために利用できない場合に、その特定の分散型アプリケーションシステム６０１のその特定のクライアント６８０が他の分散型アプリケーションシステム６０１のいずれかにフェイルオーバーすることを可能にするために、例えばシスコシステムズディレクターのような製品を使用することも可能である。
【００７９】
図７及び図８を参照すると、レプリケータークライアントインターフェイス６１０は、ターゲットであるリポジトリ６９５に関連する複数のクライアント６８０の中の特定のひとつ（すなわち、特定のクライアント６８０）とのインターフェイスを司る。レプリケータークライアントインターフェイス６１０は、特定のクライアント６８０によってネットワーク６９９上に発行されたコマンドを再構成し、そのコマンドをプレクオリファイアー６２０に配信する。プレクオリファイアー６２０はレプリケーター６００の効率的なオペレーションを可能にするが、レプリケーター６００の有用かつ有利なオペレーションに必須というわけではない。
【００８０】
各コマンドのために、プレクオリファイアー６２０はオプションで、そのコマンドが失敗する運命にあるか否かを決定し、そしてもしそうであれば、適切なエラーメッセージ又はエラー状態が上記特定のクライアント６８０に返されることを決定する。もしそうであれば、そのエラーメッセージ又はエラー状態はレプリケータークライアントインターフェイス６１０に返送されることができ、レプリケータークライアントインターフェイス６１０はそのエラーメッセージ又はエラー状態は上記特定のクライアント６８０に配信する。それ以来、そのコマンドは、どの他のレプリケーター６００によっても処理されないかもしれない。
【００８１】
各コマンドのために、プレクオリファイアー６２０はオプションで、そのコマンドが複製状態マシン６３０、又は、複製状態マシン６３０とスケジューラー６４０の両方を迂回できるか否かを決定する。もしプレクオリファイアー６２０が複製状態マシン６３０は迂回され得ると決定しなかったならば、そのコマンドは複製状態マシン６３０に配信され得る。複製状態マシン６３０は、自身と、分散型アプリケーションシステム６０１の他の関連するレプリケーター６００のそれぞれにある仲間の複製状態マシン６３０とに提出されたすべてのコマンドをコレート(collate)する。このオペレーションのシーケンスは、すべての分散型アプリケーションシステム６０１において同一であることが保証されてもよい。複数の分散型アプリケーションシステム６０１のそれぞれにおいて、それぞれの複製状態マシン６３０は、上記のようにしてコレートされたコマンドを、順番に、それぞれのスケジューラー６４０に対して配信する。
【００８２】
スケジューラー６４０は、それに対して配信されたコマンドに対して依存状態分析を行い、なおもワンコピーシリアライザビリティ(one-copy Serializability)を保証するウィーケストパーシャルオーダリング(the weakest partial ordering)を決定する。そのような依存状態分析及びワンコピーシリアライザビリティは、「データベースシステムにおける同時制御及びリカバリ(Concurrent Control & Recovery in Database System)」とのタイトルが付けられたウエズリー・アディソン(Wesley Addison)の先行技術文献に開示されているとともに、Ｐ．ベルシュタイン(P.Berstein)による参考図書に公表されている。スケジューラー６４０はその後、構築された半順序(partial order)によって許可されると同時に、さもなければ連続的に、コマンドをレプリケーターリポジトリインターフェイス６５０に配信する。
【００８３】
レプリケーターリポジトリインターフェイス６５０は、コマンドをリポジトリ６９５に配信する。それに応じて、３つの結果のうちのひとつが起きる。その後、レプリケーターリポジトリインターフェイス６５０は、起きている結果を結果ハンドラ６６０に配信する。
【００８４】
上記３つの結果のうちの一つ目は、リポジトリ６９５がコマンドに対する応答を返すことを含み得る。この応答は、コマンドの実行中に何もおかしくならなかったことを示す結果、状態、又はその両方を含む。もしコマンドの起源がローカルにあれば、結果ハンドラ６６０はその応答をレプリケータークライアントインターフェイス６１０に配信し、レプリケータークライアントインターフェイス６１０はその応答をクライアント６８０に配信する。もしコマンドの起源が他の分散型アプリケーションシステム６０１のレプリケーターにあれば、好ましくは、応答は廃棄される。
【００８５】
上記３つの結果のうちの二つ目は、リポジトリ６９５がエラー状態を返すことを含み得る。結果ハンドラ６６０は、そのエラー状態が、リポジトリ６９５内の決定論的なエラーであるか否か（すなわち、他の分散型アプリケーションシステム６０１のそれぞれで同じ又は同等のエラーが発生するか否か）を決定する。もしエラーの決定が曖昧であれば、結果ハンドラ６６０は、そのエラーと、他の分散型アプリケーションシステム６０１での結果との比較を試みる。もしこのことが曖昧さを解消せず、又は、もしエラーが明確に決定論的なものでなければ、結果ハンドラ６６０は、レプリケーター６００のオペレーションを中止し、管理者コンソール６７０を通じて（すなわち、管理者コンソール６７０を介した通知の発行を通じて）オペレーターに通知する。
【００８６】
レプリケーターがＣＶＳレプリケーターである場合、以下にＣＶＳに特有の機能性について議論するように、結果ハンドラによって、決定論的なエラーのフラグを立てるためにエラーパターンのリストが使用される。結果ハンドラ６６０は、応答ストリーム内で正規表現マッチを行うために、これらのパターンを使用する。
【００８７】
上記３つの結果のうちの三つ目は、ハングアップした（すなわち、コマンドの実行から戻らない）リポジトリ６９５を含み得る。一実施の形態では、この結果は、上記３つの結果のうちの二つ目を参照して議論したように、まさに決定論的でないエラーのように取り扱われ得る。
【００８８】
一実施の形態に基づくと、各レプリケーター６００は二者択一的に構成され得る。代替の実施の形態では、レプリケーター６００は、リポジトリ６９５のクライアント６８０の中に埋め込まれ、直接的にドライブされ得る。他の代替の実施の形態では、レプリケーター６００は、リポジトリ６９５へのクライアントインターフェイス６９０の中に埋め込まれてもよい。他の代替の実施の形態では、レプリケーター６００は、リポジトリ６９５の中に埋め込まれてもよい。他の代替の実施の形態では、レプリケーターのグローバルシーケンサーは、付随する堅牢性とサービスの質の妥協とともに、他の技術に基づいてもよい。そのような技術のいくつかの可能な例のうちのひとつは、グループコミュニケーションである。他の代替の実施の形態では、レプリケーター６００は、付随する堅牢性とサービスの質の妥協とともに、１つ以上のリポジトリ６９５をドライブする。他の代替の実施の形態では、レプリケーター６００のモジュールは、より粗いモジュールに統合されるか、より細かいモジュールに分かれるか、或いはこれらの両方である。他の代替の実施の形態では、ワンコピーシリアライザビリティからの逸脱に対する冗長的な予防手段として、各分散型アプリケーションシステム６０１のリポジトリ６９５に含まれる情報が他の分散型アプリケーションシステム６０１のそれぞれに対して首尾一貫した状態を維持することを保証するために、すべての分散型アプリケーションシステム６０１の応答が比較される。
【００８９】
図７及び図８を参照すると、上で議論された複数のリポジトリ６９５のひとつひとつは、コンカレント・バージョンズ・システム（ＣＶＳ）リポジトリであってよく、クライアント６８０は対応してＣＶＳクライアントであってよい。リポジトリ６９５がＣＶＳリポジトリであり、クライアント６８０がＣＶＳクライアントである場合、リポジトリ６９５及びクライアント６８０に関連付けられるインターフェイスは、ＣＶＳ特有のインターフェイス（例えば、レプリケーターＣＶＳインターフェイス、レプリケーターＣＶＳリポジトリインターフェイス、及びリポジトリＣＶＳクライアントインターフェイス）となる。さらに、一実施の形態に基づくと、レプリケーター６００は、ＣＶＳリポジトリとの使用のために具体的にかつ特に構成された機能を有するように変更され得る。
【００９０】
ここに開示されるレプリケータークライアントインターフェイス６１０は、ＣＶＳクライアントと、ターゲットとなるＣＶＳリポジトリとをインターフェイスするために具体的に構成され得る。そのために、レプリケータークライアントインターフェイス６１０は、ＣＶＳクライアントから到着するバイトを、メモリマップされたファイルバッファに記憶させる。レプリケータークライアントインターフェイス６１０は、到着するバイトストリーム内に有効なコマンド文字列を見つけたとき、ＣＶＳコマンドの終端を検出する。そのような有効なコマンド文字列の限定されないリストは、限定されるものではないが、「Root、「Valid-responses」、「valid-requests」、「Max-dotdot」、「Static-directory」、「Sticky」、「Entry」、「Kopt」、「Checkin-time」、「Modified」、「Is-modified」、「UseUnchanged」、「Unchanged」、「Notify」、「Questionable」、「Argument」、「Argumentx」、「Global_option」、「Gzip-stream」、「wrapper-sendme-rcsOptions」、「Set」、「expand-modules」、「ci」、「co」、「update」、「diff」、「log」、「rlog」、「list」、「rlist」、「global-list-quiet」、「ls」、「add」、「remove」、「update-patches」、「gzip-file-contents」、「status」、「rdiff」、「tag」、「rtag」、「import」、「admin」、「export」、「history」、「release」、「watch-on」、「watch-off」、「watch-add」、「watch-remove」、「watchers」、「editors」、「init」、「annotate」、「rannotate」、「noop」、及び「version」を含み得る。
【００９１】
その後、レプリケータークライアントインターフェイス６１０は、到着したＣＶＳコマンドをリードコマンド又はライトコマンドに分類することを試みる。有効なライトコマンド文字列の限定されないリストは、限定されるものではないが、「ci」、「tag」、「rtag」、「admin」、「import」、「add」、「remove」、「watch-on」、「watch-off」、及び「init」を含み得る。有効なライトコマンド文字列のリストに含まれない有効なコマンド文字列内のすべてのコマンドは、有効なコマンド文字列のリストに対して、ここではリードコマンドであるとみなされる。
【００９２】
リードコマンドは、ターゲットであるＣＶＳリポジトリによる実行のために、ＣＶＳレプリケーターリポジトリインターフェイスに直接的に配信される。ＣＶＳライトコマンドは、オプションで、プレクオリファイアーモジュール２０に配信される。
【００９３】
それぞれのＣＶＳライトコマンドのために、プレクオリファイアー２０はオプションでＣＶＳが失敗する運命にあるか否かを決定することができ、もしそうであるなら、ＣＶＳクライアントに対して返されるべき適切なエラーメッセージ又はエラー状態を決定する。失敗の検出は、ＣＶＳリポジトリから返される結果又は状態バイトストリームと、既知のエラーパターンとを照合することに基づいて行われ得る。既知のシステムエラーパターンの例は、限定されるものではないが、．＊から．＊へのシンボリックリンクを生成できない、ｒｓｈを介してサーバを起動できない、．＊をｆｓｔａｔできない、一時ファイルを生成するのに失敗した、生成のためにｄｂｍファイル．＊をオープンできない、．＊に書き込めない、履歴ファイルをｓｔａｔできない、履歴ファイル：．＊をオープンできない、「．＊」をオープンできない、マッピングのためのＲＣＳアーカイブ．＊をｓｔａｔできなかった、比較のためにファイル．＊をオープンできない、仮想メモリが使い果たされた、ＲＣＳファイル内でｆｔｅｌｌｏできない、．＊を読み出せない、補助的なグループのリストを得ることができない、コピーの後、ファイル．＊をｆｓｙｎｃできない、．＊をｓｔａｔできない、カレントディレクトリを開けない、ディレクトリ．＊をｓｔａｔできない、．＊に書き込めない、．＊をｒｅａｄｌｉｎｋできない、パイプをクローズできない、ディレクトリ．＊に変更できない、一時ファイルを生成できない、．＊のためのファイル情報を取得できなかった、ｄｉｆｆ出力ファイル．＊をオープンできなかった。．＊を生成できない、ワーキングディレクトリを得ることができない、．＊をｌｓｔａｔできない、ｄｉｆｆのためのｆｏｒｋが．＊に対して失敗した、．＊のための情報を得ることができなかった、．＊のためにモードを変更できない、．＊のためにｆｔｅｌｌｏできない、メッセージベリフィケーションが失敗した、一時ファイルをｓｔａｔできない、メモリ不足、「．＊」の中にディレクトリ「．＊」を作ることができない、ログイン時にパスワードを読み込むのに失敗した、履歴ファイルをリードする際のエラー、作業ディレクトリを得ることができなかった、￥ｄ＋にｃｌｏｓｅ−ｏｎ−ｅｘｅｃフラグをセットできない、ロックファイル．＊にライトする際のエラー、履歴ファイルに書き込めない、ファイル．＊を．＊にリネームできない、．＊ディレクトリに変更できない、．＊のためのファイル情報を得ることができない、コピーするために．＊を生成できない、一時ファイル．＊に書き込めない、．＊をオープンできない、フローコントロールリードに失敗した、サーバへの書き込み、．＊をクローズできない、ロックファイル「．＊」をオープンできなかった、リードのために￥ｄ＋をｆｄｏｐｅｎできない、一時ファイル．＊をクローズできない、要求されたチェックアウトディレクトリ「．＊」にディレクトリを変更しない、ディレクトリ．＊を生成できない、ｕｍａｓｋの値が無効である、リードのために．＊をオープンすることに失敗した、補助グループの番号を得られない、ライトのために．＊をオープンできなかった、．＊にｃｈｄｉｒできなかった、．＊をｄｉｆｆしている間にｆｏｒｋが失敗した、．＊をオープンできなかった、ライトのために￥ｄ＋をｆｄｏｐｅｎできない、．＊へのライトが失敗した、一時ファイル．＊を生成できない、．＊をリードできなかった、コピーするためにファイル．＊にライトできない、コピーするために．＊をオープンできない、パイプをｄｕｐ２できない、．＊にｇｅｔｗｄできない、書き込むために．＊をオープンできない、ｆｏｒｋできない、サーバに書き込む際のエラー、．＊にチェックインできなかった−ｆｏｒｋが失敗した、比較のためにファイル．＊をリードできない、．＊に．＊をリンクできない、．＊をクローズする際のエラー、ネットコネクションをｄｕｐできない、データのリードに失敗した、．＊をリードできない、．＊をリムーブできない、「．＊」にｃｈｄｉｒできなかった、一時ファイル．＊をオープンできない、．＊をｓｔａｔできなかった、ディレクトリ．＊をオープンできない、ｆｗｒｉｔｅに失敗した、一時ファイル．＊を生成できない、一時ファイルをｓｔａｔできない、．＊をｓｔａｔできない、「．＊」をリードできない、．＊をｄｉｆｆする際のエラー、特別なファイル．＊を生成できなかった、履歴ファイル：．＊をクローズできない、ＲＣＳアーカイブ＊にメモリをマップできなかった、ディレクトリ「．＊」を生成できない、コピーのためにファイル．＊をリードできない、パイプを生成できない、一時ファイル．＊をオープンできない、ファイル．＊を利ムーブできない、オープンできない、履歴ファイルの終端をシークできない、．＊にｃｈｄｉｒできない、レングスのリードに失敗した、．＊を実行できない、．＊をｆｄｏｐｅｎできない、及び、一時ファイルのサイズをｆｉｎｄできない、を含んでいた。既知のノンシステムエラーパターンの例は、限定されるものではないが、内部エラー：そのようなリポジトリはない、求められるバージョンが見つからなかった、ｇｅｔｓｏｃｋｎａｍｅが失敗した、警告：ＲＣＳファイルをリライトしている間にｆｅｒｒｏｒがセットされた、内部エラー：ｉｓｌｉｎｋがリードリンクをｌｉｋｅしない、アクセスが否定された、このシステムの装置ファイルを比較できない、サーバ内部エラー：サーバアップデートにおける未処理ケース、．＊信号を受信した、内部エラー：そのためのレビジョン情報はない、プロトコルエラー：重複モード、サーバ内部エラー：サーバアップデートにおけるモードなし、ｒｃｓｂｕｆキャッシュがオープンする：内部エラー、致命的エラー，アボートする、致命的エラー：イグジットする、．＊：予期しないＥＯＦ、．＊：混同したレビジョン番号、無効なｒｃｓファイル、ＲＣＳファイル内のキーにＥＯＦ、ＣＶＳ内のＲＣＳファイルがいつもｖで終わる、ハードリンク情報が失われた、．＊：ファイルの終わりがリードできない、ｒｃｓｂｕｆオープン：内部エラー、メモリ不足、ｉｎｆｏｐａｔｈをアロケートできない、．＊からの予期しないｄｙｉｎｇ  ｇａｓｐ、内部エラー：不正な日付．＊、ケルベロス認証が失敗した：．＊、．＊デルタ．＊：予期しないＥＯＦ、ＲＣＳファイル．＊を読み込む際に予期しないＥＯＦ、ＥＲＲＯＲ：スペース不足−中断、フローコントロールＥＯＦ、ＲＣＳファイル．＊をｆｓｅｅｋｏでき���い、．＊に対するチェックサムの失敗、ＣＶＳ内部エラー：未知の状態￥ｄ＋、内部エラー：ｒｕｎ＿ｐｒｉｎｔに対する不正なアーギメント、このシステムに装置ファイルをコピーできない、．＊をリードする際に予期しないファイルの終了、メモリ不足、内部エラー：解析されたＲＣＳファイルがない、内部エラー：ＲＣＳ＿ｃｏｐｙｄｅｌｔａｓにおける早すぎるＥＯＦ、内部エラー：未知の応答￥？のためのサポートをテストしている。ＲＣＳファイル．＊内の値におけるＥＯＦ、ＰＡＮＩＣ￥＊管理ファイルが失われている￥！、．＊をリードする際に早すぎるファイルの終わり、ＲＣＳファイル．＊内の値を探している間にＥＯＦ、継続できない、リードロックが失敗した−ギブアップする、．＊をリードする際に予期しないＥＯＦ、「．＊」をｒｅｓｕｒｒｅｃｔできない、セカンドパーティーによって削除されたＲＣＳファイル、あなたの見かけのユーザ名．＊がこのシステムには未知である、ファイル属性データベースの崩壊、．＊内におけるタブの喪失、このシステムに装置ファイルをインポートできない、．＊：未知の種類の特別なファイルをインポートできない、＊：未知のタイプの特別なファイルをインポートできない、エラー：．＊をｍｋｄｉｒできない−加えられなかった、リポジトリ「．＊」にライトロックを生成できない、．＊を生成できない、このシステムに特別なファイルを生成できない、．＊を保存できない、このシステムに装置ファイルを保存できない、リポジトリファイル．＊を解析する際のエラー、ファイルが破損している可能性があり、ファイル．＊のためのファイル状態￥ｄ＋が未知である、を含んでいた。
【００９４】
図７及び図８を参照して議論したように、プレクオリファイアー６２０はそれぞれのコマンドについて、そのコマンドが失敗する運命にあり、かつ、複製状態マシン６３０及びスケジューラ６４０の両方をバイパスできる、ということを決定できる。ＣＶＳに特有の機能性のケースでは、もしプレクオリファイアー６２０が複製状態マシン６３０がバイパスされ得ると決定しなかったならば、そのコマンドはＣＶＳ提案コマンドに変換され得る。ＣＶＳ提案コマンドは、実際のＣＶＳコマンドバイトアレイの他、もしこのＣＶＳ提案コマンドがＣＶＳリポジトリによって直接的に実行されたとしたらそのＣＶＳリポジトリに取得させることになる書き込みロックを表すロックセットを含む。以下で議論するように、スケジューラ６４０はこのロックセットを利用する。
【００９５】
ＣＶＳ提案コマンドは、複製状態マシン６３０に対して配信され得る。複製状態マシン６３０は、自身及び、他の複数のレプリケーターのそれぞれにある自身の仲間である複製状態マシン６３０に提出されたすべてのコマンドを、１つのシーケンスにコレートする。このシーケンスは、すべての複製で同一であることが保証される。分散型アプリケーションシステム６０１のそれぞれにおいて、複製状態マシン６３０は、上記のようにしてコレートされたコマンドを、順番に、スケジューラ６４０に対して配信する。
【００９６】
スケジューラ６４０は、自身に対して配信されたコマンドに対して依存状態分析を行い、なおもワンコピーシリアライザビリティ(one-copy Serializability)を保証するウィーケストパーシャルオーダリング(the weakest partial ordering)を決定する。スケジューラ６４０は、構築された半順序(partial order)によって許可されると同時に、さもなければ連続的に、コマンドをＣＶＳレプリケーターリポジトリインターフェイスに配信する。
【００９７】
一実施の形態に基づくと、依存状態分析は、ロックの衝突をテストすることに基づいて行われ得る。スケジューラに対して提出される各ＣＶＳ提案コマンドは、ロックセットを含む。スケジューラーは、そのロックセットが他のコマンドのロックセットと衝突しない場合にのみ、コマンドがＣＶＳリポジトリに配信されることを保証する。もし衝突が検出されたら、そのコマンドはキューに待機し、ロックセット内のすべてのロックが衝突なしで得られるときより後の時点に予定される。
【００９８】
上記したように、マルチサイトコンピューターシステムアーキテクチャーの実装は、そのような複製状態マシンの拡張性、信頼性、有用性、及びフォートトレランスに良い影響を与える。効率的なスケーリングは、システムに対して新たに割り振られたアプリケーションノード（又は単にノード）を加えるために効率的なプロセスを要求する。しかしながら、新たに加えられたノードが分配型のコンピューターシステム内に参加することを可能にするためには、それらに一定量の情報が与えられなければならない。例えば、新ノードは、共同プロジェクトに参加するために必要な資格を与えられなければならないし、既存のロケーションと、そこから見ることができ、かつ新たに招待されたノードがメッセージの交換と相互作用を許容されるノードとについて話されなければならない。一実施の形態によれば、それらはメッセージングモデルと、ノードインダクション法と、誘導者ノードが新入者ノードを分散型のコンピューターシステムに連れてくることを可能にするために効果的である、対応する装置とシステムと、導入されたノードが役に立つ仕事を行うことを可能にすることとによって実現される。
メッセージングモデル
【００９９】
ここで、用語「誘導者」又は「誘導者ノード」は他のノード、すなわち「新入者ノード」の分散型コンピューターシステムへの導入を少なくとも起動するノードを意味する。一実施の形態によれば、誘導者ノードと新入者ノードは、下記のような非同期かつ複雑でないモデルを用いるメッセージの送信により、互いに通信を行う。
−どちらか一方のプロセスは、任意のスピードで動作し、停止することによって失敗し、再起動するかもしれない、
−プロセスが任意の時点で失敗するかもしれないので、いくつかの情報は再起動の前後にわたって記憶されなければ（すなわち、永続的でなければ）ならない、
−メッセージは、配信されるのに任意の長時間をかけることができ、重複及び失われ得るが、破損しない（破損したメッセージは配信されていないメッセージと同じ扱いを受けるので、受信側によって破棄される）。
【０１００】
図９は、一実施の形態によるノードのグループへのノードの安全かつ認証された導入を可能にする装置、方法、及びシステムの一側面を示す図である。その中に示されるように、そして一実施の形態によれば、例えばプレ認証フェイズ、新入者ノードのスタートアップフェイズ、ブートストラップメンバーシップの配置フェイズ、及び新入者ノードと位置の認知のようないくかつの方法を分散型コンピューターシステムにノードを導入する方法は含み得、本システム及び装置は実行するように構成され得る。加えて、複数の導入後タスクが実行され得る。これらのフェイズのそれぞれは、以下に詳細に記述される。
Ａ．  プレ認証フェイズ
【０１０１】
一実施の形態によれば、プレ認証フェイズは新入者ノード２０６が起動される前に実行されることができ、管理者２０２に、導入プロセスで使用されるとともに導入プロセスのプレコンフィグレーションを可能にする情報を含む導入タスクを生成する機会を提供することができる。したがって、一実施の形態によれば、プレ認証フェイズは人間の干渉なしに進むことができる。
Ａ．０  新導入タスクの生成
【０１０２】
新入者ノード２０６が起動される前に、成功しかつ完全な導入プロセスのために要求される情報を含む導入タスクが誘導者ノード２０４に生成され得る。永続的なタスクの使用は、導入プロセス内で要求される情報と導入プロセスの状態とが誘導者ノード２０４の再起動の後に残るように、そして、同じ導入タスクが他の導入でコピーされて（クローニングされて）再利用されるように、この情報が同じ場所に記憶されることを許容する。
【０１０３】
一実施の形態によれば、導入タスクは、導入チケット、新入者ノード２０６が知るべきであるノードのセット、及び導入後タスクのセットの３要素を含むように構成され得る。他の要素が付加されてもよく、また、他の要素によってこれら３つの要素が代替されてもよいことが理解される。
Ａ．１  導入チケット
【０１０４】
導入は、例えば管理者によって生成され、図９のＢ２１に示されるように、新入者ノード２０６に送信される。この導入チケットは、例えば、管理者２０２に対して、誘導者ノード２０４の詳細な連絡先をパッケージし、新ノードの詳細を特定し（そして制御し）、そしてまた、いくつかの他のプラットフォーム又は新ノードのためのアプリケーション設定パラメータを特定するためのメカニズムを提供する。一実施の形態によれば、導入チケットは以下を含み得る。
−導入タスクの識別
−新入者ノード２０６のノードとロケーションの識別
−誘導者ノード２０４のロケーション識別、ホストネーム、及びポート（新入者ノード２０６が誘導者ノード２０４にアクセスするために必要な基本情報）、及び／又は
−他の、任意の、プラットフォーム／アプリケーションの設定情報
【０１０５】
導入チケットは、分散型コンピューターシステム内の選択された他のノードについて、新入者ノード２０６が見ることができ、見られることができ、かつ、通信することができるようになることと同じ又は機能的に類似の結果を達成する他の情報を含み得る。導入チケットは、例えば、ファイルとして構成され得る。セキュリティを高めるため、そのような導入チケットはそれゆえ、ＰＫＩシステムにおける誘導者ノードの秘密鍵を用いて協調設計され得る。同様に、新入者ノード２０６は、誘導者ノード２０４の公開鍵を用いて、導入チケットに含まれる詳細の信憑性を確認するよう構成される。ここに記述され示された実装はセキュリティのＰＫＩモデルに制限されないので、他の認証及び権威が定義する方法を、効果があるように利用することができる。導入チケットは、一実施の形態によれば、その後、インクダクティーノード２０６のインストレーションを実行するエンジニア２０８に帯域外で送信される。一実施の形態によれば、導入チケットは誘導者ノード２０４とともに残り、新入者ノード２０６が起動するときに新入者ノード２０６に対して「プッシュ送信」される。
Ａ．２  新入者ノードが気付くべきであるノードのセット
【０１０６】
一実施の形態によれば、導入タスクは、導入プロセス中に新入者ノード２０６が通知されるべき既存のノードの詳細を含み得る。新入者ノード２０６は、新入者ノード２０６がそれとともに通信／仕事をすることができ、及び／又は、許容される分散型コンピューターシステム内の他のノードを知らされる、ということに留意する必要がある。そのような情報はそれゆえ、もし人間の干渉がないとすれば、導入プロセスが開始される前に有利に特定される。新入者ノード２０６が通信を可能とされ、又は、許容されるノード又は複数のノードの選択は、すでに複数のノードのネットワークの中に導入されている既存のノードの完全なセット又はサブセットの中のノードのセットを選択することを管理者２０２に許容するユーザインターフェイス（ＵＩ）を用いて実行され得る。この情報は、後にアクセスでき得るよう導入タスク内に記憶される。ＵＩは、例えば、ブラウザ又はモバイル装置アプリを含んでよい。
Ａ．３  導入後タスク
【０１０７】
一実施の形態によれば、導入後タスクは複数のタスクの詳細を含み得る。そのようなタスクの１つ以上は、例えば既存のメンバーシップに参加するなど、導入をフォローする新しい新入者ノード２０６に適用され得る。このタスクのセットは、もし新入者ノード２０６が導入をフォローする際に何をすることも要求されないならば、空でもよいことに留意が必要である。一旦、導入タスクが生成され、持続状態とされる（例えば、不揮発性メモリに記憶される）と、新入者ノード２０６が起動され得る。
Ｂ．  新入者の起動
【０１０８】
一実施の形態によれば、新入者ノード２０６は起動され得る。
Ｂ．１．  新入者ノードに導入チケットが存在しない場合
【０１０９】
一実施の形態によれば、もし新入者ノード２０６に導入チケットが存在しないならば、新入者ノード２０６は、以下に記述するように、基礎的なコンフィグレーションで起動し、又は、起動させられ、新入者ノード２０６がメンバーとなるであろうブートストラップメンバーシップの詳細とともに誘導者ノード２０４が接触してくるのを待機する（すなわち、Ｂ２２に示すように聞く）。
Ｂ．２．  新入者ノードに導入チケットが存在する場合
【０１１０】
一実施の形態によれば、Ｂ２３に示した起動時点で、もし新入者ノード２０６に導入チケットが本当に存在するならば、新入者ノード２０６は、次のように構成され得る：
ａ）導入タスク内の情報を解析する（必要に応じて、オプションで認証する）。
ｂ）この情報を、アプリケーションプラットフォームを設定するために使用する。
ｃ）この情報を、Ｂ２４に示したブートストラップメンバーシップ要求(BootstrapMembershipRequest)ビーコンを生成しかつオンするために使用する。ブートストラップメンバーシップ要求ビーコンは、Ｂ２５に示すように、新入者ノード２０６が導入プロセスを起動していることを誘導者ノード２０４に通知するように構成され得る。一実施の形態によれば、ビーコンは、ターゲット受信者の所定のリストに対してメッセージを繰り返しブロードキャストするよう構成されるとともに、所定のリストからターゲット受信者を削除するプロセスである。メッセージは、個々のターゲット受信者から応答のアクナレッジメントが受信されるまで、所定のリストに対してブロードキャストされる。一実施の形態によれば、ブートストラップメンバーシップ要求は、導入タスクの識別、新入者ノードとロケーションの識別、ホストネーム、及びポートを含むように構成され得る。
【０１１１】
一実施の形態によれば、誘導者ノード２０４が新入者ノード２０６からブートストラップメンバーシップ要求を受信するのに応答して、誘導者ノード２０４は、Ｂ２６に示すように新入者ノード２０６に対してブートストラップメンバーシップレスポンス(BootstrapMembershipResponse)を返送し、それによって、Ｂ２７に示すようにリクエストビーコンを無効にすることとしてもよい。誘導者ノード２０４はその後、導入タスクを調べ、そのノード及びロケーションの識別が、以前に受信した導入チケット内に特定されていたものと一致するか否かを、Ｂ２８に示すように確認することができる。もしこの確認が失敗したら、すなわちそのノード及び／又はロケーションの識別が導入タスク内のものと一致しなかったら、誘導者ノード２０４は、Ｂ２９に示すように、ブートストラップメンバーシップ否定(BootstrapMembershipDenied)メッセージを新入者ノード２０６に送信(beacon)し得る。
【０１１２】
新入者ノード２０６は、ブートストラップメンバーシップ否定メッセージを受信したとき、呼応してブートストラップメンバーシップアック(BootstrapMembershipAck)メッセージを送信し、Ｂ３０に示すように処理を終了するように構成され得る。誘導者ノード２０４は、Ｂ３１に示すように新入者ノード２０６からブートストラップメンバーシップアックメッセージを受信したとき、Ｂ３２に示すように、ブートストラップメンバーシップ否定メッセージを無効にし得る。
Ｃ．  ブートストラップメンバーシップの配置
【０１１３】
一実施の形態によれば、新入者ノード２０６が導入チケットなしで起動し、管理者２０２が誘導者ノード２０４で導入プロセスを開始した場合、又は、導入タスクのルックアップが成功した場合、ブートストラップメンバーシップの生成及び配置が次のプロセスを用いて実行され得る：
【０１１４】
一実施の形態によれば、誘導者ノード２０４は、一実施の形態により以下を実行する。
１．次のａ〜ｃとともにブートストラップメンバーシップを生成する。
ａ．決定論的に生成されたメンバーシップ識別
ｂ．同意提案者及び同意受容者の役割にある誘導者ノード２０４
ｃ．学習者の役割にある新入者ノード
２．Ｂ３３に示すように、メンバーシップを配置する。
３．Ｂ３４に示すように、ブートストラップメンバーシップを参照して決定論的な状態マシンを生成する。
４．Ｂ３５に示すように、ブートストラップメンバーシップレディ(BootstrapMembershipReady)メッセージを新入者ノード２０６に対して送信(beacon)する。
【０１１５】
一実施の形態によれば、Ｂ３６に示すようにブートストラップメンバーシップレディメッセージを受信したとき、新入者ノード２０６は、一実施の形態により以下を実行する。
１．次のａ〜ｃとともにブートストラップメンバーシップを生成する。
ａ）決定論的に生成されたメンバーシップ識別
ｂ）同意提案者及び同意受容者の役割にある誘導者ノード２０４
ｃ）学習者の役割にある新入者ノード
２．Ｂ３７に示すように、メンバーシップを配置する。
３．Ｂ３８に示すように、ブートストラップメンバーシップを参照して決定論的な状態マシンを生成する。
４．Ｂ３９に示すように、ブートストラップメンバーシップアックメッセージを新入者ノード２０６に対して送信(beacon)する。
一実施の形態によれば、誘導者ノード２０４は、ブートストラップメンバーシップアックメッセージを受信すると、Ｂ４０に示すように、ブートストラップメンバーシップレディビーコンを無効にすべきである。
Ｄ．  新入者ノード及びロケーションの認知
【０１１６】
ブートストラップメンバーシップの配置に次いで、新入者ノード２０６は自身が気付くべきノードとロケーションを知らされる。これは、一実施の形態によれば、以下のプロセスを用いて達成される。
１．誘導者ノード２０４が、新入者ノード２０６が知らされるべきロケーション及びノードがどれかを決定するために導入タスクを調べる。
２．導入タスクが、この新入者ノード２０６のためにロケーションとノードのリストを返す。
３．誘導者ノード２０４が、決定論的な状態マシンに、ノードとロケーションのセットを提案する。
４．Ｂ４１に示すように同意が形成される場合、新入者ノード２０６は、Ｂ４２に示すように、知る必要のあるロケーション及びノードについて学習する。
５．新入者ノード２０６がノード及びロケーションについて学習することに続いて、導入プロセスが完了する。
Ｅ．  導入後タスク
【０１１７】
ノード及びロケーションの同意、すなわち導入プロセスの完了に続いて、導入タスク内に特定されるタスク設置を実行することが可能となる。これらのタスクは例えば、新たに導入されたノードを含む新しいメンバーシップを生成すること、既存のメンバーシップに参加すること（すなわち、既存のメンバーシップ内に新たに導入されたノードが含まれるように、メンバーシップの変更を実施する）、複製された実体の配置と同期を実施することを含むことができる。
【０１１８】
図１０は、実施の形態が実行され得るコンピューターシステム１０００のブロック図を示す。コンピューターシステム１０００は、情報を通信するためのバス１００１又は他の通信メカニズムと、情報を処理するためにバス１００１と結合する１つ以上のプロセッサ１００２とを含み得る。コンピューターシステム１０００はさらに、情報と、プロセッサ１００２によって実行される指示とを記憶するためにバス１００１と結合するランダムアクセスメモリ（ＲＡＭ）又は他の動的な記憶装置１００４（メインメモリと参照される）を含み得る。メインメモリ１００４はまた、プロセッサ１００２による指示の実行の間、一時的な変数や他の中間情報を記憶するためにも使用され得る。コンピューターシステム１０００はまた、プロセッサ１００２のための情報及び指示を記憶するためにバス１００１と結合するリードオンリーメモリ（ＲＯＭ）及び／又は他の静的な記憶装置１００６も含み得る。例えば磁器ディスクやフラッシュメモリのようなデータ記憶装置１００７が、情報と指示を記憶するためにバス１００１に結合されていてもよい。コンピューターシステム１０００はまた、コンピューターのユーザに対して情報を表示するために、ディスプレイ装置１０１０とバス１００１を介して結合されていてもよい。英数字や他のキーを含む英数字入力装置１０２２が、プロセッサ１００２に対する情報の伝達と命令選択のためにバス１００１に結合されていてもよい。他のタイプのユーザ入力装置は、例えばマウス、トラックボール、カーソル指示キーのような、プロセッサ１００２に対する指示情報の伝達と命令選択のため、かつ、ディスプレイ１０２１におけるカーソルの動きをコントロールするためのカーソルコントロール１０２３である。コンピューターシステム１０００は、コミュニケーション装置（例えば、モデムやＮＩＣ）を介して、ネットワーク１０２６及び分散型コンピューターシステムの１つ以上のノードと結合され得る。
【０１１９】
実施の形態は、コンピューターシステムの使用、及び／又は、分散型コンピューターシステムにノードを導入する複数のそのようなコンピューターシステムに関連する。一実施の形態によれば、ここに記載された方法とシステムは、１つ以上のコンピューターシステム１０００により、メモリ１００４内に含まれる一連の指示を実行するプロセッサ１００２に応じて提供され得る。そのような指示は、データ記憶装置１００７のようなもうひとつのコンピューター読み出し可能なメディアから、メモリ１００４内に読み出され得る。メモリ１００４に含まれる一連の指示の実行は、プロセッサ１００２がここに記述したステップを実施し、機能を有する原因となる。代替の実施の形態では、実施の形態を実行するために、ソフトウェア命令に代えて、又は、ソフトウェア命令と組み合わせて、ハード・ワイヤードの回路が使用され得る。したがって、実施の形態は、ハードウェア回路とソフトウェアの特定の組み合わせに限定されない。実際、任意の適切なコンピューターシステムがここに記述された機能を実行し得ることは、当業者によって理解されるはずである。コンピューターシステムは、望ましい機能を実行するために動作する１又は複数のマイクロプロセッサを含み得る。一実施の形態では、１つのマイクロプロセッサ又は複数ののマイクロプロセッサによって実行された命令は、マイクロプロセッサにここに記述されたステップを実行させる働きをする。命令は、任意のコンピューター読み出し可能なメディアに記憶されてよい。一実施の形態では、マイクロプロセッサの外側にある、若しくは、マイクロプロセッサに組み込まれた不揮発性の半導体メモリに記憶され得る。他の実施の形態では、命令はディスクに記憶され、マイクロプロセッサによって実行される前に揮発性の半導体メモリに読み込まれ得る。
【０１２０】
開示のいくつかの実施の形態を記述したが、これらの実施の形態はほんの一例として表現されたものであり、開示の範囲を限定することを目的とするものではない。実際、ここに記述された新規な方法、装置、及びシステムは、多様な他の形式に具体化され得る。さらに、ここに記述された方法及び装置の形式において、多様な省略、置換、変更が、開示の精神から離れることなく、実施され得る。添付の請求項及びその等価物は、開示の範囲及び精神に含まれるように、そのような形式又は変更をカバーすることを意図したものである。例えば当業者は、多様な実施の形態において、実際の物理的及び論理的構造が図面に示したものと異なり得ることを理解するであろう。実施の形態によっては、上記の例の中に記述したいくつかのステップが除去される可能性があり、また、他のステップが加えられる可能性がある。また、上で開示した特定の実施の形態の特徴及び属性は、追加の実施の形態を形作るために、異なる方法で混ぜ合わせられ得る。ここでいう追加の実施の形態はすべて、本開示の範囲に含まれる。本開示は、いくつかの実施の形態とアプリケーションを提供するけれども、当業者にとって明らかであり、ここで説明したすべての特徴と利益は提供しない実施の形態を含む他の実施の形態もまた、本開示の範囲内にある。したがって、本開示の範囲は、添付の請求項を参照することによってのみ定義されることが予定されたものである。
【図１】
0006342425.tif 000002
【図２】
0006342425.tif 000003
【図３】
0006342425.tif 000004
【図４】
0006342425.tif 000005
【図５】
0006342425.tif 000006
【図６】
0006342425.tif 000007
【図７】
0006342425.tif 000008
【図８】
0006342425.tif 000009
【図９】
0006342425.tif 000010
【図１０】
0006342425.tif 000011