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