(57)【特許請求の範囲】
【請求項１】
複数のステートマシンと、複数のプロセスと、アグリーメント／コーディネーションエンジンとを実行するサーバ群を含むコンピュータネットワークにおいて前記サーバ群により実行される方法であって、
前記複数のプロセスは、少なくとも１つのプロポーザー、少なくとも１つのアクセプター、及び少なくとも１つのラーナーを含み、
前記サーバ群は、前記アグリーメント／コーディネーションエンジンによって生成され、順序付けられた複数のアグリーメントからなる第１のセットによって特定される順序で前記複数のアグリーメントを実行し、
前記サーバ群は、第１のステートマシンを含む前記複数のステートマシンの少なくとも一部、前記複数のプロセスの一部、及び、前記第１のセットを、同じステートを有するステートマシンのグループである複数のメンバシップの中の第１のメンバシップに対応付けて管理し、
前記アグリーメント／コーディネーションエンジンは、前記第１のメンバシップに属する前記プロポーザーから前記アグリーメント／コーディネーションエンジンに対して提案され、その後、前記第１のメンバシップに属する１以上の前記アクセプターの過半数により同意された提案を前記第１のセット内に一連のアグリーメントの１つとして組み入れるよう構成され、
前記方法は、
前記第１のメンバシップに属する１以上の前記ラーナーのそれぞれが前記第１のセット内の一連のアグリーメントを順に処理することにより、前記第１のメンバシップに属する前記複数のステートマシンを一貫性のある状態に維持するステップと、
前記第１のステートマシンのメンバシップ変更についてのアグリーメントである第１のアグリーメントが前記第１のセット内に含まれていた場合に、前記第１のメンバシップに属する前記ラーナーが前記第１のアグリーメントを実行することにより、前記第１のステートマシンのメンバシップを変更するステップとを含み、
前記アグリーメント／コーディネーションエンジンは、前記第１のアグリーメントが実行されている間にも、前記プロポーザーからの提案を受け付けるよう構成される、
方法。
【請求項２】
前記第１のセット内のアグリーメントにより、前記第１のメンバシップに対応付けて管理される複数のプロセスを変更するステップをさらに含み、
前記複数のプロセスを変更するステップは、前記複数のプロセスのうちの少なくとも１つの役割を変更することを含む、
請求項１に記載の方法。
【請求項３】
前記役割を変更することは、前記複数のプロセスのうちの少なくとも１つの役割を、プロポーザー、アクセプター、及びラーナーのうちの１つに変更することを含む、
請求項２に記載の方法。
【請求項４】
前記複数のプロセスを変更するステップは、前記複数のプロセスの数を変更すること、及び、前記第１のメンバシップに対応付けて管理されるすべてのプロセスを変更することのうちの１つを含む、
請求項２に記載の方法。
【請求項５】
前記複数のステートマシンの各々において、前記第１のセットに含まれるアグリーメントを受信するステップ、
をさらに含む請求項１に記載の方法。
【請求項６】
前記受信するステップは、非同期に、かつ、前記第１のセットによって定められた順序に反して、処理についての前記アグリーメントを受信することを含む、
請求項５に記載の方法。
【請求項７】
前記第１のセットは、前記第１のメンバシップに対応付けて管理される複数のプロセスを変更することについての少なくとも１つのアグリーメントを含む、
請求項１に記載の方法。
【請求項８】
前記複数のプロセスを変更するステップは、前記第１のセットから学習する既存のラーナーに影響を与えることなく、前記複数のプロセスにラーナーを追加することを含む、
請求項２に記載の方法。
【請求項９】
前記複数のプロセスに対する変更が完了した後、追加された前記ラーナーのアプリケーション状態を同期させるステップ、
をさらに含む請求項８に記載の方法。
【請求項１０】
複数のステートマシンと、複数のプロセスと、アグリーメント／コーディネーションエンジンとを実行するサーバ群を含むコンピュータネットワークにおいて前記サーバ群により実行される方法であって、
前記複数のプロセスは、少なくとも１つのプロポーザー、少なくとも１つのアクセプター、及び少なくとも１つのラーナーを含み、
前記サーバ群は、前記アグリーメント／コーディネーションエンジンによって生成され、順序付けられた複数のアグリーメントからなる第１のセットによって特定される順序で前記複数のアグリーメントを実行し、
前記サーバ群は、第１のステートマシンを含む前記複数のステートマシンの少なくとも一部、前記複数のプロセスの一部、及び、前記第１のセットを、同じステートを有するステートマシンのグループである複数のメンバシップの中の第１のメンバシップに対応付けて管理し、
前記アグリーメント／コーディネーションエンジンは、前記第１のメンバシップに属する前記プロポーザーから前記アグリーメント／コーディネーションエンジンに対して提案され、その後、前記第１のメンバシップに属する１以上の前記アクセプターの過半数により同意された提案を前記第１のセット内に一連のアグリーメントの１つとして組み入れるよう構成され、
前記方法は、
前記第１のメンバシップに属する１以上の前記ラーナーのそれぞれが前記第１のセット内の一連のアグリーメントを順に処理するステップと、
前記アグリーメント／コーディネーションエンジンが、前記第１のメンバシップに属する前記プロポーザーから、前記第１のステートマシンのメンバシップを前記第１のメンバシップから前記複数のメンバシップの中の第２のメンバシップに変更することについての提案である第１の提案を受信し、該第１の提案を前記第１のセット内に第１のアグリーメントとして組み入れるステップと、を含み、
前記第１のメンバシップに属する前記ラーナーは、前記第１のセット内の一連のアグリーメントを順に処理している間に前記第１のアグリーメントの処理順が到来した場合に、前記第１のアグリーメントを処理するよう構成される、
方法。
【請求項１１】
前記第１のステートマシンが、前記第１のメンバシップに属するプロセスによってアグリーメントが処理されている間に、前記第２のメンバシップに属するプロセス上で処理されるべき第２のアグリーメントを受信するステップ、
をさらに含む請求項１０に記載の方法。
【請求項１２】
前記第１のステートマシンが、受信した前記第２のアグリーメントを、メンバシップ変更についてのアグリーメントが処理された後に処理するために、永続的に記憶するステップ、
をさらに含む請求項１１に記載の方法。
【請求項１３】
前記第２のメンバシップに属する前記ラーナーが、前記第２のメンバシップに属する複数のアグリーメントからなる第２のセット内の一連のアグリーメントを順に処理している間に前記第２のアグリーメントの処理順が到来した場合に、前記第２のアグリーメントを処理するステップ、
をさらに含む請求項１２に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
複製されたステートマシンを提供するプロセスである分散コンピューティングシステムにおいては、ステートマシンの動作に関与するプロセスの集合へのステートマシンの関連付けを変更することが望ましい場合がある。
【図面の簡単な説明】
【０００２】
図１は、各複製されたステートマシンのアグリーメントハンドラにアグリーメントを配信するアグリーメント／コーディネーションエンジンを示す一実施形態によるブロック図である。
【０００３】
図２は、一実施形態によるメンバシップ変更がない場合におけるアグリーメントのハンドリングを示す図である。
【０００４】
図３は、一実施形態による動的なメンバシップ変更を示すフローチャートである。
【０００５】
図４は、一実施形態による方法を示すフローチャートである。
【０００６】
図５は、一実施形態による方法のさらなる側面を示すフローチャートである。
【０００７】
図６は、一実施形態による動的なメンバシップの側面を実施可能なコンピューティングデバイスのブロック図である。
【発明を実施するための形態】
【０００８】
分散システム：分散システムは、空間的に分離可能であり、かつ、メッセージの交換によって互いに通信し得る区別可能なプロセスの集合を含む。
【０００９】
複製されたステートマシン：複製されたステートマシンのアプローチは、サーバを複製し、かつ、クライアントのサーバレプリカとの相互作用を調整することにより、フォールトトレラントなサービスを実行するための方法である。これらのステートマシンは、ステートマシンの状態が全てのラーナーにおいて同様に進展することとなるよう「複製される」。１つのサーバの複数のレプリカが分散システムの別個のプロセッサによって実行され、クライアントのこれらのレプリカとの相互作用を調整するためにプロトコルが用いられる。複製されたステートマシンの１つの例及び実装は、決定論的な方法でその状態を実行する決定論的なステートマシンである。
【００１０】
一連のアグリーメント：ステートマシンアプローチにおいては、リクエストは、一貫性のある順序で、一度に１つずつステートマシンにより処理される。したがって、ステートマシンの複数のレプリカが互いに一致しているためには、同一のコマンドシーケンスが各レプリカ上で同じ順序で確実に再生されるよう、同意された一連のコマンドが必要となる。一実施形態によれば、１つの複製されたステートマシンに対する複数のアグリーメントの処理及び配信は、別個の待ち行列の実行を通じて、その提案するという側面から切り離され得る。そして、一連のアグリーメントは、出力提案シーケンスと呼ばれる概念を通じて、複製されたステートマシンに配信され得る。一実施形態によれば、出力提案シーケンスによってソフトウェアアプリケーション（例えば、ソフトウェアバージョンの制御システム）に配信された一連のアグリーメントは、（一実施形態によれば単調に増加する整数として実装され得る）キーｋｌａｓｔ＿ｏｕｔｐｕｔによって全体的に順序付けられ得る。
【００１１】
分散されたアグリーメント／コーディネーションエンジン：一実施形態では、ステートマシンの一貫したレプリカを達成するために必要な一連のアグリーメントを生成するために、１つのアグリーメント／コーディネーションエンジンが必要とされる。参照によりその全体が本明細書に組み込まれる２００８年２月１３日に出願された同一出願人による同時係属中の米国特許出願第１２／０６９，９８６号には、一例によるコーディネーションエンジンが記載されている。しかしながら、一実施形態によれば、動的なメンバシップのために使用されるコーディネーションエンジンは、アグリーメントが成立した複製されたステートマシンの識別子「ｄ」と、アグリーメントが成立したメンバシップ「ｍ」の識別子と、アグリーメントのユニークなキー「ｋ」とを含むユニークなアグリーメントの識別子をサポートし得る。一実施形態によれば、ユニークなキー「ｋ」は、一連のアグリーメントの中のそのアグリーメントによって占有される位置に対応する。したがって、一実施形態によれば、ｄ、ｍ、及びｋは、メンバシップｍ及びアグリーメントキーｋの下、複製されたステートマシンｄのためにアグリーメントエンジンによって行われた各アグリーメントを一意的に識別することを可能にする。本明細書では、３つの部分からなる＜ｄ，ｍ，ｋ＞により、アグリーメントの識別子を表す。
【００１２】
非ブロッキング：本明細書において、「非ブロッキング」という用語は、あるプロセスのセットに変更が加えられている間に、そのセットが完全に又は部分的に利用可能であることを意味する。
【００１３】
プロポーザー：一実施形態によれば、プロポーザーは、複製されたステートマシンの将来の状態への変更を提案する（すなわち、申し出をする）ように構成され、かつ、該提案を可能にするプロセスである。複製されたソフトウェアのバージョン制御システムを含む実施形態においては、プロポーザーは、システムによって管理されるソフトウェアレポジトリに変更を加えることが許可されたプロセスであり得る。
【００１４】
アクセプター：一実施形態によれば、アクセプターは、複数のプロポーザーによって行われた複数の提案の順序の決定に参加するように構成されたプロセスである。一実施形態によれば、過半数のアクセプターにより、ある提案が一連のアグリーメントの中で特定の場所を取ると決定された場合にのみ、その提案は同意されたものとなる。一実施形態によれば、アクセプターは、アグリーメントの順序を決定することにのみ参加するように構成され、アグリーメントの根本的な内容について理由付けをせず、また、関心を持たない（本明細書で説明するように、アグリーメントの価値は、アグリーメント／コーディネーションエンジンに対して不明瞭である）。アクセプターは、アプリケーションに依存しない実体として構成され得る。
【００１５】
ラーナー：一実施形態によれば、ラーナーは、プロポーザーとアクセプターとの間でなされた複数のアグリーメントを学習し、それらの出力提案シーケンスを通じて、アプリケーションに対し、決定論的順序でアグリーメントを適用する。複製されたソフトウェアのバージョン制御システムを備える実施形態においては、ラーナーは、システムによって管理されるソフトウェアレポジトリのレプリカを提供するように構成されたプロセスを備える。
【００１６】
メンバシップ：メンバシップは、複数のステートマシンのうち同じステートを有するステートマシンのグループであって、１組のノード又はプロセスを特定するとともに、特定された1組のノードの中でそれぞれが果たす役割を特定する。一実施形態によれば、実施形態による動的メンバシップにおける使用に適したメンバシップは、１組のアクセプターと、１組のプロポーザーと、１組のラーナーとを含み得る。
【００１７】
ここでは、非ブロッキングで（すなわち、システムが常に利用可能であり）、融通性があり（メンバシップに対して、任意のプロセスを削除及び追加することができ）、決定論的な（すべてのノードにおいて、複製されたステートマシンの動作中の同じポイントで同じ変更が生じる）メンバシップの変更を可能にする複製されたステートマシンの動的なメンバシップ変更を、分散されたコーディネーションエンジンにより非同期かつ順序が乱れた状態でプロセスに対するアグリーメントが配送されたとしても、ステートマシンにヌル動作を提案するなどのようなスループットを低下させる手段に頼ることなく可能とし、達成するための実施形態を述べる。メンバシップ変更とは、ステートマシンに関連付けられた現在のメンバシップを別のメンバシップに移行させることをいう。
【００１８】
したがって、一実施形態は、動的なメンバシップ変更と、ノードへの分散コンピューティング環境における役割の選択的な関連付けとをサポートすることにより、上述した米国特許出願第１２/０６９，９８６号に記載され、かつ、クレームされているもののような一連のアグリーメントを強化する。一実施形態によれば、それぞれの複製されたステートマシンに対して、各メンバシップの一連のアグリーメントが永続的に記録されることを可能にする永続的なストアと同様に、アグリーメントの識別子が提供される。一実施形態によれば、永続的ストアは、アグリーメントが成立したメンバシップの識別子を、アグリーメントのキーｋ及び関連する値ｅの組(tuple)である複数のキーととともにマッピングする。したがって、一実施形態によれば、各複製されたステートマシンのためのアグリーメントハンドラは、複数のメンバシップのために一度に複数の一連のアグリーメントを維持し、その一連のアグリーメントの中の適切なポイントにおいて、それらの間での切り替えを行うように構成され得る。
提案、アグリーメント、及びアグリーメントのハンドリング
【００１９】
動的なメンバシップの一実施形態の構成要素、及び、そのような構成要素が相互作用する方法について詳しく説明する前に、提案に含まれる情報、提案がアグリーメントになり得る方法、及び、アグリーメントハンドラがアグリーメントを処理する方法を含む提案の概念について説明する。これらの概念を手に入れたうえで、非ブロッキングで、柔軟かつ決定論的な動的メンバシップを実現するための実施形態が説明されるであろう。一実施形態によれば、動的メンバシップの機能は、実施形態が1つの実施例に限定されないのと同様、複数の（例えば、１０００の）複製されたステートマシンにわたって並列に実装されてもよい。上述したように、一実施形態によれば、この並列性は、各アグリーメントがアグリーメントの識別子＜ｄ、ｍ、ｋ＞を含むことによって達成され得る。すなわち、複製されたステートマシンｄは、アグリーメントが成立したメンバシップｍと、そのメンバシップのためのアグリーメントのユニークなキーｋとに互いに関連付けられる。
【００２０】
一実施形態によれば、１つの複製されたステートマシンに対する提案、アグリーメント、及びアグリーメントのハンドリングメカニズムは、以下で説明するように実施されることができ、多数の複製されたステートマシンのうちのいずれかに対し、必要に応じて繰り返され得る。以下の実施形態は、１つの複製されたステートマシンに関して記述されたものである。すなわち、トリプレット＜ｄ，ｍ，ｋ＞におけるｄは省略される。
【００２１】
最初に、複製されたステートマシン（プロポーザー）の状態に対する変化を提案することを許可されたプロセスｎが提案ｅを構築し、それを複製されたステートマシンｄに提出する。複製されたステートマシンｄは、何らかの形で提案ｅを解釈する必要はない。すなわち、提案ｅは、ｄに対して不明瞭であってよい。
複製されたステートマシンｄは、アグリーメントの識別子＜ｄ，ｍ，ｋ＞を以下のように構築する。
ｄはそれ自体の識別子である。
ｍは現在関連しているメンバシップの識別子である。
ｋは次に使用可能なキーであり、例えば、次のうちの最大のものよりも1大きい自然数である。
ａ．到達したアグリーメント＜ｄ，ｍ，ｘ＞の最大のｘ
ｂ．ｄがメンバシップｍの下で提案したアグリーメント＜ｄ，ｍ，ｙ＞の最大のｙ。
【００２２】
提案ｅは、一旦構成されると、ステートマシンによって、メンバシップのキー及び値ｅにしたがって提案を格納するデータ構造内に永続的に記憶される。すなわち、各提案は、トリプル＜ｍ，ｋ，ｅ＞を用いて一意的に識別され得る。
【００２３】
提案は、一旦記憶されると、＜ｄ，ｍ，ｋ＞によって識別されるアグリーメントのインスタンスに対して提出され得る。
【００２４】
提案が一旦、＜ｄ，ｍ，ｋ＞によって識別されるアグリーメントのインスタンスに対して提出されると、メンバシップｍは、アグリーメント／コーディネーションエンジンを介して、その提案が一連のアグリーメントの中でｋ番目の位置を占めるアグリーメントであるべきか否かを同意する。提案が同意される場合、それはアグリーメント識別子＜ｄ，ｍ，ｋ＞のアグリーメントとなり、アグリーメント／コーディネーションエンジンによって、複製されたステートマシンｄのアグリーメントハンドラに対して配送され、そして（最終的には）ｄのための出力提案シーケンスに対して配送され得る。図１には、３つの複製されたステートマシン、すなわちＡ、Ｂ、及びＣに関して、このシーケンスを示している。実際、図１は、各複製されたステートマシンのアグリーメントハンドラにアグリーメントを配送するアグリーメント／コーディネーションエンジン１０２を示すブロック図である。各複製されたステートマシンは、それぞれの出力提案シーケンスへの配信のためにアグリーメントを処理し、整理する。図示するように、アグリーメントは、アグリーメント／コーディネーションエンジン１０２によって、複製されたステートマシンＡ（ｄ＝Ａ）１０４、複製されたステートマシンＢ（ｄ＝Ｂ）１０６、及び、複製されたステートマシンＣ（ｄ＝Ｃ）１０８に配送され、これらは、キーｋｌａｓｔ＿ｏｕｔｐｕｔにしたがって順序付けされたアグリーメントを、それぞれの出力提案シーケンス１１０，１１２，及び１１４に配送するために処理し、整理する。
【００２５】
同意されたイベントのハンドラに対する重複は、例えば、アグリーメント／コーディネーションエンジン１０２及びアグリーメントハンドラ１０４，１０６，１０８の間でトランザクションコミットを共有することにより回避され得る（他の方法によっても、同意されたイベントの複製は同様に回避され得るが）。しかしながら、分散プロセスは自律的かつ非同期的であり、アグリーメントプロセスに含まれる複数のプロセスは異なるレートで実行され得るので、アグリーメント／コーディネーションエンジン１０２は、アグリーメントハンドラ１０４，１０６，及び１０８に対し順不同でアグリーメントを配送するように構成されてもよい。したがって、複製されたステートマシンのアグリーメントハンドラ１０４，１０６，及び１０８は、アグリーメントハンドラ１０４，１０６，及び１０８とそれぞれの出力提案シーケンス１１０，１１２，及び１１４との間を仲介するために出力提案シーケンスに対して最後に与えられたｋの値として定義され得る変数ｋｌａｓｔ＿ｏｕｔｐｕｔを維持するように構成され得る。
メンバシップ変更のないアグリーメントハンドリング
【００２６】
アグリーメントハンドリングは、いかなるアクションを取るべきかを、観測されたアグリーメントのキーｋに依拠して決定するための論理を備えることができる。以下、アグリーメントが処理され得る方法についての一実施形態による論理について、説明する。
【００２７】
出力提案シーケンスに対して配信されたメンバシップｍのために全体的に順序付けられたアグリーメントのセットは、アグリーメントのセットＡｍ＝｛ａ１，  ...  ，ａｋ｝として表現され得る。ただし、アグリーメントキーｋは、一実施形態によれば、自然数のセット（すなわち、｛∀ｋ：ｋ∈Ｎ｝）に属し得る。
【００２８】
出力提案シーケンス内の各アグリーメントａｋは、ｄが複製されたステートマシンの識別子であり、かつ、ｍがアグリーメントの成立したメンバシップの識別子であるとした場合、識別子＜ｄ，ｍ，ｋ＞を有する。しかしながら、一実施形態によれば、アグリーメントエンジンは、複製されたステートマシンのアグリーメントハンドラに対し非決定論的な順序でアグリーメントを配信することができ、したがってアグリーメントハンドラは、出力提案シーケンス上に正しい順序でアグリーメントを配置することについて責任を有し得る。これを行うため、アグリーメントハンドラは、一実施形態によれば、アグリーメント／コーディネーションエンジンから配信されたアグリーメントを観測したときにアグリーメントのキーｋを抽出し、以下の論理にしたがってそれを処理することができる。
ｋ＜ｋｌａｓｔ＿ｏｕｔｐｕｔの場合、この現在のシーケンスに対して、アグリーメントは無効である。
ｋ＝ｋｌａｓｔ＿ｏｕｔｐｕｔの場合、アグリーメントは、処理の準備ができているものとしてマークされる。
ｋ＞ｋｌａｓｔ＿ｏｕｔｐｕｔの場合、アグリーメントは、出力提案シーケンスへの後の配信のために（永続的に）待ち行列に入れられる。
【００２９】
図２は、一実施形態による、メンバシップ変更を想定しないアグリーメントハンドリングを示す図である。この中に示されるように、アグリーメントハンドリングの処理は２０２で開始されることができ、するとアグリーメントハンドラは、２０４で次のアグリーメント（すなわち、｛ａ１，  ...  ，ａｋ｝のうちの１つ）を観測し、特徴付けることができる。この特徴付けは、一実施形態によれば、受信したアグリーメントキーｋを現在のアグリーメントキーすなわちｋｌａｓｔ＿ｏｕｔｐｕｔと比較した結果に基づくことができる。もし受信したキーｋが２０８に示されるように最後の出力よりも遅れたものであった場合、現在の同期キーｋｌａｓｔ＿ｏｕｔｐｕｔよりも古いものであるので、２１０に示されるように事実上無効となる。もし受信したキーが２１２に示されるように現在のキーに位置している（等しい）場合、２１４に示すように、出力提案シーケンス内にキューイングされる。しかしながら、２１６に示すように、もし受信したキーｋが最後の出力よりも進んでいる（現在のキーｋｌａｓｔ＿ｏｕｔｐｕｔよりも大きい）場合、そのキーｋが現在のキーｋｌａｓｔ＿ｏｕｔｐｕｔに等しくなり、出力提案シーケンスにキューイングできるようになるときまで、２１８で示すように、単にアグリーメントシーケンス内にキューイングされ得る。プロセスはその後、２０２に戻り、次のアグリーメントの受信を待つことができる。
動的メンバシップを用いるアグリーメントハンドリング
【００３０】
一実施形態によれば、同意された値は、アグリーメント／コーディネーションエンジン１０２に対して不明瞭である。したがって、一実施形態によれば、複製されたステートマシンのメンバシップを変更することについてのアグリーメントは「ありふれたアグリーメント」であり、特定のメンバシップの下で生成された一連のアグリーメント内のどこでも発生し得る。したがって、メンバシップ変更を実施するために、特定の型式のステートマシン又はハンドラは必要とされない。しかしながら、一連のアグリーメント及びその構成アグリーメントは、それらが生じるメンバシップにのみ関連していることに注意が必要である。
【００３１】
したがって、上記に鑑みると、アグリーメントは、非同期に受信されたり、順序が乱れた状態で受信されたりする可能性があるので、プロセスは、同意されたメンバシップ変更のキーｋより大きいアグリーメントキーｋ'を有する提案を構築し、アグリーメントにまで至る可能性がある。メンバシップ変更のキーｋよりも大きいアグリーメントキーを有するアグリーメントのセット（すなわち｛∃ａｋ'∈Ａ：ｋ'＞ｋ｝で定義されるアグリーメントのセット）は、それ故、アグリーメントａｋの処理に続く無効なアグリーメントとなる。それらは、ａｋが処理された後の複製されたステートマシンに関連付けられていないメンバシップの下で作られたものであるからである。
【００３２】
一実施形態によれば、アグリーメントは、複製されたステートマシンのアグリーメントハンドラに非決定論的な順序で配信され得るので、次のメンバシップ（及び、その後のメンバシップ等）の下でなされたアグリーメントが、メンバシップ自体が変更になる前にアグリーメントハンドラに提供される可能性がある。すなわち、新たなメンバシップの下で行われた１つまたはそれ以上のアグリーメントが、古いメンバシップの下でなされたアグリーメントを未だ処理中であるアグリーメントハンドラに配送される可能性がある。
【００３３】
上で詳述したように、一実施形態によれば、アグリーメントエンジンは、同じ複製されたステートマシンに対し、同じメンバシップｍについての同じシーケンス番号ｋを有する複製マシンｄに関する２つのアグリーメントが発行されないことを保証することができる。すなわち、アグリーメントの識別子＜ｄ，ｍ，ｋ＞は、ユニークでなければならない。
【００３４】
一実施形態によれば、決定論的ステートマシンの決定論的動作は、その決定論的ステートマシンが自身の現在のメンバシップの下で同意された提案のみを出力する場合にのみ達成され得るので、上記の望ましい性質は、ｋ'（＞ｋ）を有する現在のメンバシップに対して成立しかつ観測されたすべてのアグリーメントを無効にすることによって達成され得る。かくして、古いメンバシップの下でアグリーメントが行われる。このような提案が同意されるためには、新たなメンバシップｍ'の下で再提案されかつ同意されなければならない。しかしながら、そのような提案（ｋ'（＞ｋ）を有する現在のメンバシップｍに対して成立しかつ観察されたアグリーメント）が再提案されなければならないわけではない。もしそのような提案が新たなメンバシップｍ'の下で再提案されない場合、それらが同意されることはなく、したがって無視され得る。
【００３５】
一実施形態によれば、アグリーメントは、異なるプロセスにより異なる速度でなされ得るため、メンバシップ変更についてのアグリーメントが他のプロセスに到着する前に、次の又は新たなメンバシップ（ｍ'）の下で行われるイベントがそのプロセスに到達する可能性がある。したがって、アグリーメントハンドラは、ｍ'の下でなされたアグリーメントを記憶するように構成され得る。このようにして、例えｍ'の下で成立したアグリーメントを受信したプロセスがいつ（ｍからｍ'への）メンバシップ変更が生じるかを（まだ）知らないとしても、メンバシップ変更が同意された後に、出力提案シーケンスに対してそのアグリーメントを配信することが可能になる。
【００３６】
一実施形態によれば、これは、各複製状態のアグリーメントハンドラにより、その下でアグリーメントのキーｋ及び関連の値ｅの組であるキーを有するアグリーメントが成立したメンバシップ識別子の写像であるストア内にアグリーメントを存続させることによって達成され得る。このように、各複製されたステートマシンのアグリーメントハンドラは、複数のメンバシップに対する複数の一連のアグリーメントを同時に維持することができる。
動的メンバシップの形式論
【００３７】
一実施形態によれば、アグリーメントエンジンは、アグリーメントハンドラに対する一連のアグリーメント内における位置ｋにおいて複製されたステートマシンｄのメンバシップをｍからｍ'に変更するために、識別子＜ｄ，ｍ，ｋ＞を有するアグリーメントを配信する。アグリーメントハンドラは、配信されたアグリーメントを、一連のアグリーメント内の正しい位置において処理する。一実施形態によれば、
・各プロセスは、メンバシップ変更提案のキーよりも大きいアグリーメントキーを有するアグリーメントのセット（すなわち｛∃ａｋ'∈Ａ：ｋ'＞ｋ｝を満たすアグリーメントのセット）を無効にし、それらのアグリーメントは、再提案が一度だけ発生することを確実にするため、元のプロポーザーによって、ｍ'に対して再提案され得る。もし元のプロポーザーが新たなメンバシップｍ'においてプロポーザーの役割を有さない場合、一実施形態によれば、これらのアグリーメントは廃棄されることができ、他のプロポーザーによっては再提案されない。
・もしプロセスが新たなメンバシップｍ'においてラーナーではないならば、そのプロセスは、複製されたステートマシンｄ（出力提案シーケンスを含む。したがって、そのアプリケーションは新たなアグリーメントを学習できなくなる）のアンインストールをも行うべきである。
・もしプロセスが新たなメンバシップｍ'においてアクセプターではない場合、そのプロセスはもはや複製されたステートマシンの動作に参加すべきでなく、それに対するすべての参照を削除するべきである。
【００３８】
この挙動を図３に示す。図３は、一実施形態による動的メンバシップを含むように図２を拡張したものである。一実施形態によれば、プロポーザーは、動的メンバシップが正しく機能するためには常にラーナーでなければならない、という要件が強制されることに留意が必要である。ラーナーは、上記のように、プロポーザーとアクセプターとの間でなされたアグリーメントを学び、そのアグリーメントを決定論的順序で、それらの出力提案書シーケンスを通じてアプリケーションに適用する。複製されたソフトウェアのバージョン制御システムを含む実施形態では、ラーナーは例えば、システムによって管理されるソフトウェアレポジトリのレプリカをホストするように構成されたプロセスを含むことができる。図３に示すように、アグリーメントのプロポーザーがラーナーであると仮定すると、３０２でアグリーメントハンドリングプロセスが開始し、アグリーメントハンドラは、３０４で次のアグリーメント（すなわち｛ａ１，  ...  ，ａｋ｝のうちの１つ）を観測して特徴付けることができる。この特徴付けは、一実施形態によれば、受信したアグリーメントキーｋを現在のアグリーメントキーすなわちｋｌａｓｔ＿ｏｕｔｐｕｔと比較した結果に基づくことができる。もし受信したキーｋが３０８に示されるように最後の出力よりも遅れたものであった場合、現在の同期キーｋｌａｓｔ＿ｏｕｔｐｕｔよりも古いものであるので、３１０に示されるように事実上無効となる。もし受信したキーｋが３１２に示されるように最後の出力よりも進んでいる（現在のキーｋｌａｓｔ＿ｏｕｔｐｕｔよりも大きい）場合、そのキーｋが現在のキーｋｌａｓｔ＿ｏｕｔｐｕｔに等しくなり、出力提案シーケンスにキューイングできるようになるときまで、３１４で示すように、単にアグリーメントシーケンス内にキューイングされ得る。プロセスはその後、次のアグリーメントを待つために、３１０及び３１４から３０２に戻り得る。
【００３９】
しかしながら、もし受信したキーが３１６に示されるように現在のキーに位置している（等しい）場合、一実施形態によれば、３１８においてメンバシップの変更が行われたかどうかの判断が実施され得る。換言すれば、処理中のアグリーメントが成立したメンバシップが現在のメンバシップと同じメンバシップであるかどうかの判断が行われ得る。もしメンバシップの変更が行われていないならば（３１７のＮＯ分岐）、３２０に示されるように、アグリーメントは、ステートマシンの出力提案シーケンス内にキューイングされ得る。もしメンバシップ変更が実際にあったとしたならば（３１８のＹＥＳ分岐）、３２２に示されるように、検討中のアグリーメントを提案したプロセスが新たなメンバシップにおけるプロポーザーであるかどうかの判断が行われ得る。もしこのアグリーメントを提案したプロセスが新たなメンバシップにおけるプロポーザーであるならば（３２２のＹＥＳ分岐）、メンバシップが変化すると同時に、そのプロセスが実際に新たなメンバシップにおけるプロポーザーとなる。したがって、３２４に示すように、このステートマシンに関連するメンバシップは変更されると、このプロセス又はノードがこの新たなメンバシップの下でのプロポーザーであることから、３２６で示すように、このノード又はプロセスによって提案された全てのアグリーメントが新たなメンバシップの下で（古いメンバシップの下でそれらを提案し、新たなメンバシップにおいても引き続きプロポーザーであるプロセスによって）再提案され得る。この方法はその後、次のアグリーメントを観測するために３０２に戻り得る。
【００４０】
しかしながら、メンバシップ変更が行われ、検討中のアグリーメントを提案したプロセスが新たなメンバシップにおけるプロポーザーではない場合（３２２のＮＯ分岐）、（現在の、最近変更されたメンバシップとは異なる）以前のメンバシップの下でこのノードによって提案されたすべてのアグリーメントは、一実施形態によれば、３２８に示されるように破棄される。これらのアグリーメントのすべては、もはや現在のメンバシップではないメンバシップの下で提案されたものであるからである。その後、検討中のアグリーメントを提案したプロセスが新たなメンバシップにおいてプロポーザーでないことが決定された後、３３０において、新しいメンバシップにおいてそのプロセスがラーナーであるかどうかが判断され得る。もしそのプロセス又はノードが実際に新たなメンバシップにおけるラーナーであるならば、そのステートマシンに関連付けられたメンバシップが３２４に示されるように変更され、その後、この方法は３０２に戻り得る。このノードによって以前に提案されたアグリーメントは、（３２６において）再提案されない。これは、このノードが新たなアグリーメントの下でプロポーザーでないことが確立されたからである。もし評価中のアグリーメントを提案したプロセスが新たなメンバシップにおけるラーナーではなければ、一実施形態によれば、出力提案シーケンスは、もはや現在のメンバシップではないメンバシップのためのものであったことから、３３２に示されるようにアンインストールされ得る。したがって、対応する出力ステートマシンもまた、３３４で示すようにアンインストールされ得る。
【００４１】
この段階では、アグリーメントが、新たなメンバシップのメンバでもあるプロセス又はノードによって提案されたかどうかは分からない。そのようなことは３３６において判定されることができる。もしプロセスが実際に新たなメンバシップにおけるメンバであるならば（３３６のＹＥＳ分岐）、それは、このアグリーメントを提案したプロセスが新たなメンバシップにおけるアクセプターであることを意味し、３２４に示されるように、このステートマシンに関連付けられたメンバシップが新たなメンバシップに変更され得る。このノードは新たなメンバシップにおけるプロポーザーではないので、そのノードのアグリーメントが再提案されることはなく、本方法は、そのノードが次のアグリーメントを処理することを可能にするために３０２に戻り得る。しかしながら、処理中のアグリーメントを提案したプロセスが新たなメンバシップにおけるメンバではない場合、そのプロセスは、３３８に示されるように現在のメンバシップにおいてプロポーザーでなく、ラーナーでなく、アクセプターでない（プロポーザーによって行われた提案の順序の決定にアクセプターが参加することに留意されたい）ので、そのステートマシンに対する全ての参照が３４０において削除される。このノードは新たなメンバシップにおいて役割を有しないので、３４２で示すように、本方法はこのノードに関しては終了できる。
複製されたステートマシンに関連付けられたプロセスのセットを変更
【００４２】
一実施形態によれば、動的なメンバシッププロセスは、メンバシップ内の複製されたステートマシンに関連付けられたプロセスのセットの役割が変更となるか、または複製されたステートマシンに関連付けられたプロセスのセットが縮小又は拡大となるようなメンバシップ変更を可能にするように構成され得る。これは、プロセスが失敗するとき、一時的又は永久にオフラインとなって閉じられるとき、又は、分散システムの機能性強化や耐障害性ないしスループットの向上のために新たなプロセスが追加されるときに、プロセスをシステムから削除するために必要となり得る。したがって、メンバシップ変更が観測されるとき、観測しているプロセスは、アクセプターとして追加又は削除され、プロポーザーとして追加又は削除され、ラーナーとして追加又は削除され、新たなメンバシップのメンバから削除され得る。
【００４３】
一実施形態によれば、メンバシップ変更が、複製されたステートマシンによって認識される一連のアグリーメントにおける「もう1つのアグリーメント」であることに留意されたい。したがって、任意のプロポーザーは、メンバシップに関係のないアグリーメントだけでなく、アグリーメントを提案するために使用されるものと同じメカニズムを用いてメンバシップを変更するように構成されたアグリーメントを提案することができ、そのようなメンバシップ変更は、プロポーザーの役割から任意のプロセスを削除することができる。プロセス中に展開された複製されたステートマシンにそのような動的メンバシップ変更を実装するために、一実施形態によれば、プロポーザーの役割にある任意のプロセスはラーナーでもなければならず（すなわち、｛∀ｐ∈Ｐ:ｐ∈Ｌ｝）、ただし、Ｐはプロポーザーのセットに対応し、Ｌはラーナーのセットに対応する）、そうすることによって提案プロセスは、（もし同意されるなら／同意されるときに）メンバシップ変更を観測し、適切なアクションを講じることができる。しかしながら、一実施形態によれば、アクセプターはラーナー又はプロポーザーである必要がなく、ラーナーはプロポーザーである必要がないことに留意されたい。
【００４４】
したがって、実施形態による動的なメンバシップでの使用に適したメンバシップは、一組のアクセプターＡｃ、一組のプロポーザーＰ、及び一組のラーナーＬを含み得る（ｍ＝｛Ａｃ，Ｐ，Ｌ｝）。プロセスは１つ又はそれ以上の役割を果たし得ることから、メンバシップ内におけるプロセスの数は、グループ内においてユニークなプロセスの数（又は、Ａｃ、Ｐ、及びＬの組の交点の基数、すなわち｜Ａｃ∩Ｐ∩Ｌ｜）であり、メンバシップ変更を行うために、少なくとも１人のプロポーザーが存在しなければならない（したがって、プロポーザーの組は空であってはならず、「Ｐ≠空集合」は常に真でなければならない）。もしメンバシップ内にプロポーザーであるプロセスがいない場合、そのメンバシップ内には、メンバシップ変更を提案できるプロセスが存在しないことになる。一実施形態によれば、そのような変更はアグリーメント提案として処理されるからである。さらに、すべてがラーナー又はアクセプターであるメンバシップは有用ではない。何故なら、プロセスがどちらの役割又は両方の役割を有するとしても、受諾し、又は、出力提案シーケンスにキューイングするべき提案されたアグリーメントを1つも持たず、遊んでいる状態となるからである。
新規ラーナーの追加
【００４５】
メンバシップが変更されると、新たな役割にプロセスが割り当てられるのみならず、その役割に関連付けられるいくつかの状態、すなわち、そのメンバシップの下でなされた一連のアグリーメントのための出力提案シーケンスの現在値ｋｌａｓｔ＿ｏｕｔｐｕｔを交換し、同期する必要が生ずるため、異なるラーナーのセットを含むメンバシップへのメンバシップの変更は重要である。これは、新しいラーナーによって維持されるべき出力提案シーケンスが、複製されたステートマシンへのアグリーメントの出力を、シーケンス内の正しいポイント（これらの新しいプロセスをラーナーとして含むメンバシップ変更の直後のアグリーメント）から始まるように開始するために必要である。新たなラーナーにおけるアプリケーション状態を他のラーナーのそれと同期させることも必要となり得る。例えば、ソフトウェアバージョン制御システムの場合であれば、アプリケーション状態は、複製されたソフトウェアレポジトリの状態である。そのソフトウェアレポジトリの新たなレプリカが必要な場合（すなわち、新規ラーナーがメンバシップに追加されるべきである場合）、ソフトウェアレポジトリの状態もまた、変更を調整するために使用される複製されたステートマシンの状態と同期されなければならない。
【００４６】
したがって、以下では、複製されたステートマシンのメンバシップｍがｍ'に変更されるときに、メンバシップｍ'に1以上のラーナーを含む一組のラーナーＬ'を複製されたステートマシンｄに関連付けるプロセスが説明される。
【００４７】
重要なことは、一実施形態による下記の手順が、既存のラーナーのセットに対して非ブロッキングであることである。すなわち、新規ラーナーは、既存のセットに影響を与えることなくプロセスのセットに追加されることができ、それによって、新規ラーナーが追加される間にも、そのユーザのための中断を発生させずに、システムを連続して利用することが可能になる。このことは、例えば、新しいソフトウェアリポジトリサイトが一連のプロセスに追加された場合に、1つのロケーションで働いているシステムのユーザが影響を受けないことであるため、複製されたソフトウェアのバージョン制御システムなどの動的なメンバシップを使用する実装にとって大きなメリットとなる。一実施形態によれば、例えばファイルシステムデータのような複製されたステートマシンと関連付けられたアプリケーションを同期させるために既存のラーナーの１人が休止され得る点は、1つだけである。
新規ラーナーを追加するための手順
【００４８】
一実施形態によれば、分散コンピューティングシステム内においてプロセスのセットに新規ラーナーを追加する方法は、以下を備え得る。
１．  メンバシップｍ内のすべてのプロセスに複製されたステートマシンｄがインストールされていると仮定する。
２．  異なるラーナーＬ'のセットを含むメンバシップｍ'は、ｍ'内のすべてのプロセスにおいて展開されると仮定する。このようなメンバシップは、例えば動的なメンバシップ変更の展開のために、上で示されかつ記載されたように展開され得る。
３．  複製されたステートマシンｄは、すべての新規ラーナーにおいて展開され（例えば、組｛∀ｌ∈Ｌ'：ｌ∈Ｌ｝におけるすべてのラーナー）、さらにｄは、新規ラーナーであるそれらのプロセスにおいてｍ'に関連付けられる。すべての新規ラーナーは、それらを含まないメンバシップ、例えばメンバシップ変更に先立って複製されたステートマシンに関連付けられたメンバシップであるｍなどのメンバシップについて、知る必要がないことに留意が必要である。
４．  ｄがこの新規ラーナーのセットに展開されると、複製されたステートマシンが、一実施形態によれば無効状態でインストールされる。この構成では、複製されたステートマシンのアグリーメントハンドラはアグリーメントエンジンからアグリーメントを学ことができるが、一実施形態によれば、出力提案シーケンスを介して複製されたステートマシンにアグリーメントを出力することはない。もし新規ラーナーがメンバシップｍ'内においてプロポーザーの役割も有しているとすると、展開されたばかりの複製されたステートマシンｄが無効状態にあることから、この新規ラーナー兼プロポーザーは、提案することを（まだ）許可されない。
５．  メンバシップｍ内のプロセスにより、複製されたステートマシンｄの関連付けをメンバシップｍ'に変更するためのメンバシップｍ'へのメンバシップ変更の提案がなされる。
６．  メンバシップ変更の提案は、メンバシップｍの下で、ｄに対する一連のアグリーメント内の（アグリーメント識別子＜ｄ，ｍ，ｋ＞を有する）アグリーメントａｋとなる。
７．  ｍ内の各ノードにおいてアグリーメントハンドラによりａｋが一連のアグリーメントの中の正しいポイントで処理されると、それらは、複製されたステートマシンｄの新たなメンバシップｍ'への関連付けをｍから変更する。
８．  新規ラーナーを有するメンバシップへのメンバシップの変更を観測した直後（すなわち、ｍ'内のラーナーの数がｍ内のそれよりも大きくなった場合（すなわち、｜Ｌ'｜＞｜Ｌ｜））、ｍ'内で提案する能力を有する各プロセス（すなわち、新たなメンバシップｍ'内のプロポーザー）は、次の利用可能なアグリーメントキーの値ｋを含む新規ラーナーを開始する（すなわち、それらの出力が始まるべき出力提案シーケンス内のポイントから開始する）ための提案を発行する。
ここで、ｍ及びｍ'に共通なプロポーザーのそれぞれは、この開始提案の望ましいアグリーメントキーを、ｋで発生したメンバシップ変更の後ろのキーであるｋｌａｓｔ＿ｏｕｔｐｕｔ＋１に設定する。ｍ及びｍ'に共通なプロポーザーのそれぞれは同一のアグリーメントキーに対する提案を発行しているので、最初の提案のみがｍ'のための一連のアグリーメントの中でこのｋｌａｓｔ＿ｏｕｔｐｕｔ＋１ｔｈのスロットを「勝ち取り」、それ故、例え何度も提案される可能性があるとしても、１つのアグリーメントのみが作成され、ラーナーによって観測されることになる。
９．  各々の新規ラーナーのアグリーメントハンドラは、識別子＜ｄ，ｍ'，ｋ＋１＞を有するスタートアグリーメントを処理し、このアグリーメントからｋ＋１の値を抽出し、ｋｌａｓｔ＿ｏｕｔｐｕｔをｋ＋１に初期化し、キューイングされた複数のアグリーメントから、ｋｌａｓｔ＿ｏｕｔｐｕｔよりも遅れているアグリーメントキーｋ（ｋ＜ｋｌａｓｔ＿ｏｕｔｐｕｔ）を削除する。
１０．同期されるべきアプリーション状態が存在しない場合には、新規ラーナーの出力提案シーケンスが開始され、アグリーメントがｋｌａｓｔ＿ｏｕｔｐｕｔ＋１から順に、複製されたステートマシンに配送される。
このように、新規ラーナーは、共通の開始点に同期されると、図２に示されかつ説明された方法で、今同期された最後の出力よりも進んでいるアグリーメントをキューイングし、最後の出力に位置するアグリーメントを出力提案シーケンスにキューイングし、最後の出力よりも遅れたアグリーメントを無効にする処理を前に進めることが可能になる。しかしながらこのことは、複製されたステートマシンに対してアグリーメントを、ｋｌａｓｔ＿ｏｕｔｐｕｔ＋１の前から順に配送するのには役立たない。一実施形態によるこのような方法を以下で述べる。
新規ラーナーがアプリケーション状態を同期するのを援助する手順
【００４９】
上記のように、一組の新規ラーナーに展開された複製されたステートマシンdは、それに関連付けられたアプリケーション状態を有し得る。例えば、ソフトウェアバージョン制御システムに関して、アプリケーション状態は、システムによって管理された複製ソフトウェアレポジトリの状態である。そのソフトウェアレポジトリの新たなレプリカが必要な場合、ビジネスをいつも通りに運営し続けるために必要となる非ブロッキングな行動を維持しながらこの状態を同期するために、何らかのメカニズムが必要となる。一実施形態によれば、１人またはそれ以上の新規ラーナーに展開された複製されたステートマシンに関連付けられたアプリケーション状態を同期することには、以下が含まれ得る。
１．  新たなラーナーは、上述した「新規ラーナーを追加するための手順」におけるプロセスの完了の後、そのアプリケーション状態を同期させるか、又は、そのアプリケーション状態の同期を受けることが可能になる。これは、少なくとも１人の他のラーナーからの助けがなくてはならないためである。
２．  したがって、古いメンバシップｍからの１人又はそれ以上のラーナーが、新規ラーナーを援助するために選択され得る。Ｈは、このプロセスのセットを示す（各ヘルパーはプロセッサのセット｛∀ｈ∈Ｈ：ｈ∈Ｌ｝内にある。すなわち全てのヘルパーは、古いメンバシップｍにおいてラーナーであった）。一実施形態によれば、複製されたソフトウェアバージョン制御レポジトリのケースにおいて、リポジトリが大きく（例えば、ギガバイト）新規ラーナーへの転送に相当の時間を要する場合があることから、ヘルパーであるラーナーを複数指定してもよい。複数のヘルパー兼ラーナーは、各新規ラーナーが例えば、空間的及び／又は地理的に近い、あるいは、より高い帯域幅を有する接続によって結合されたプロセス（すなわち、古いメンバシップｍでもラーナーであった現在のメンバシップｍ'のラーナーであって、新規ラーナーを援助するために選択されたもの）によって援助され得ることから、許容され得るし、有益である。この援助は、アプリケーション状態を新規ラーナーに転送するのに必要なネットワークトラフィック及び／又は時間を最小にする。
３．  メンバシップｍ'におけるプロポーザー（ラーナーでもある）はその後、ヘルパーのセットＨに対して新規ラーナーを援助すべきであることを通知するために、メンバシップｍ'に対して援助開始提案を提案することができる。
４．  Ｈにおける各プロセスのアグリーメントハンドラはその後、一連のアグリーメントの中の位置ｋ'にある援助開始提案を、位置ｋ（すなわち、援助開始提案はアグリーメント識別子＜ｄ，ｍ'，ｋ'＞（ｋ'＞ｋ）を有する）の後ろにあり、自身の出力提案シーケンスを無効にしている複製されたステートマシンｄのために処理することができる。これは、複製されたステートマシンｄが、アグリーメントの学習（必要ならばそれらのキューイング）と、（もしそれがメンバシップｍ'においてプロポーザーの役割を有しているが、複製されたステートマシンに対してアグリーメントを出力することがもはやなく、アプリケーション状態を一定に維持するならば）提案の生成とを継続できることを意味する。
５．  新規メンバシップｍ'における新規ラーナーのアプリケーション状態はその後、例えば帯域外の転送メカニズムを用いて同期され得る。例えば、ファイルシステムデータの同期であれば、ファイル転送は、例えば、新規ラーナー及び指定されたヘルパーにリンクしているネットワーク上でデータを送信するｒｃｐ（互いに独立した複数のソフトウェアコンポーネントの統合を容易にするプログラマーツール）のようなファイル転送プログラムを用いて行われ得る。しかしながら、必要なアプリケーション状態を新規ラーナーに対して転送するためには、例えば、ピアツーピア、フラッシュストレージ、ＣＤ−ＲＯＭ、テープその他の、ランダムアクセス、シーケンシャルアクセス、固定式、又は回転式のメディアデータキャリアのような、他のオンライン又はオフラインのメカニズムも用いられ得る。
６．  ファイル転送が完了すると、ｍ'内のプロポーザーは、Ｈ内のプロセス及び新規ラーナーを再有効化するための提案を発行可能になる。この提案は、新規メンバシップｍ'内のアクセプターの過半数によって同意されると、位置ｋ'の後ろにある複製されたステートマシンｄのために、一連のアグリーメントの中の位置ｋ''（ｋ''＞ｋ'）におけるアグリーメント識別子＜ｄ，ｍ'，ｋ''＞を与えられる。
７．  Ｈ内の各プロセス上のアグリーメントハンドラが、ステートマシンｄのために一連のアグリーメントの中の位置ｋ''に配置された再有効化アグリーメントを処理し、自身の出力提案シーケンスを有効化する。複製されたステートマシンｄは、この時点より、アグリーメントの学習をｋ'から順番に開始し、ステップ４で休止された自身の出力提案シーケンスが取り損ねたアグリーメントのキャッチアップを行う。
８．  ｍ'内の各新規ラーナープロセス上のアグリーメントハンドラが、複製されたステートマシンｄのために一連のアグリーメントの中の位置ｋ''に配置された再有効化アグリーメント（すなわち、この再有効化アグリーメントは、アグリーメント識別子＜ｄ，ｍ'，ｋ''＞（ｋ''＞ｋ'）を有する）を処理し、自身の出力提案シーケンスを有効化する。
９．  しかしながら、ステップ５で新規ラーナーに転送されたアプリケーション状態がステップｋ'で獲得されると、新規ラーナーの出力提案シーケンスの値ｋｌａｓｔ＿ｏｕｔｐｕｔはｋ＋１（メンバシップのアグリーメントが行われた直後のアグリーメントのアグリーメント識別子のキー）に設定される。したがって、ｋ＋１からｋ'までのアグリーメントは出力提案シーケンスに与えられず、ｋ'以降のアグリーメントのみが複製されたステートマシンに適用される。そこで、新規ラーナーはｋ以降の見落としていたアグリーメントを複製されたステートマシンｄに適用し、それによって、新しいラーナーのアプリケーション状態を新たなメンバシップｍ'に同期させる。
【００５０】
図４は、一実施形態によるコンピュータ実施方法のフローチャートである。この中に示されるように、ブロックＢ４１は、複数の複製されたステートマシンを生成するために、コンピュータネットワーク上で、複数のされたステートマシン中の1つのステートマシンの状態の複製を要求する。ブロックＢ４２に示されるように、複数の複製されたステートマシンは、複数のプロセスと、すべての複製されたステートマシンから見ることができ、かつ、それらの一貫性を維持する順序付けられたアグリーメントの第１のセットとに関連付けられ得る。複数の複製されたステートマシンに関連付けられた複数のプロセスは、Ｂ４３に示されるように、順序付けられたアグリーメントの第１のセットの任意のポイントにおいて変更され得る。この変更は、例えば、複製されたステートマシンに関連付けられた複数のプロセスのうちの１つを追加ないし削除すること、これらのプロセスのうちの１以上の役割を変更すること、又は、複数されたステートマシンが関連付けられたすべてのプロセスを変更することを含み得る。例えば、この変更は、その下でアグリーメントの処理がなされるメンバシップの変更を含んでもよい。Ｂ４４に示されるように、複数のプロセスに対する変更がなされている間に、複数の複製されたステートマシンに関連付けられた複数のプロセスのうちの１つ以上が状態を変更できるようにしてもよい。例えば、ラーナーは、現在のメンバシップ内の１つ以上のプロセスの役割が変更される間、複製されたステートマシンにアグリーメントを出力し続けることができる。すなわち、メンバシップの変更が行われる間、システムはブロックされない。
【００５１】
図５は、一実施形態によるコンピュータ実施方法のさらなる側面を示すフローチャートである。Ｂ５１に示されるように、コンピュータネットワーク上で受信されたアグリーメントは、第１のメンバシップに属するプロセス上に展開された第１の複製されたステートマシンにおいて処理され得る。このような処理は、第１のメンバシップに関連付けられた順序付けられたアグリーメントの第１のセットによって定義される順序で実行され得る。ブロックＢ５２は、順序付けられたアグリーメントの第２のセットに関連付けられた第２のメンバシップに属するプロセス上に第１の複製されたステートマシンが展開されることとなるように構成された、メンバシップ変更についてのアグリーメントを受信することを要求する。Ｂ５３に示されるように、メンバシップ変更についてのアグリーメントは、順序付けられたアグリーメントの第１のセット内の１つのポイント（例えば、任意のポイント）で処理され得る。
【００５２】
複数の実施形態によれば、引き続き図５を参照すると、第１のメンバシップに属するプロセスによってアグリーメントが処理されている間に、非同期かつ順序が乱れた状態でのアグリーメントの受信の結果として、第２のメンバシップに属するプロセス上で処理されるように構成されたアグリーメントが受信され得る。第２のメンバシップに属するプロセス上で処理されるべき受信されたアグリーメントは、メンバシップ変更のアグリーメントが処理された後に処理するため、（例えば、電力サイクルを跨いでもデータが失われない電力セーフな方法で）永続的に記憶され得る。第２のメンバシップに属するプロセス上で処理されるべき記憶されたアグリーメントは、その後、順序付けられたアグリーメントの第２のセット内の１つのポイント（例えば、任意のポイント）で処理され得る。第１のメンバシップに属するプロセス上に展開された複製されたステートマシンで受信されたアグリーメントは、メンバシップ変更についてのアグリーメントが処理されている間、継続して処理され得る。さらに、第１のメンバシップからのプロセスは、受信されたアグリーメントが第１のメンバシップに属する他のプロセス上に展開された複製されたステートマシンにおいて処理されている間に、追加又は削除され得る。また、第１のメンバシップに属する他のプロセス上に展開された複製されたステートマシンにおいて受信されたアグリーメントが処理されている間に、第１のメンバシップに属するプロセスの役割が変更され得る。例えば、役割を変更することは、プロセスの役割をプロポーザー、アクセプター、及び／又はラーナーのそれに変更することを含み得る。受信されたアグリーメントは、第１のメンバシップに関連付けられ、順序付けられたアグリーメントの第１のセットによって定義される順序で、第１のメンバシップに属するプロセス上に展開された第２の複製されたステートマシンで処理され得る。この方法では、アグリーメントが非同期かつ順序が乱れた状態で受信されるときにも、第１及び第２の複製されたステートマシンの一貫性が維持される。
【００５３】
都合のいいことに、本明細書に記載され図示された複製された状態機械の動的メンバシップの実施形態は、ステートマシンに関連付けられたプロセスのコレクションが、ステートマシンのすべてのレプリカから見ることのできる一連のアグリーメント内の任意のポイントで変更されることを可能にする。実際に、一実施形態によれば、メンバシップ内で変更を行うためのアグリーメントは、一連のアグリーメントの中の任意のポイントで行われ得る。そして、システム内のプロセスは、いずれのポイントでも進行（例えば、出力提案シーケンス内にアグリーメントをキューイングすること、及び、それらのアプリケーション状態を変更すること）をブロックされない。
【００５４】
本動的メンバシップの方法及びシステムの実施形態は、ステートマシンおよびそのすべてのレプリカから見ることのできる一連のアグリーメント内の任意のポイントで、提案が提案され同意されることを可能にする。したがってシステムは、メンバシップ変更が行われる間、利用可能な状態で維持される。このことは、企業にとって重要である。なぜなら、実施形態が、新しいノードをオン又はオフラインにしたり、既存のノードの役割を変更したりするためにダウンタイムを発生させることなく、重要なビジネス機能をエンドユーザーにとって継続的に利用できるようにすることによって、ビジネスの継続性を実現するからである。結果として、実施形態は、ビジネス継続性計画（すなわち、ダウンタイム及びメンテナンス期間をスケジュールし、そのようなダウンタイム及びメンテナンス期間を分散コンピューティングネットワークを通じてエンドユーザーに伝達すること）の必要性も低減する。生産性もまた、向上する。なぜなら、そのようなメンバシップ変更の間、新たなノードがオンライン化され、それらのアプリケーション状態が同期されている間、又は、既存のノードが故障し、代替のものがオンライン化されるときにもユーザが生産的であり続けられるためである。さらに、一実施形態によれば、分散コンピューティング環境における動的メンバシップが可能になるだけでなく、そのような環境の構成ノードへの役割の選択的な関連付けも可能になる。
【００５５】
図６は、実施形態を実施できるコンピュータシステム６００のブロック図を示す。コンピュータシステム６００は、情報を伝達するためのバス６０１又はその他の通信機構と、情報を処理するためにバス６０１と接続された１つ以上のプロセッサ６０２とを備え得る。コンピュータシステム６００はさらに、情報と、プロセッサ６０２によって実行されるべき命令とを記憶するためにバス６０１に接続されたランダムアクセスメモリ（ＲＡＭ）又はその他の（メインメモリと呼ばれる）動的記憶装置６０４を含み得る。メインメモリ６０４はまた、プロセッサ６０２による命令の実行中に、仮の変数又はその他の中間情報を記憶するために使用され得る。コンピュータシステム６００はまた、プロセッサ６０２のための静的な情報及び命令を記憶するためにバス６０１に接続されたリードオンリーメモリ（ＲＯＭ）及び／又はその他の静的記憶装置６０６を備え得る。バス６０１には、例えば磁気ディスク又はフラッシュメモリのようなデータ記憶装置６０７が情報および命令を記憶するために接続され得る。コンピュータシステム６００はまた、コンピュータのユーザーに対して情報を表示するために、バス６０１を介して表示装置６１０に接続され得る。別のタイプのユーザ入力装置は、方向情報及びコマンド選択をプロセッサ６０２に伝達し、ディスプレイ６２１上におけるカーソルの移動を制御するための、マウス、トラックボール、又はカーソル方向キーなどのカーソルコントロール６２３である。コンピュータシステム６００は、通信装置（例えば、モデムやＮＩＣ）を介して、ネットワーク６２６及び分散コンピューティングシステムの１つ以上のノードに接続され得る。
【００５６】
実施形態は、分散コンピューティングシステム内の複製されたステートマシンにおいてメンバシップを生成し、展開し、かつ動的に変化させるために、コンピュータシステムの使用及び／又は複数のそのようなコンピュータシステムに関連する。一実施形態によれば、本明細書で説明した方法及びシステムは、１つ以上のコンピュータシステム６００により、プロセッサ６０２がメモリ６０４内に含まれる一連の命令を実行することに応答して提供され得る。そのような命令は、データ記憶装置６０７のような別のコンピュータ可読媒体からメモリ６０４内に読み出され得る。メモリ６０４内に含まれる一連の命令の実行は、プロセッサ６０２がステップを実施し、本明細書で説明した機能性を有することを可能にする。代わりの実施形態では、本発明を実施するために、ソフトウェア命令の代わりに、又はそれと組み合わせて、ハードウェアにより実現される回路を用いることができる。このように、本発明は、ハードウェア回路及びソフトウェアの特定の組み合わせには限定されない。実際、任意の適切なコンピュータシステムが本明細書で説明した機能性を実現できることを当業者は理解するべきである。コンピュータシステムは、望ましい機能を実施するために動作する１つ又は複数のマイクロプロセッサを含み得る。一実施形態においては、１つのマイクロプロセッサ又は複数のマイクロプロセッサによって実行される命令は、本明細書で説明したステップをマイクロプロセッサに実行させるように動作可能である。各命令は、任意のコンピュータ可読媒体に記憶され得る。一実施形態では、それらは、マイクロプロセッサの外部にある、又は、マイクロプロセッサと一体化されてなる不揮発性の半導体メモリ上に記憶され得る。別の実施形態では、各命令はディスクに記憶され、マイクロプロセッサによって実行される前に揮発性の半導体メモリ内に読み出され得る。
【００５７】
以上、本開示の実施形態を説明したが、これらの実施形態は例としてのみ提示されたものであり、本開示の範囲を限定することを意図したものではない。実際、本明細書で説明した新規な方法、装置、及びシステムは、他の様々な形式で具体化され得る。さらに、本明細書で説明した方法及びシステムの形式においては、様々な省略、代替、及び変更が本開示の精神を逸脱することなく行われ得る。添付の請求の範囲及びその均等物は、本開示の範囲及び精神に含まれるものとしてのそのような形式又は変更を網羅することを意図している。例えば、当業者は、様々な実施形態において、実際の物理的及び論理的構造が図面に示されたものとは異なり得ることを認識するであろう。実施形態によっては、上記実施例で説明した一定のステップが削除され、他のものが追加されてもよい。また、上で説明した具体的な各実施形態の特徴及び属性は、追加の実施形態を構成するために異なる方法で組み合わされてもよく、それらのすべてが本開示の範囲内となる。本開示は、一定の好ましい実施形態及びアプリケーションを提供するが、本明細書で述べた特徴及び利点のすべてを提供するわけではない実施形態を含む、当業者に明らかな他の実施形態もまた、本開示の範囲内である。したがって、本開示の範囲は、添付の請求の範囲を参照してのみ定められるものであることが意図される。
【図１】
0006754299.tif 000002
【図２】
0006754299.tif 000003
【図３】
0006754299.tif 000004
【図４】
0006754299.tif 000005
【図５】
0006754299.tif 000006
【図６】
0006754299.tif 000007