(57)【要約】コンピュータ実施方法は、第１のメンバシップに関連する第１のグローバルにオーダされた組のアグリーメントによって定められたオーダで前記第１のメンバシップに属するプロセスに配置した第１の複製状態マシンにおいてコンピュータネットワーク上で受け取られたアグリーメントを処理するステップと、アグリーメントを受け取って、第２のグローバルにオーダされた組のアグリーメントに関連する第２のメンバシップに属するプロセスに前記第１の複製状態マシンが配置されるように構成されたメンバシップを変更するステップと、前記アグリーメントを受け取って、前記第１のグローバルにオーダされた組のアグリーメント内の点でメンバシップを変更するステップと、を備える。【選択図】図１
2016510924.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータネットワーク上で複数の状態マシンにおける状態マシンの状態を複製し、複数の複製状態マシンを作成するステップと、
複数のプロセスと、全ての複製状態マシンに見え、その一貫性を維持する第１のグローバルにオーダされた組のアグリーメントとに前記複数の複製状態マシンを関連付けるステップと、
前記複数の複製状態マシンに関連付けられた前記複数のプロセスを、前記第１のグローバルにオーダされた組のアグリーメントにおける任意の点において変更するステップと、
前記複数のプロセスに対する変更が行われている間、前記複数の複製状態マシンに関連付けられた前記複数のプロセスのうちの少なくともいくつかが状態を変更するのを可能化するステップと、
を備えることを特徴とするコンピュータ実施方法。
【請求項２】
前記変更ステップが、前記複数のプロセスのうちの少なくとも１つの役割を変更するステップを備えることを特徴とする、請求項１に記載のコンピュータ実施方法。
【請求項３】
前記役割を変更するステップが、前記複数のプロセスのうちの少なくとも１つの役割を提案者、受諾者および学習者のうちの１人に変更するステップを備えることを特徴とする、請求項２に記載のコンピュータ実施方法。
【請求項４】
前記変更ステップが、前記複数のプロセスの数を変更するステップと、前記複数の複製状態マシンに関連付けられた全てのプロセスを変更するステップとのうちの１つを備えることを特徴とする、請求項１に記載のコンピュータ実施方法。
【請求項５】
前記複数のプロセスへの前記変更を完了するステップと、前記複数の複製状態マシンを前記変更した複数のプロセスと第２のグローバルにオーダした組のアグリーメントとに関連付けるステップとをさらに備えることを特徴とする、請求項１に記載のコンピュータ実施方法。
【請求項６】
前記複数のプロセスが第１のメンバシップに属し、前記複数のプロセスを変更するステップが、前記複数の複製状態マシンの、前記変更した複数のプロセスを含む第２のメンバシップへの関連付けを変更するステップを備えることを特徴とする、請求項１に記載のコンピュータ実施方法。
【請求項７】
前記複製状態マシンの各々において、前記第１のグローバルにオーダされた組のアグリーメント内の点で処理するべきアグリーメントを受け取るステップをさらに備えることを特徴とする、請求項１に記載のコンピュータ実施方法。
【請求項８】
前記受け取りステップが、非同期に、しかも前記第１のグローバルにオーダされた組のアグリーメントによって定められた順序を無視して処理するためのアグリーメントを受け取るステップを備えることを特徴とする、請求項７に記載のコンピュータ実施方法。
【請求項９】
前記複数の複製状態マシンに関連付けられた前記複数のプロセスを変更するステップが、アグリーメントの受け取りに応じて行われ、現在のメンバシップから新規メンバシップへ変更することを特徴とする、請求項７に記載のコンピュータ実施方法。
【請求項１０】
前記第１のグローバルにオーダされた組のアグリーメントが、前記複数の複製状態マシンに関連付けられたプロセスを変更するための少なくとも１つのアグリーメントを備えることを特徴とする、請求項１に記載のコンピュータ実施方法。
【請求項１１】
前記複数の複製状態マシンに関連付けられた前記複数のプロセスを変更するステップが、前記第１のグローバルにオーダされた組のアグリーメントから学習する現存の学習者に影響を与えることなく、前記複数のプロセスに学習者を追加するステップを備えることを特徴とする、請求項１に記載のコンピュータ実施方法。
【請求項１２】
前記複数のプロセスに対する変更が完了した後、前記追加した学習者のアプリケーション状態を同期させるステップをさらに備えることを特徴とする、請求項１１に記載のコンピュータ実施方法。
【請求項１３】
第１のメンバシップに関連付けられた第１のグローバルにオーダされた組のアグリーメントによって定められたオーダで前記第１のメンバシップに属するプロセスに配置した第１の複製状態マシンにおいてコンピュータネットワーク上で受け取られたアグリーメントを処理するステップと、
アグリーメントを受け取って、第２のグローバルにオーダされた組のアグリーメントに関連付けられた第２のメンバシップに属するプロセスに前記第１の複製状態マシンが配置されるように構成されたメンバシップを変更するステップと、
前記アグリーメントを処理して、前記第１のグローバルにオーダされた組のアグリーメント内の点でメンバシップを変更するステップと、
を備えることを特徴とするコンピュータ実施方法。
【請求項１４】
前記第１のメンバシップに属するプロセスによってアグリーメントが処理される間、前記第２のメンバシップに属するプロセス上で処理されるべきアグリーメントを受け取るステップをさらに備えることを特徴とする、請求項１３に記載のコンピュータ実施方法。
【請求項１５】
メンバシップを変更するべきアグリーメントが処理された後に処理するための前記第２のメンバシップに属するプロセス上で処理されるべき受け取りアグリーメントを永続的に記憶させるステップをさらに備えることを特徴とする、請求項１４に記載のコンピュータ実施方法。
【請求項１６】
前記第２のグローバルにオーダされた組のアグリーメント内の点において、前記第２のメンバシップに属するプロセス上で処理されるべき記憶したアグリーメントを処理するステップをさらに備えることを特徴とする、請求項１５に記載のコンピュータ実施方法。
【請求項１７】
メンバシップを変更する前記アグリーメントの処理中に、前記第１のメンバシップに属するプロセスに配置された前記複製状態マシンにおいて受け取られたアグリーメントを処理するステップをさらに備えることを特徴とする、請求項１４に記載のコンピュータ実施方法。
【請求項１８】
前記第１のメンバシップに属する前記プロセスのうちの他のものに配置された前記複製状態マシンにおいて、前記受け取られたアグリーメントが処理されている間、前記第１のメンバシップにプロセスを追加するステップおよび前記第１のメンバシップからプロセスを削除するステップのうちの１つをさらに備えることを特徴とする、請求項１４に記載のコンピュータ実施方法。
【請求項１９】
前記第１のメンバシップに属する前記プロセスのうちの他のものに配置された前記複製状態マシンにおいて、前記受け取られたアグリーメントが処理されている間、前記第１のメンバシップに属するプロセスの役割を変更するステップをさらに備えることを特徴とする、請求項１４に記載のコンピュータ実施方法。
【請求項２０】
前記役割を変更するステップが、前記プロセスの前記役割を提案者、受諾者および学習者のうちの１人に変更するステップを備えることを特徴とする、請求項１９に記載のコンピュータ実施方法。
【請求項２１】
前記第１のメンバシップに関連付けられた前記第１のグローバルにオーダされた組のアグリーメントによって定められたオーダで、前記第１のメンバシップに属するプロセスに配置された第２の複製状態マシンにおいての受け取られたアグリーメントを処理するステップをさらに備え、アグリーメントが非同期に、しかも無秩序に受け取られているので、前記第１および第２の複製状態マシンは一貫したままであることを特徴とする、請求項１６に記載のコンピュータ実施方法。
【発明の詳細な説明】
【技術分野】
【０００１】
複製状態マシンをホスティングするプロセスの分散コンピューティングシステムにおいては、状態マシンの関連付けを状態マシンの動作に参加するプロセスの収集に変化させることが望ましい場合もある。
【図面の簡単な説明】
【０００２】
図１は、各複製状態マシンのアグリーメントハンドラに合意を与えるアグリーメント／調整エンジンを示す一実施形態によるブロック図である。
【０００３】
図２は、一実施形態によるメンバシップ変更がない場合におけるアグリーメントのハンドリングを示す図である。
【０００４】
図３は、一実施形態による動的メンバシップ変更を示すフローチャートである。
【０００５】
図４は、一実施形態による方法を示すフローチャートである。
【０００６】
図５は、一実施形態による方法のさらなる側面を示すフローチャートである。
【０００７】
図６は、一実施形態による動的メンバシップの側面を実施可能なコンピューティングデバイスのブロック図である。
【発明を実施するための形態】
【０００８】
分散システム：分散システムは、空間的に分離されており且つメッセージの交換によって互いに通信可能なである明確なプロセスの収集を備える。
【０００９】
複製状態マシン：複製状態マシンのアプローチは、複製サーバおよびサーバレプリカと相互作用する協調クライアントにより、耐障害サービスを実現する方法である。状態マシンの状態は、全ての学習者において同様に展開するので、これらの状態は「複製される」。１つのサーバのレプリカが、分散システムの別個のプロセッサによって実行され、プロトコルは、協調クライアントとこれらのレプリカを相互作用させるために用いられる。複製状態マシンの１つの例および実現化は、決定論的方法でその状態を実行する決定論的状態マシンである。
【００１０】
アグリーメントのグローバルシーケンス：状態マシンアプローチにおいては、一貫性のある順序でリクエストが１つずつ状態マシンにより処理される。従って、互いに調和したままである状態マシンのレプリカに対して、各レプリカ上で同じ順序で確実にレプレイされるように、コマンドのグローバルに合意したシーケンスが必要となる。一実施形態によれば、アグリーメントの処理および複製状態マシンへの通知は、別個のキューの具現化によってその提案アスペクトから分離可能であり、アグリーメントのグローバルシーケンスは、出力提案シーケンスと呼ばれる概念によって複製状態マシンに通知可能となる。出力提案シーケンスによってソフトウェアアプリケーション（例えばソフトウェアバージョンコントロールシステム）に通知されたアグリーメントのグローバルシーケンスは、一実施形態によれば、キーklast_outputによって全体的に命令可能である（一実施形態によれば、単調に増加する整数として実現化可能である）。
【００１１】
分散アグリーメント／協調エンジン：一実施形態は、状態マシンの一貫したレプリカを達成するために必要なアグリーメントのグローバルシーケンスを生成するために、アグリーメントまたは協調エンジンを求める。例示の協調エンジンは、その全体が参照することにより本明細書に援用されている、２００８年２月１３日に出願され、本発明の譲受人に譲渡された同時係属中の米国特許出願第１２／０６９，９８６号に述べられている。しかしながら、一実施形態によれば、動的メンバシップのために使用する協調エンジンは、アグリーメントが行われた複製状態マシンのアイデンティティを含む固有のアグリーメントアイデンティティ、アグリーメントが行われたメンバシップ「ｍ」のアイデンティティおよびアグリーメントの固有のキー「ｋ」を支持することが可能であり、その固有のキーkは、一実施形態によれば、アグリーメントのグローバルシーケンスでアグリーメントによって占有された位置に対応する。従って、一実施形態によれば、d, m およびkは、メンバシップmおよびアグリーメントキーkの下で、複製状態マシンdに対するアグリーメントエンジンによって行われた各アグリーメントを一意的に識別することを可能にする。ここでは、アグリーメントアイデンティティは３重の<d,  m, k>で示される。
【００１２】
非ブロッキング：ここでは、用語「非ブロッキング」は、１組のプロセスを変化させながら、その組が完全にまたは一部が利用可能なままである能力に関する。
【００１３】
提案者：一実施形態によれば、提案者は、複製状態マシンの将来の状態への変化を提案する（すなわち、申し出をする）ように構成され、可能化される。複製ソフトウェアバージョンコントロールシステムを備える実施形態では、提案者は、システムによって管理されたソフトウェアレポジトリを変化するよう許可されたプロセスであってもよい。
【００１４】
受諾者：一実施形態によれば、受諾者は、提案者が行った提案のオーダでの判定に参加するように構成されたプロセスである。一実施形態によれば、提案がグローバルシーケンスで特定の場所を取ることを大多数の受諾者が決定した時にのみ、同意する。一実施形態によれば、受諾者は、アグリーメントのオーダでの判定に参加するのみであるように構成可能であり、アグリーメントの根本的な内容についての理由付けをしない／関心を持たない（ここで述べるように、アグリーメントの価値はアグリーメント協調エンジンに対しては不明瞭である）。受諾者は、アプリケーション非依存エンティティとして構成することも可能である。
【００１５】
学習者：一実施形態によれば、学習者は、提案者と受諾者との間で行われたアグリーメントについて聞知し、その出力提案シーケンスによって決定論的オーダのアグリーメントをアプリケーションに適用する。複製ソフトウェアバージョンコントロールシステムを備える実施形態において、学習者は、システムによって管理されるソフトウェアレポジトリのレプリカをホスティングするように構成されたプロセスを備えることも可能である。
【００１６】
メンバシップ：メンバシップは、１組のノードまたはプロセスを特定し、役割が各々、特定された組のノード内で果たされる。一実施形態によれば、実施形態による動的メンバシップにおける使用に好適なメンバシップは、１組の受諾者と、１組の提案者と、１組の学習者とを含むことも可能である。
【００１７】
分散協調エンジンによりプロセスに対するアグリーメントの非同期で無秩序の搬送の存在下においても、状態マシンヌル操作の提案をmなどのスループット低下手段に再分類することなく、非ブロッキング（すなわち、システムが常に利用可能である）、融通性があり（任意のプロセスが削除され且つメンバシップに追加され得る）、決定論的な（複製状態マシンの動作において同じ点の全てのノードにおいて同じ変更が生じる）メンバシップ変更を許容する複製状態マシンの動的メンバシップ変更を可能化し、達成するための実施形態をここで述べる。
【００１８】
従って、一実施形態は、動的メンバシップ変更および分散コンピューティング環境におけるノードに対する役割の選択的関連付けを支持する上記米国特許出願第１２/０６９，９８６号において述べられ請求されたアグリーメントのグローバルシーケンスを向上させる。一実施形態によれば、アグリーメントアイデンティティは、各複製状態マシンに対して、各メンバシップに対するアグリーメントのシーケンスが永続的に記録出来る永続的記憶装置として提供される。一実施形態による永続的記憶装置は、アグリーメントのキーkおよび関連値eのタプルであるキーを用いてアグリーメントが行われたメンバシップのアイデンティティをマッピングする。従って、一実施形態によれば、各複製状態マシンに対するアグリーメントハンドラは、多数のメンバシップに対する多数のアグリーメントシーケンスを一度に維持し、アグリーメントのグローバルシーケンスでの適切な点において、その間での切り替えを行うように構成することも可能である。
提案、アグリーメントおよびアグリーメントハンドリング
【００１９】
動的メンバシップの一実施形態のコンポーネントおよびこのようなコンポーネントがインタネット化する方法を詳述する前に、提案の概念を説明するが、提案が何の情報を含むか、提案がいかにしてアグリーメントに成り得るか、さらにアグリーメントハンドラがアグリーメントをいかにして処理するかを含む。これらの概念を考慮する場合、非ブロッキングであり、融通性がある決定論的動的メンバシップを達成するための実施形態が設定される。一実施形態によれば、動的メンバシップ機能性は、多数（例えば１０００個）の複製状態マシンに亘り同時に実現可能である。何故なら、実施形態が１つの実例に限定されないからである。上記のように一実施形態によれば、この並列処理は、各教程がアグリーメントアイデンティティ<d, m, k>を備えた状態で達成可能である。すなわち、複製状態マシンdは、アグリーメントが行われたメンバシップmと、そのメンバシップに対するアグリーメントの固有のキーとに互いに関連付けられる。
【００２０】
一実施形態によれば、１個の複製状態マシンに対する提案、アグリーメントおよびアグリーメントハンドリング機構は、以下のように実施可能であり、多数の複製状態マシンのうちのいずれかに対して望ましいものとして反復可能である。１個の複製状態マシンに関して実施形態を以下で述べる。トリプレット<d, m, k>におけるdは省略される。
【００２１】
最初に、複製状態マシン（提案者）の状態に対する変化を提案するように許可されるプロセスnは提案eを構成し、それを複製状態マシンdに提示する。複製状態マシンdは、提案eを解釈する必要はない。すなわち、提案eは、dに対して不明瞭であってもよい。
複製状態マシンdは、アグリーメントアイデンティティ<d, m, k>を以下のように構成する：
dは、それ自体のアイデンティティである；
mは、現在関連しているメンバシップのアイデンティティである；
kは、次の実行可能なキーである。例えば、自然数であり、以下の最大値よりも大きい。
ａ．  アグリーメントの最大値xに達する、< d, m, x>
ｂ．  dがメンバシップmに基づいて提案されたアグリーメントの最大値y、<d, m, y>。
【００２２】
提案eは、一旦構成されると、メンバシップキーおよび値ｅに従って提案を記憶するデータ構造に、状態マシンによって永続的に記憶される。すなわち、各提案は、３重＜ｍ，ｋ，ｅ＞を用いて一意的に識別可能である。
【００２３】
提案は、一旦記憶されると、<d, m, k>によって識別されたアグリーメントの実例に提示可能である。
【００２４】
提案が一旦、<d, m, k>によって識別されたアグリーメントの実例に提示されると、メンバシップmは、提案がアグリーメントのグローバルシーケンスでの位置におけるアグリーメントであるべきである、またはあるべきではないことにアグリーメント／協調エンジンを介して同意する。提案が同意される場合、アグリーメントアイデンティティ<d, m, k>内のアグリーメントとなり、複製状態マシンdのアグリーメントハンドラおよび（最終的に）dに対する出力提案シーケンスにアグリーメント／協調エンジンによって搬送することが可能である。このシーケンスは、３つの複製状態マシン、すなわちＡ、Ｂおよび?として図１に示される。図１は、それぞれの出力提案シーケンスへ搬送するためのアグリーメントを処理し且つオーダする各複製状態マシンのアグリーメントハンドラにアグリーメントを搬送するアグリーメント／協調エンジン１０２を示すブロック図である。図示するように、アグリーメントは、アグリーメント／協調エンジン１０２によって複製状態マシンＡ（d＝Ａ）、複製状態マシンＢ（d＝Ｂ）１０６および複製状態マシンＣ（d＝Ｃ）１０８に搬送され、これらは、キーklast_outputに従ってオーダされたそれぞれの出力提案シーケンス１１０、１１２および１１４に搬送するためのアグリーメントを処理し且つオーダする。
【００２５】
ハンドラに同意したイベントの複製は、例えば、（同意したイベントの複製が同様に他の方法で回避することも可能であるが）アグリーメント／協調エンジン１０２とアグリーメントハンドラ１０４、１０６および１０８との間でトランザクションコミットを共有することにより回避することも可能である。しかしながら、分散プロセスが自律的であり且つ同期しており、アグリーメントプロセスに含まれるプロセスが異なる速度で進行可能であり、ため、アグリーメント／協調エンジン１０２は、アグリーメントハンドラ１０４、１０６および１０８にアグリーメントを不規則に搬送するように構成することも可能である。従って、複製状態マシンのアグリーメントハンドラ１０４、１０６および１０８は、変数klast_outputを維持するように構成することも可能であり、変数klast_outputは、アグリーメントハンドラ１０４、１０６および１０８とそれぞれの出力提案シーケンス１１０、１１２および１１４との間で調節するように出力提案シーケンスに最後に与えられたkの値として定めることも可能である。
メンバシップ変更の無いアグリーメントハンドリング
【００２６】
アグリーメントハンドリングは、アグリーメントの観察キーkに依っていかなるアクションを取るべきかを決定するための論理を備えることも可能である。一実施形態によってアグリーメントが処理可能な方法の論理を以下で述べる。
【００２７】
出力提案シーケンスに搬送されたメンバシップmに対するグローバルで全体的にオーダされた組のアグリーメントは、アグリーメントの組Am＝｛a1, ??? , ak｝として表すことが可能であり、ここでは一実施形態によりアグリーメントキーｋが自然数の組（すなわち、｛∀ｋ：ｋ∈Ｎ｝）に属することも可能である。
【００２８】
出力提案シーケンスでの各アグリーメントは、アイデンティティ<d, m, k>を有し、ここでは、dは複製状態マシンのアイデンティティであり、mは、アグリーメントが同意されたメンバシップのアイデンティティである。しかしながら、一実施形態によれば、アグリーメントエンジンは、非決定論的オーダで複製状態マシンのアグリーメントハンドラにアグリーメントを搬送することが可能であり、従って、アグリーメントハンドラは正しいオーダで出力提案シーケンスにアグリーメントを設定する責任を負う場合もある。このために、アグリーメント協調エンジンから搬送されたアグリーメントを観察すると、一実施形態により、アグリーメントハンドラは、kを抽出し、それを以下の論理によって処理することも可能である。
ｋ＜ｋlast_output  の場合、アグリーメントは、この現在のシーケンスに対して無効である。
ｋ＝ｋlast_output  の場合、アグリーメントは、処理の準備が出来ているものとして明白である。
ｋ＞ｋlast_output  の場合、アグリーメントは、出力提案シーケンスに後に搬送するために（永続的に）待機状態にある。
【００２９】
図２は、一実施形態によるメンバシップ変更を仮定しないアグリーメントハンドリングを示す図である。ここで示すように、アグリーメントハンドリングプロセスは２０２で開始し、アグリーメントハンドラが、２０４で次のアグリーメント（すなわち｛a1, ??? , ak｝のうちの１つ）を観察して特徴付けることも可能である。特徴付けは、一実施形態によれば、現在のアグリーメントキーまたはｋlast_outputに関して受け取ったアグリーメントキーｋの比較に基づく場合もある。受け取ったキーｋが２０８で示すように、最後の出力よりも遅れている場合、現在のアグリーメントキーｋlast_outputよりも古いものとして２１０で示すように事実上無効である。受け取ったキーが２１２で示すように現在のキーにある（等しい）場合、２１４に示すように、出力提案シーケンスで待機状態となる。しかしながら、２１６に示すように、受け取ったキーｋが最後の出力の前にある（現在のキーｋlast_outputよりも大きい）場合、そのキーｋが現在のキーｋlast_outputに等しくなる時間まで、２１８で示すようにアグリーメントシーケンスで単に待ち状態になる可能性もあり、その時間に、出力提案シーケンスへの待ち状態となる可能性もある。プロセスは、その後、２０２に戻り、次のアグリーメントの受け取りを待つことが可能となる。
動的メンバシップを用いるアグリーメントハンドリング
【００３０】
一実施形態によれば、同意された値は、アグリーメント／協調エンジン１０２に対して不明瞭である。従って、一実施例によれば、複製状態マシンのメンバシップを変更するためのアグリーメントは、「まさに他のアグリーメント」であり、特定のメンバシップの下で行われたアグリーメントのグローバルシーケンスでのいずれかの点で発生する可能性がある。従って、メンバシップ変更を実施するためには、特定の型式の状態マシンまたはハンドラは必要ない。しかしながら、アグリーメントのグローバルシーケンスおよびその構成アグリーメントは、それらが生じるメンバシップに関連するのみであることに注目するべきである。
【００３１】
従って、上記に鑑み、アグリーメントが非同期で受け取られ、順序を無視して受け取られる場合もあるため、プロセスは、アグリーメントキーｋ′が同意したメンバシップ変更のキーｋよりも大きい提案を構成し、同意する場合もある。従って、アグリーメントキーｋ′がメンバシップ変更のキーｋよりも大きいアグリーメントの組（すなわち｛∃ａｋ′∈Ａ：ｋ′＞ｋ｝で定められたアグリーメントの組）は、ａｋが処理された後、複製状態マシンに関連しないメンバシップの下で行われているため、アグリーメントａｋの処理に続いて無効なアグリーメントとなる。
【００３２】
一実施形態によれば、アグリーメントは非決定論的順序で複製状態マシンのアグリーメントハンドラに搬送可能であるので、次のメンバシップ（およびその後のメンバシップ等）の下で行われたアグリーメントが、メンバシップ自体が変更になる前にアグリーメントハンドラに提供可能である。すなわち、新たなメンバシップの下で行われた１つまたはそれ以上のアグリーメントは、古いメンバシップの下で行われたアグリーメントを今まで通り処理しているアグリーメントハンドラに搬送可能である。
【００３３】
上で詳述したように、一実施形態によれば、アグリーメントエンジンは、同じ複製状態マシンに対するアグリーメントを保証することも可能であり、同じメンバシップmに対して同じグローバルシーケンス番号kである状態マシンdに対して２つのアグリーメントは発行されない。すなわち、アグリーメント識別子<d, m, k>は一意的でなければならない。
【００３４】
一実施形態によれば、決定論的状態マシンの決定論的動作は、決定論的状態マシンがその現在のメンバシップの下で同意された提案を出力するのみである場合達成されるのみであるので、適切に望ましい上記は、このようなアグリーメントが古いメンバシップの下で生じるため、k' > kが無効である現在のメンバシップｍに対して全てのアグリーメントが行われ観察されることにより、達成することも可能である。このような提案が同意されるために、新たなメンバシップm'の下で再提案され且つ同意されなければならない。しかしながら、このような提案（k' > kである現在のメンバシップｍに対して行われ且つ観察されたアグリーメント）は、再提案する必要はない。このような提案が、新たなメンバシップm'の下で再提案されない場合、それらは同意不可能であり、無視される可能性がある。
【００３５】
一実施形態によれば、アグリーメントは、異なるプロセスにより異なる速度で実施可能であるため、メンバシップを変更するアグリーメントがその同じプロセスに到達する前に、次の／新たなメンバシップ（ｍ′）の下で行われたイベントが別のプロセスに到達する可能性がある。従って、アグリーメントハンドラは、m'の下で行われたアグリーメントを記憶するように構成することも可能である。この方法で、例えアグリーメントを受け取るプロセスがいつメンバシップ変更が生じるかを（まだ）知らない場合であっても、mからm'への）メンバシップ変更が同意された後、出力提案シーケンスに搬送することも可能である。
【００３６】
一実施形態によれば、これは、アグリーメントのキーｋおよび関連の値eのタプルであるキーを用いてアグリーメントが行われたメンバシップアイデンティティのマップである記憶装置にアグリーメントを記憶装置内に存続させることにより各複製状態のアグリーメントハンドラにより達成可能である。このように、各複製状態マシンのアグリーメントハンドラは、多数のメンバシップに対するアグリーメントの多数の多重シーケンスを同時に維持することが可能である。
動的メンバシップ形式主義
【００３７】
一実施形態によれば、アグリーメントエンジンは、アイデンティティ<d, m, k>を有するアグリーメントを搬送して、アグリーメントハンドラに対するアグリーメントのグローバルシーケンスでの位置kにおいてmからm'まで複製状態マシンdのメンバシップを変更する。アグリーメントハンドラは、搬送されたアグリーメントを、アグリーメントのグローバルシーケンスで正しい位置において処理する。一実施形態によれば：
―  各プロセスは、メンバシップ変更提案のキーよりも大きいアグリーメントキーを用いてアグリーメントの組を無効にし（すなわち｛∃ａｋ′∈Ａ：ｋ′＞ｋ｝）、さらにそれらのアグリーメントは、最初の提案者によりm'に再提案され、再提案が一度のみ生じることを確実にすることも可能である。最初の提案者が新たなメンバシップm'において提案者の役割を有さない場合、一実施形態によるこれらのアグリーメントは廃棄可能であり、他の提案者によって再提案されることはない。
プロセスが、新たなメンバシップm'における学習者ではない場合、（出力提案シーケンスを含むのでアプリケーションが新たなアグリーメントを聞知不可能である）複製状態マシンdをアンインストールするべきでもある。
プロセスが新たなメンバシップm'のおける受諾者ではない場合、もはや複製状態マシンの動作に参加して、それに対する関連性を削除されるべきではない。
【００３８】
この動作は、図３に示される。この図３は、図２を延長して一実施形態による動的メンバシップを含む。一実施形態により、提案者が正しく機能するために常に動的メンバシップに対する学習者でなければならないという必要条件を論理が実施することが注目されるべきである。上記のように、提案者と受諾者との間で行われたアグリーメントのチームである学習者は、決定論的オーダのアグリーメントをその出力提案シーケンスを介して、アプリケーションに適用する。複製ソフトウェアバージョンコントロールシステムを備える実施形態では、例えば、システムが管理するソフトウェアレポジトリのレプリカをホスティングするように構成されたプロセスを学習者が備えることも可能である。図３に示すように、アグリーメントの提案者が学習者であると仮定すると、アグリーメントハンドリングプロセスは３０２で開始し、アグリーメントハンドラが、３０４で次のアグリーメント（すなわち｛a1, ??? , ak｝のうちの１つ）を観察して特徴付けることも可能である。特徴付けは、一実施形態によれば、現在のアグリーメントキーまたはｋlast_outputに関して受け取ったアグリーメントキーｋの比較に基づく場合もある。受け取ったキーｋが３０８で示すように、最後の出力よりも遅れている場合、現在のアグリーメントキーｋlast_outputよりも古いものとして３１０で示すように事実上無効である。受け取ったキーｋが３１２で示すように最後の出力の前にある（現在のキーｋlast_outputよりも大きい）場合、そのキーｋが現在のキーｋlast_outputに等しくなる時間まで、３１４で示すようにアグリーメントシーケンスで単に待ち状態になる可能性もあり、その時間に、出力提案シーケンスへの待ち状態となる可能性もある。３１０および３１４から、プロセスは、その後、２０２に戻り、次のアグリーメントを待つことが可能となる。
【００３９】
しかしながら、受け取られたキーｋが３１６で示すように現在のキー（ｋ＝ｋlast_output）である場合、一実施形態により、３１８においてメンバシップの変更が行われたかどうかを判断することが可能である。換言すれば、処理中のアグリーメントが行われたメンバシップが現在のメンバシップと同じメンバシップであるかどうかの判断を行ってもよい。メンバシップの変更が行われない場合（３１７のＮＯ分岐）、３２０で示すように、アグリーメントは、状態マシンの出力提案シーケンスに対して待ち状態となり得る。メンバシップ変更が実際に行われた場合（３１８のＹＥＳ分岐）、３２２で示すように、考慮中のアグリーメントを提案したプロセスが新たなメンバシップにおける提案者であるかどうか判断を行うことが可能である。このアグリーメントを提案したプロセスが、新たなメンバシップにおける提案者である場合（３２２のＹＥＳ分岐）、メンバシップが変化し、プロセスが実際には新たなメンバシップにおける提案者となる。従って、３２４に示すように、この状態マシンに関連するメンバシップは変更可能であり、このプロセスまたはノードがこの新たなメンバシップの下での提案者であるので、このノードまたはプロセスによって提案された全てのアグリーメントは、３２６で示すように、新たなメンバシップの下で（新たなメンバシップにおいて今まで通り提案者である古いメンバシップの下でそれらを提案したプロセスにより）再提案可能である。この方法はその後、３０２に戻って、次にアグリーメントを観察することも可能である。
【００４０】
しかしながら、メンバシップ変更が行われ、考慮中のアグリーメントを提案したプロセスが新たなメンバシップにおける提案者ではない場合（３２２のＮＯ分岐）、（現在の、最近変更したメンバシップである）前のメンバシップの下でこのノードによって提案された全てのアグリーメントが、一実施形態によれば、もはや現在のメンバシップではないメンバシップの下でこれらのアグリーメント全てが提案されたので、３２８に示すように廃棄される。３３０において、その後、考慮中のアグリーメントを提案したプロセスが新たなメンバシップにおける提案者ではないと決定した後、プロセスが新たなメンバシップにおける学習者であるかどうかを判断することが可能である。プロセスまたはノードが、実際に、新たなメンバシップにおける学習者である場合、状態マシンに関連するメンバシップは、３２４で示すように変更可能であり、本方法は、その後、３６２に戻ることが可能である。このノードによって以前提案されたアグリーメントは、このノードがこの新たなアグリーメントの下で提案者ではないことが確立されたため、（３２６において）再提案されない。評価中のアグリーメントを提案したプロセスが、新たなメンバシップにおける学習者ではない場合、出力提案シーケンスは、一実施形態により、もはや現在のメンバシップではないメンバシップのためのものであるため、３３２に示すようにアンインストール可能である。従って、出力状態マシンもまた、３３４で示すようにアンインストール可能である。
【００４１】
この段階では、アグリーメントが、新たなメンバシップのメンバでもあるプロセスまたはノードによって提供されたかどうかは分からない。これは３３６において判断可能であり、プロセスが、実際、新たなメンバシップにおけるメンバであり（３３６のＹＥＳ分岐）、このアグリーメントを提案したプロセスが新たなメンバシップにおける受諾者であることを意味し、この状態マシンに関連するメンバシップは、３２４で示すように、新たなメンバシップに変更可能である。このノードが新たなメンバシップにおける提案者ではないので、そのアグリーメントは再提案されず、本方法は３０２に戻り、ノードが次のアグリーメントを処理出来るのを可能にする。しかしながら、処理中のアグリーメントを提案するプロセスが、新たなメンバシップにおけるメンバではない場合、プロセスは提案者ではなく、学習者ではなく、受諾者ではなく（提案者によって行われた提言のオーダでの判断に受諾者が参加することをリコールする）、しかも状態マシンに対する全ての関連性は、３４０で削除される。本方法は、このノードが新たなメンバシップにおける役割を有さないため、３４２で示すように、このノードに対しては終了可能となる。
複製状態マシンに関連するプロセスの組を変更
【００４２】
一実施形態による動的メンバシッププロセスは、メンバシップ変更を可能化するように構成してもよく、この場合、メンバシップ内の複製状態マシンに関連するプロセスの組の役割が変更となるか、または複製状態マシンに関連するプロセスの組が縮小または拡大される。これは、失敗し、一時的にまたは永久的にオフラインとなり閉鎖されるか、または新たなプロセスが追加され、向上した機能性およびより高度なフォールトトレランスもしくはスループットを分散システムに提供するので、システムから削除されるプロセスのために必要となる可能性がある。従って、メンバシップ変更が観察されると、観察プロセスは、受諾者として追加されるか、もしくは削除され、提案者として追加されるか、もしくは削除され、学習者として追加されるか、もしくは削除され、または新たなメンバシップにおけるメンバとして削除される場合もある。
【００４３】
一実施形態によれば、メンバシップ変更が、複製状態マシンによって認識されるアグリーメントのグローバルシーケンスで、「まさに別のアグリーメント」であることをリコールされたい。従って、いずれかの提案者は、メンバシップとは関連性のないアグリーメントを提供するのみならず、アグリーメントを提案するのに使用するのと同じ機構を用いてメンバシップを変更するように構成されたアグリーメントを提案することも可能であり、このようなメンバシップ変更は、提案者の役割からいずれかのプロセスを削除することが可能である。このような動的メンバシップ変更を実現化するために、プロセスにおいて配置された複製状態マシンでは、一実施形態によれば、提案者の役割におけるいずれかのプロセスが学習者でもなければならず（すなわち、｛∀ｐ∈Ｐ:ｐ∈Ｌ｝）、ここではＰは提案者の組に対応し、Ｌは学習者の組に対応する）。そのため、提案プロセスはメンバシップ変更を（同意された場合／時）観察し、適切なアクションを講じることが可能である。しかしながら、一実施形態によれば、受諾者は学習者または提案者である必要がなく、学習者は提案者である必要がないことに注目されたい。
【００４４】
従って、実施形態による動的メンバシップにおいて使用するのに好適なメンバシップは、１組の受諾者Ａｃとして、１組の提案者Ｐと、１組の学習者Ｌ（ｍ＝｛Ａｃ，Ｐ，Ｌ｝）とを備えることも可能である。プロセスが１つまたはそれ以上の役割を果たすことが可能であるので、メンバシップにおけるプロセスの数は、グループ内の一意的プロセスの数（またはＡｃ、ＰおよびＬの組の交点の基数もしくは｜Ａｃ∩Ｐ∩Ｌ｜）、メンバシップ変更を行うために、少なくとも１人の提案者が存在しなければならない（従って、提案者の組は空であってはならず、しかもＰ＝Πは常に真でなければならない）。メンバシップ内のプロセスが提案者ではない場合、一実施形態によれば、このような変更がアグリーメント提案として扱われるため、メンバシップに対する変更を提案することが可能なメンバシップ内のプロセスは存在しない。さらに、全ての学習者または受諾者を有するメンバシップは有用ではない。何故なら、いずれかのまたは両方の役割におけるプロセスが何も行わず、受諾または出力提案シーケンスへの待ち状態とするべき提案アグリーメントを持たないからである。
新規学習者の追加
【００４５】
異なる組の学習者を含むメンバシップへのメンバシップの変更は、重要である。何故なら、メンバシップが変更されると、新たな役割にプロセスが割り当てられるのみならず、その役割、すなわちそのメンバシップの下で行われたアグリーメントのそのシーケンスに対する出力提案シーケンスの現在の値ｋlast_outputに関連する状態を交換し同期する必要条件も存在する。これが必要であるため、新規学習者によって維持されるべき出力提案シーケンスが、グローバルシーケンスで正しい点から開始する複製状態マシンへのアグリーメントの出力を開始する（これらの新たなプロセスを学習者として含んだメンバシップの変更直後のアグリーメント）。新規学習者におけるアプリケーション状態を他の学習者と同期させることも必要となり得る。例えば、ソフトウェアバージョンコントロールシステムの場合、アプリケーション状態は、複製ソフトウェアレポジトリの状態である。そのソフトウェアレポジトリの新たなレプリカが必要な場合（すなわち、新規学習者がメンバシップに追加されるべきである場合）ソフトウェアレポジトリの状態もまた、変更を協調するのに使用する複製状態マシンの状態と共に同期されなければならない。
【００４６】
従って、一実施形態による手順を以下で述べる。この手順は、複製状態マシンのメンバシップがm からm1まで変更になると、１人またはそれ以上の新規学習者をメンバシップm' に含む１組の学習者L'を複製状態マシンdに関連させる。
【００４７】
意義深いことに、一実施形態による下記の手順は、現存する学習者の組での非ブロッキングである。すなわち、新規学習者は、現存する組に影響を与えることなく１組のプロセスに追加され、それによって、新規学習者が追加される間、そのユーザに対して割り込みすることなく、システムの連続利用可能性を提供することも可能である。これは、例えば、新たなソフトウェアレポジトリサイトがプロセスの組に追加される場合、１箇所で作動するシステムのユーザには影響を与えないので、複製ソフトウェアバージョンコントロールシステム等の動的メンバシップを用いる実現化のためのかなりの利益となる。一実施形態によれば、現存する学習者の１人が、すなわち、ファイルシステムデータ等の複製状態マシンに関連するアプリケーション状態を同期させるために休止可能となる唯一の点が存在する。
新規学習者を追加するための手順
【００４８】
一実施形態によれば、新規学習者を分散コンピューティングシステム内のプロセスの組に追加する方法は、以下を備えることも可能である。
１．    メンバシップm内の全てのプロセスにおいて複製状態マシンdがインストールされると仮定する。
２．    異なる組の学習者L' を含むメンバシップm' がm' 内の全てのプロセスに配置されることを仮定する。このようなメンバシップは、例えば、動的メンバシップ変更配置のために上で示され述べられるように配置することも可能である。
３．    複製状態マシンdは、全ての新規学習者に配置され（例えば、組{∀ｌ∈Ｌ'：ｌ∈Ｌ}における全ての学習者）、さらにdは、新規学習者であるプロセスにおいてm'に関連する。全ての新規学習者が、メンバシップ変更前に複製状態マシンに関連するメンバシップである、例えばmを含まないメンバシップについて知る必要がないことに注目されたい。
４．    dがこの組の新規学習者に配置されると、複製状態マシンは、一実施形態により、動作不能状態でインストールされる。この構成では、複製状態マシンのアグリーメントハンドラは、アグリーメントエンジンからアグリーメントについてのチーム形成が可能であるが、一実施形態によれば、出力提案シーケンスを介して複製状態マシンにアグリーメントを出力しない。適正に配置された複製状態マシンdが動作不能状態にあるため、新規学習者もメンバシップm内に提案者の役割を有する場合、この新規学習者―提案者は提案することを（まだ）許可されない。
５．    メンバシップmないしメンバシップm'内のプロセスにより、メンバシップ変更提案が行われ、複製状態マシンdの、新たなメンバシップm'への関連を変更する。
６．    メンバシップ変更提案は、メンバシップmの下でdに対するアグリーメントのグローバルシーケンスで、アグリーメント（すなわちアグリーメントアイデンティティ<d, m, k>を有する＞となる。
７．    m内のノードにおけるアグリーメントハンドラによりアグリーメントのグローバルシーケンスの正確な地点でakが処理されると、複製状態マシンdの、新たなメンバシップm'へのその関連性をmから変更する。
８．    メンバシップの新規学習者を有するメンバシップへの変更を観察した直後（すなわち、m' 内の学習者の数がm' 内よりも大きい（または|L'| > |L|）
である場合）、m' 内で提案可能な各プロセス（すなわち、新たなメンバシップm' 内の提案者）は、次の利用可能なアグリーメントキーの値kを含む新規学習者を開始する（すなわち、その出力が開始するべき出力提案シーケンスにおける地点から始まる）ための提案を発行する。
注：  mおよびm' に共通する各提案者は、この開始提案の望ましいアグリーメントキーをklast_outputに設定し、これは、ｋで生じたメンバシップの変更後のキーである。mおよびm' に共通する各提案者は同一のアグリーメントキーに対する提案を発行しているので、最初の提案のみがｍ′に対するアグリーメントのグローバルシーケンスでこのklast_output + lth  スロットを「獲得」し、そのため、例え何度も提案される可能性があるとしても、１つのアグリーメントのみが作成され、学習者に理解されることになる。
９．    各々の新規学習者のアグリーメントハンドラは、アイデンティティ<d, m', k+l> 有する開始アグリーメントを処理し、アグリーメントからk+lの値を抽出し、ｋlast_outputをk+lに初期化し、klast_outputよりも遅れているアグリーメントキーｋ (k< klast_output)からいずれかの待ち状態のアグリーメントを削除する。
１０．  同期されるべきアプリケーション状態が現存しない場合、新規学習者の出力提案シーケンスが開始可能であり、klast_output + lからのアグリーメントがシーケンシャルオーダで複製状態マシンに搬送される。
このように、新規学習者は、図２で示し説明する方法で、共通開始点に同期可能であり、現在は進行中であり、現在同期された最後の出力の前にあるアグリーメントを待機している状態であり、出力提案シーケンスへの最後の出力にあるアグリーメントを待機している状態であり、最後の出力よりも遅れているアグリーメントを無効にする。しかしながら、これは、シーケンシャルオーダでbefore klast_output + l t から複製状態マシンにアグリーメントを搬送する働きはしない。一実施形態によるこのような方法を以下で述べる。
新規学習者がアプリケーション状態を同期するのを援助する手順
【００４９】
上記のように、１組の新規学習者に配置した複製状態マシンdは、それに関連するアプリケーション状態を有することも可能である。例えば、ソフトウェアバージョンコントロールシステムに対して、アプリケーション状態がシステムによって管理された複製ソフトウェアレポジトリの状態である。そのソフトウェアレポジトリの新規レプリカが必要な場合、ビジネスがいつも通りに運営し続けるのに必要な非ブロッキング行動も維持しながら、この状態を同期するのに何らかの機構が必要となる。一実施形態によれば、１人またはそれ以上の新規学習者に配置した複製状態マシンに関連するアプリケーション状態の同期は以下を含んでもよい。
１．    上記「新規学習者を追加するための手順」におけるプロセスの完了に続いて、新規学習者は、少なくとも１人の他の学習者からの助けがなくてはならないため、所定位置にて、そのアプリケーション状態を同期させるか、またはそのアプリケーション状態が同期される。
２．    従って、古いメンバシップmからの１人またはそれ以上の学習者を選択して新規学習者を援助することも可能である。Ｈは、この組のプロセスを示す（各援助者はプロセッサの組（{∀ｈ∈Ｈ:ｈ∈Ｌ}）内にあり、すなわち全ての援助者は、古いメンバシップm内の学習者であった）。一実施形態によれば、２人以上の援助者−学習者は、複製ソフトウェアバージョンコントロールレポジトリの場合に、レポジトリは大きくてもよく（例えばギガバイト）、新規学習者を転送するのにかなりの時間量を必要とする可能性もあるので特定することも可能である。多数の援助者および学習者は、許容され有益となり得るので、各新規学習者は、例えば、空間的に且つ／または地理的にそれらに近いか、またはより高い帯域幅接続によってそれらに結合させるプロセス（すなわち、新規学習者を援助するために選択された古いメンバシップmにある学習者でもあった現在のメンバシップm'の学習者）によって援助することも可能である。この援助は、ネットワークトラフィックおよびアプリケーション状態を新規学習者に転送するのに必要な時間またはそのいずれかを最小限にする。
３．    メンバシップm1における提案者（学習者でもある）は、その後、StartHelping提案をメンバシップm'に提案して、援助者Ｈの組に新規学習者を援助するべきことを知らせることも可能である。
４．    Ｈにおける各プロセスのアグリーメントハンドラは、その後、位置kの後ろにある複製状態マシンdに対してアグリーメントのグローバルシーケンスでの位置k'におけるStartHelpingを処理することも可能であり（すなわち、StartHelpingアグリーメントはアグリーメントアイデンティティ<d, m', k'>およびk' > k）を有し、その出力提案シーケンスを不能にする。これは、複製状態マシンdがアグリーメントを聞知し続ける（必要に応じてそれらをエンキューする）ことが可能であり、メンバシップm'における提案者の役割にある場合、提案を行うことが可能であることを意味するが、それはもはや複製状態マシンにアグリーメントを出力せず、それによってアプリケーション状態を一定に維持する。
５．    新規メンバシップm' における新規学習者のアプリケーション状態は、その後、同期され、例えば、帯域外転送機構を上昇させることも可能である。例えば、ファイルシステムデータが同期されている場合、新規学習者および指定した援助者を連結するネットワーク上でデータを送信するrep（独立ソフトウェアコンポーネントをより容易に統合するプログラマツール）等のファイル転送プログラウを用いてファイル転送を実施することが可能である。しかしながら、他のオンラインまたはオフライン機構を用いて、必要なアプリケーション状態を新規学習者、例えば、ピアツーピア、フラッシュストレージ、ＣＤ−ＲＯＭ、テープまたは他のランダムアクセス、シーケンシャルアクセス、固定または回転メディアデータキャリア等に転送することが可能である。
６．    ファイル転送が完了すると、m' 内の提案者は、Ｈ内のプロセスであるReEnableおよび新規学習者に提案を発行することも可能である。この提案は、新規メンバシップm' 内の大多数の受諾者によって同意されると、位置k' (またはk" > k')の後ろである複製状態マシンdに対するアグリーメントのグローバルシーケンスでの位置ｋ″におけるアグリーメントアイデンティティ<d, m', k" >が与えられる。
７．    Ｈ内の各プロセス上のアグリーメントハンドラは、状態マシンdに対するアグリーメントのグローバルシーケンスで位置k"においてReEnableアグリーメントを処理し、その出力提案シーケンスを可能化する。この点から、複製状態マシンdがk'からシーケンシャルオーダでアグリーメントの聞知を開始し（従って、そのアプリケーション状態は、改めて変更するように許可される）、さらに、その出力提案シーケンスがステップ４で休止になって以来、見失っていたアグリーメントに追いつく。
８．    m1内の各新規学習者プロセス上のアグリーメントハンドラは、複製状態マシンdに対するアグリーメントのグローバルシーケンスで位置k"におけるReEnableアグリーメントを処理する（すなわち、ReEnableアグリーメントはアグリーメントアイデンティティ<d, m', k"> および k" > k'を有する）、さらに、その出力提案シーケンスを可能化する。
９．    しかしながら、ステップ５における新規学習者に転送されたアプリケーション状態はステップk'で取られ、新規学習者の出力提案シーケンスの値klast_outputはk+lに設定される（メンバシップアグリーメント直後のアグリーメントのアグリーメントアイデンティティのキーが発生する）。従って、k+l から k' までのアグリーメントは、出力提案シーケンスには与えられず、k' からのアグリーメントのみが複製状態マシンに適用され、新規学習者がk以来見落としていたアグリーメントを複製状態マシンdに適用し、それによって、新規メンバシップm'に対して新しい学習者のアプリケーション状態を同期させる。
【００５０】
図４は、一実施形態によるコンピュータ実施方法のフローチャートである。ここで示すように、ブロックＢ４１は、コンピュータネットワーク上で複数の状態マシンにおける状態マシンの状態の複製を要求し、複数の複製状態マシンを生成する。ブロックＢ４２に示すように、複数の複製状態マシンが複数のプロセスと、全ての複製状態マシンに見え、その一貫性を維持する第１のグローバルオーダされた組のアグリーメントとに関連する場合がある。Ｂ４３で示すように、複数の複製状態マシンに関連する複数のプロセスが、第１のグローバルオーダされた組のアグリーメントにおける任意の点で変更することも可能である。この変更は、例えば、複製状態マシンが関連する複数のプロセスのうちの１つを追加または削除し、これらのプロセスのうちの１つまたはそれ以上の役割を変更するか、または複製状態マシンが関連する全てのプロセスを変更することを含んでもよい。例えば、変更は、アグリーメントが処理されるメンバシップを変更することを含んでもよい。Ｂ４４で示すように、複数の複製状態マシンに関連する複数のプロセスのうちの１つまたはそれ以上が、複数のプロセスに対する変更を行いながら、状態を変更することが可能化される場合もある。例えば、学習者が、現在のメンバシップ内の１つまたはそれ以上プロセスの役割が変更される間、複製状態マシンにアグリーメントを出力し続けることも可能である。すなわち、メンバシップ変更が行われる間は、システムはブロックされる。
【００５１】
図５は、一実施形態によるコンピュータ実施方法のさらなる局面を示すフローチャートである。Ｂ５１で示すように、コンピュータネットワーク上で受け取られたアグリーメントは、第１のメンバシップに属するプロセスに配置された第１の複製状態マシンにおいて処理可能である。このような処理は、第１のメンバシップに関連する第１のグローバルにオーダされた組のアグリーメントによって定められたオーダで達成可能である。ブロックＢ５２は、第２のグローバルにオーダされた組のアグリーメントに関連する第２のメンバシップに属するプロセス上に第１の複製状態マシンが配置されるように構成されたメンバシップを変更するためのアグリーメントを受け取ることを要求する。Ｂ５３に示すように、メンバシップを変更するためのアグリーメントは、第１のグローバルにオーダされた組のアグリーメント内の点（例えば任意の点）で処理可能である。
【００５２】
実施形態により、引き続き図５を参照すると、アグリーメントを非同期に、さらに無秩序に受け取った結果、第１のメンバシップに属するプロセスによってアグリーメントが処理される間、第１のメンバシップに属するプロセス上で処理されるように構成されたアグリーメントを受け取ることが可能である。第２のメンバシップに属するプロセス上で処理される受け取られたアグリーメントは、メンバシップを変更するべきアグリーメントが処理された後に処理するために（例えば、パワーサイクルに亘るデータを失わないパワーセーフ方法で）永続的に記憶可能である。第２のメンバシップに属するプロセス上で処理されるための記憶したアグリーメントは、その後、第２のグローバルにオーダされた組のアグリーメント内の点（例えば、任意の点）で処理可能である。第１のメンバシップに属するプロセス上に配置された複製状態マシンで受け取れられたアグリーメントは、メンバシップを変更するためのアグリーメントが処理中である時、継続して処理可能である。さらに、第１のメンバシップに属するプロセスの他のものに配置された複製状態マシンにおいて、受け取られたアグリーメントが処理中である時、第１のメンバシップからのプロセスを追加または削除可能である。第１のメンバシップに属するプロセスの役割はまた、第１のメンバシップに属するプロセスの他のものに廃止された複製状態マシンにおいて、受け取られたアグリーメントが処理中である時、変更可能である。例えば、役割変更は、プロセスの役割を提案者、受諾者および学習者またはそのいずれかに変更することを含むことが可能である。受け取られたアグリーメントは、第１のメンバシップに関連する第１のグローバルにオーダされた組のアグリーメントによって定められたオーダで、第１のメンバシップに属するプロセス上に配置された第２の複製状態マシンにおいて処理可能である。このように、第１および第２の複製状態マシンは、アグリーメントが非同期に、しかも無秩序に受け取られるので、一貫したままである。
【００５３】
有利には、ここで述べられ示される複製状態マシンの動的メンバシップの実施形態は、状態マシンの全てのレプリカによって理解されるアグリーメントのグローバルシーケンスで任意の点において状態マシンに関連するプロセスの収集が変更となるのを可能化する。実際に、一実施形態によれば、メンバシップの変更を実施するためのアグリーメントは、アグリーメントのグローバルシーケンスで任意の点において生成可能であり、システム内のプロセスは、いずれかの点において進行する（例えば、その出力提案シーケンスでアグリーメントをエンキューし、そのアプリケーション状態を変更する）ことがないようにブロックすることはない。
【００５４】
本動的メンバシップ方法およびシステムの実施形態は、状態マシンおよびその全てのレプリカによって理解されるアグリーメントにおいてグローバルシーケンスでいずれかの点において提案が行われ同意することを可能にするので、システムは、メンバシップ変更が生じる間は、利用可能状態に維持される。これは、企業にとっては重要である。何故なら、新たなノードをオンラインまたはオフラインにするためのダウンタイムおよび現存のノードの役割を変更するためのダウンタイムが無い状態で、重大なビジネス機能がエンドユーザに対して連続的に利用可能であることを確実にすることによってビジネス継続を実施形態が提供するからである。従って、実施形態は、ビジネス継続プラニング（すなわち、ダウンタイムまたは維持期間をスケジュール化し、分散コンピューティング環境に亘って、このようなダウンタイムおよび維持期間をエンドユーザに伝達する）ための必要性もまた低減する。生産性もまた向上される。何故なら、新規ノードがオンラインにされ、そのアプリケーション状態が同期される間、ユーザがこのようなメンバシップ変更中に生産的であり続けることが可能であるか、または現存のノードが故障し、代替物がオンラインにされるためである。さらに、一実施形態によれば、分散コンピューティング環境における動的メンバシップが可能化されるのみではなく、このような環境の構成ノードに対する役割の選択的関連性も同様である。
【００５５】
図６は、実施形態が実現可能なコンピュータシステム６００のブロック図を示す。コンピュータシステム６００は、情報を伝達するためのバス６０１または他の通信機構と、バス６０１と接続され、情報を処理するための１つまたはそれ以上のプロセッサ６０２とを備えることが可能である。コンピュータシステム６００は、バス６０１に接続され、情報およびプロセッサ６０２によって実行される命令を記憶するためのランダムアクセスメモリ（ＲＡＭ）または他の動的記憶装置６０４（主メモリと呼ぶ）をさらに備える。主メモリ６０４は、プロセッサ６０２による命令の実行中に、仮の変数または他の中間情報を記憶するために使用することも可能である。コンピュータシステム６００はまた、バス６０１に接続され、プロセッサ６０２のための静的情報および命令を記憶するためのリードオンリメモリ（ＲＯＭ）および他の静的記憶装置またはそのいずれか６０６を備えることも可能である。データ記憶装置６０７、例えば、磁気ディスクまたはフラッシュメモリはバス６０１に接続され、情報および命令を記憶するものであってもよい。コンピュータシステム６００はまた、バス６０１を介してディスプレイ装置６１０に接続され、コンピュータユーザへの情報を表示するためのものであってもよい。英数字と他のキーを含む英数字入力装置６２２は、バス６０１に接続され、情報およびコマンド選択をプロセッサ６０２に伝達するものであってもよい。他の型式のユーザ入力装置は、方向情報およびコマンド選択をプロセッサ６０２に伝達し、ディスプレイ６２１上のカーソル移動を制御するためのマウス、トラックボールまたはカーソル方向キー等のカーソルコントロール６２３である。コンピュータシステム６００は、通信装置（例えば、モデム、ＮＩＣ）を介して、ネットワーク６２６および分散コンピューティングシステムの１つまたはそれ以上のノードに接続することも可能である。
【００５６】
実施形態は、コンピュータシステムの使用および複数のこのようなコンピュータシステムまたはそのいずれかに関連し、分散コンピューティングシステムにおける複製状態マシンにおいてメンバシップを作成し、配置し、且つ動的に変化させる。一実施形態によれば、ここで述べる方法およびシステムは、メモリ６０４に含まれる命令のシーケンスを実行するプロセッサ６０２に応答して、１つまたはそれ以上のコンピュータシステム６００によって提供することも可能である。このような命令は、データ記憶装置６０７等の別のコンピュータ可読媒体からメモリ６０４内に読み出し可能である。メモリ６０４内に含まれる命令のシーケンスの実行により、プロセッサ６０２がステップを実施し、ここで述べる機能性を有することになる。代わりの実施形態では、ソフトウェア命令の代わりに、またはそれと組み合わせてハードワイヤード回路を用いて、本発明を実現化することが可能である。このように、本発明は、ハードウェア回路およびソフトウェアの特定の組み合わせには限定されない。実際には、いずれかの好適なコンピュータシステムが、ここで述べる機能性を実現化可能であることを当業者は理解するべきである。コンピュータシステムは、望ましい機能を実施するための１つまたは複数のマイクロプロセッサの作業を含むことも可能である。一実施形態において、１つまたはそれ以上のマイクロプロセッサによって実行される命令は、マイクロプロセッサが、ここで述べるステップを実施するように動作可能である。命令は、いずれかのコンピュータ可読媒体に記憶可能である。一実施形態では、それらは、マイクロプロセッサの外部にある、またはマイクロプロセッサと一体化された不揮発性半導体メモリ上に記憶可能である。別の実施形態では、命令は、マイクロプロセッサによって実行される前にディスクに記憶され、揮発性半導体メモリに読み出し可能である。
【００５７】
開示の実施形態を述べたが、これらの実施形態は、例としてのみ提示されたものであり、開示の範囲を限定することを意図されていない。実際には、ここで述べた新規な方法、装置およびシステムは、様々な他の形式で具体化することも可能である。さらに、ここで述べた方法およびシステムの形式での様々な省略、代用および変更は、本開示の精神を逸脱することなく行われ得る。添付の請求の範囲およびその均等物は、本開示の範囲および精神に含まれるものとしてこのような形式または変更を網羅するように意図されている。例えば、当業者は、様々な実施形態において、実際の物理的および論理的構造が図面に示すものとは異なる可能性があることを認識するであろう。実施形態に依り、上記実施例で述べたステップが削除され、他のものが追加されてもよい。また、上記特定の実施形態の特徴および属性は、異なる方法で組み合わされ、さらなる実施形態を形成することも可能であり、その全ては、本開示の範囲内にある。本開示は、好ましい実施形態および適用を提供するが、ここで述べた特徴および利点の全てを提供するわけではない実施形態を含む、当業者に明らかな他の実施形態もまた本開示の範囲内である。従って、本開示の範囲は、添付の請求の範囲を参照してのみ定められるものであることが意図されている。
【図１】
2016510924.tif 000003
【図２】
2016510924.tif 000004
【図３】
2016510924.tif 000005
【図４】
2016510924.tif 000006
【図５】
2016510924.tif 000007
【図６】
2016510924.tif 000008
【国際調査報告】
2016510924.tif 000009
2016510924.tif 000010
2016510924.tif 000011