(57)【要約】【課題】  分散障害許容型コンピューティングシステムにおける効率のよいレプリカセットの変更を提供する。【解決手段】  分散コンピューティングシステムは、コンピューティングデバイスの集合を使って障害許容方式で運用される。コンピューティングデバイスの集合は、状態マシンの同一のレプリカを実施し、提案を選択することにより、いくつかの障害を許容する。レプリカをホストすることによって分散コンピューティングシステムに参加しているコンピューティングデバイスの集合は、その集合にコンピューティングデバイスを追加し、またはそこから除去することによって変更される。欠陥のあるデバイスを動作可能なデバイスと交換することによって、あるいはシステム中の冗長量を増大させることによってその集合に参加するコンピューティングデバイスを変更することにより、耐障害性が増大する。【選択図】  図６
2006004434.tif 000002
【特許請求の範囲】
【請求項１】
状態マシンによってステップシーケンスとして実行される操作を決定するコンピューティングデバイスの第１の集合を備える障害許容型分散コンピューティングシステムにおいて、コンピューティングデバイスの第２の集合が前記ステップシーケンスでの操作を決定することを可能にする方法であって、
前記第１の集合中のあるコンピューティングデバイスによって、前記コンピューティングデバイスの第２の集合を指定すること、
１つのステップを、前記第１の集合が、それについて前記状態マシンによって実行される操作を決定する最後のステップであると指定すること、および
前記第２の集合中の前記コンピューティングデバイスによって、前記指定されたステップに続くステップにおいて前記状態マシンによって実行される操作を決定すること
を備えることを特徴とする方法。
【請求項２】
前記第２の集合中の１つまたは複数のコンピューティングデバイスによって、前記第１の集合中の１つまたは複数のコンピューティングデバイスの確実性を検証すること
をさらに備えることを特徴とする請求項１に記載の方法。
【請求項３】
ポリシーに応答して自動的に開始されることを特徴とする請求項１に記載の方法。
【請求項４】
明示的ユーザ要求に応答して開始されることを特徴とする請求項１に記載の方法。
【請求項５】
第１のコンピューティングデバイスの集合を備える障害許容型分散コンピューティングシステムであって、前記第１の集合中の各コンピューティングデバイスは状態マシンのレプリカを実行し、前記状態マシン上で実行される操作は前記第１の集合のリーダによって提案されるシステムにおいて、それぞれが前記状態マシンのレプリカを実行するコンピューティングデバイスの第２の集合を作成する方法であって、
前記第１の集合中のあるコンピューティングデバイスによって、前記第２の集合を作成するよう要求すること、
前記第１の集合中の定足数の前記デバイスの間で、前記第２の集合を構成する前記コンピューティングデバイスが所与のステップの後で前記状態マシンを実行することに合意すること、
前記第１の集合の前記リーダによって、前記所与のステップに到達するために前記状態マシンでの十分な数のヌル操作を提案すること
を備えることを特徴とする方法。
【請求項６】
ポリシーに応答して自動的に開始されることを特徴とする請求項５に記載の方法。
【請求項７】
明示的ユーザ要求に応答して開始されることを特徴とする請求項５に記載の方法。
【請求項８】
前記第２の集合中の１つまたは複数のコンピューティングデバイスによって、前記第１の集合中の１つまたは複数のコンピューティングデバイスの確実性を検証すること
をさらに備えることを特徴とする請求項５に記載の方法。
【請求項９】
前記リーダによって提案される操作は、前記第１の集合中の定足数のコンピューティングデバイスが前記提案に同意した場合に限って前記状態マシンによって実行されることを特徴とする請求項５に記載の方法。
【請求項１０】
複数のコンピューティングデバイスを備える障害許容型分散コンピューティングシステムであって、前記コンピューティングデバイスの第１の集合は、第１のステップシーケンスで状態マシンによって実行される操作を決定し、前記コンピューティングデバイスの第２の集合は、第２のステップシーケンスで前記状態マシンによって後で実行される操作を決定し、前記第１および第２のシーケンスは互いに排他的であるシステムにおいて、
前記状態マシンのステップにおける操作を実行する実行モジュールと、
前記第１の集合中の他のコンピューティングデバイスと連係して前記第１のシーケンスでの操作を決定する第１の同意モジュールと
によって実行を円滑化する、第１のコンピューティングデバイス上での実行のためのコンピュータ実行可能命令を含むことを特徴とするコンピュータ可読媒体。
【請求項１１】
前記コンピュータ実行可能命令は、
前記第２の集合中の他のコンピューティングデバイスと連係して前記第２のシーケンスでの操作を決定する第２の同意モジュール
によってさらに実行を円滑化することを特徴とする請求項１０に記載のコンピュータ可読媒体。
【請求項１２】
前記第１の同意モジュールは、前記実行モジュールが前記第１のシーケンスの前記ステップを実行した後に破棄されることを特徴とする請求項１０に記載のコンピュータ可読媒体。
【請求項１３】
破棄される前に、前記第１の同意モジュールは、前記コンピューティングデバイスの第２の集合が前記状態マシンによって実行される操作を決定することを保証するために、前記第２の集合中の１つまたは複数のコンピューティングデバイスにポーリングすることを特徴とする請求項１２に記載のコンピュータ可読媒体。
【請求項１４】
破棄される前に、前記第１の同意モジュールは、前記第２の集合中の定足数のコンピューティングデバイスが、安定した記憶に、前記第１のステップシーケンスでの最後の操作の実行の直後の前記状態マシンの状態を記憶していることを保証することを特徴とする請求項１３に記載のコンピュータ可読媒体。
【請求項１５】
前記破棄された第１の同意モジュールは、前記コンピューティングデバイスの第２の集合に関する情報を維持することを特徴とする請求項１２に記載のコンピュータ可読媒体。
【請求項１６】
前記実行モジュールは、前記コンピューティングデバイス上に同意モジュールが残っていない場合に破棄されることを特徴とする請求項１２に記載のコンピュータ可読媒体。
【請求項１７】
前記コンピューティングデバイスの第１の集合はリーダデバイスを含み、前記第１のシーケンスにおける操作は、前記第１の集合中の定足数のコンピューティングデバイスが前記リーダデバイスによるその操作についての提案に同意した場合に限って、前記状態マシンによって実行されることを特徴とする請求項１０に記載のコンピュータ可読媒体。
【請求項１８】
複数のコンピューティングデバイスを備える障害許容型分散コンピューティングシステムであって、前記コンピューティングデバイスの第１の集合は、第１のステップシーケンスで状態マシンによって実行される操作を決定し、前記コンピューティングデバイスの第２の集合は、第２のステップシーケンスで前記状態マシンによって実行される操作を決定し、前記第１および第２のシーケンスは互いに排他的であり、前記第１のステップシーケンスは前記第２のステップシーケンスに先行するシステムにおいて、
前記状態マシンの操作を実行する実行モジュールと、
前記第１の集合中の他のコンピューティングデバイスと連係して前記第１のシーケンスでの操作を決定する第１の同意モジュールと
を備えることを特徴とするコンピューティングデバイス。
【請求項１９】
前記第２の集合中の他のコンピューティングデバイスと連係して前記第２のシーケンスでの操作を決定する第２の同意モジュール
をさらに備えることを特徴とする請求項１８に記載のコンピューティングデバイス。
【請求項２０】
前記第１の同意モジュールは、前記実行モジュールが前記第１のシーケンスの前記ステップを実行した後に破棄されることを特徴とする請求項１８に記載のコンピューティングデバイス。
【請求項２１】
破棄される前に、前記第１の同意モジュールは、前記コンピューティングデバイスの第２の集合が前記状態マシンによって実行される操作を決定することを保証するために、前記第２の集合中の１つまたは複数のコンピューティングデバイスにポーリングすることを特徴とする請求項２０に記載のコンピューティングデバイス。
【請求項２２】
破棄される前に、前記第１の同意モジュールは、前記第２の集合中の定足数のコンピューティングデバイスが、安定した記憶に、前記第１のステップシーケンスでの最後の操作の実行の直後の前記状態マシンの状態を記憶していることを保証することを特徴とする請求項２１に記載のコンピューティングデバイス。
【請求項２３】
前記破棄された第１の同意モジュールは、前記コンピューティングデバイスの第２の集合に関する情報を維持することを特徴とする請求項２０に記載のコンピューティングデバイス。
【請求項２４】
前記実行モジュールは、前記コンピューティングデバイス上に同意モジュールが残っていない場合に破棄されることを特徴とする請求項２０に記載のコンピューティングデバイス。
【請求項２５】
前記実行モジュールは、前記第１の集合によって決定されたステップまでヌル操作を実行し、前記決定されたステップの後で前記第２のシーケンスの操作を実行することを特徴とする請求項１９に記載のコンピューティングデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、分散コンピューティングに関し、より詳細には、障害許容型分散コンピューティングに関する。
【背景技術】
【０００２】
分散システムの１つの利点は、単一の、モノリシックなコンピューティングデバイスを損なうことになる物理的障害に直面しても動作し続けることができることである。そのような障害には、持続的停電、悪天候、洪水、テロリスト活動などが含まれ得るであろう。
【０００３】
個々のメンバコンピューティングデバイスがネットワークから切断され、電源を切られ、システム誤動作を生じ、あるいはそれ以外の理由で使用不能になり得る増大する危険を補償するために、冗長を用いて、分散コンピューティングシステムに動作可能な状態を続行させることができる。ゆえに、任意の１つのコンピューティングデバイス上に格納される情報またはそこで実行されるプロセスはその他のコンピューティングデバイス上に重複して格納され、それらのコンピューティングデバイスの１つが故障した場合でも、その情報をアクセス可能なままに保つことができる。
【０００４】
分散コンピューティングシステムは、そのシステム内のあらゆるデバイスが同一のタスクを実行し、同一の情報を格納する完全な冗長を実施することができる。そのようなシステムは、それらのデバイスのほぼ半分が故障した場合でも、ユーザが有用な操作を実行し続けられるようにすることができる。代替として、そのようなシステムを使って、同じ情報の複数のコピーをある地理的領域全体にわたって分散させることもできる。例えば、多国籍企業は、世界規模の分散コンピューティングシステムを構築することができる。
【０００５】
しかしながら、分散コンピューティングシステムは、システムを構成する個々のデバイスが同じ順序で同一の操作を実行することを適正に保証することの複雑さのために、維持するのが難しいことがある。この困難の多いタスクを円滑に行わせるために、しばしば、状態マシンの手法を使って、個々のデバイス間のアクティビティが調整される。状態マシンは、１組の状態、１組のコマンド、１組の応答、および１つの応答／状態対を各コマンド／状態対にリンクさせるクライアントコマンドによって説明され得る。状態マシンは、その状態を変更し、応答を生成することによってコマンドを実行することができる。ゆえに、状態マシンは、その現在の状態、およびそれが実行しようとしているアクションによって完全に記述され得る。
【０００６】
したがって、状態マシンの現在の状態は、その前の状態、その後に実行されたコマンド、およびそれらコマンドが実行された順序に依存する。２つ以上に状態マシン間の同期を維持するために、共通の初期状態が設定され、各状態マシンは、その初期状態から開始して、同一のコマンドを同一の順序で実行することができる。したがって、ある状態マシンを別の状態マシンに同期させるためには、他方の状態マシンによって実行されたコマンドが決定される必要がある。したがって、同期の問題は、実行されたコマンドの順序を決定する問題、より具体的には、所与のステップで実行された特定のコマンドを決定する問題になる。
【０００７】
所与のステップでどのコマンドが実行されるべきか決定する１つの機構は、パクソス（Ｐａｘｏｓ）アルゴリズムと呼ばれる。パクソスアルゴリズムでは、個々のデバイスのいずれもリーダとして働き、システム中のあらゆるデバイスによる実行のために所与のクライアントコマンドを提案しようとすることができる。そのようなあらゆる提案は、それらの提案をより容易に追跡できるように、提案番号と共に送られ得る。そのような提案番号は、それらのデバイスが、それについて実行するコマンドに合意しようとする特定のステップに全く関係なくてもよい。最初に、リーダは、そのリーダが提出しようとする提案の提案番号を示唆することができる。次いで、残りのデバイスのそれぞれは、そのリーダの提案番号の示唆に応答して、それらが賛成投票した最後の提案を示し、またはそれらがどんな提案にも賛成投票していないことを示す。リーダが、様々な応答を介して、それらのデバイスによって賛成投票された他のどんな提案も確認しなかった場合、リーダは、先のメッセージで示唆した提案番号を使って、それらのデバイスによって所与のクライアントコマンドが実行されるよう提案することができる。各デバイスは、その段階で、そのアクションに賛成投票すべきか、それともそれを拒否すべきか決定することができる。デバイスがアクションを拒否すべきなのは、より大きい提案番号を持つ別のリーダの示唆に応答している場合だけである。定足数と呼ばれる、十分な数のデバイスがその提案に賛成投票した場合、その提案されたアクションは合意されているといい、各デバイスはそのアクションを実行し、その結果を送ることができる。そのようにして、デバイスのそれぞれが同じ順序でアクションを実行し、それらのデバイスすべての間で同じ状態を維持することができる。
【０００８】
一般に、パクソスアルゴリズムは、前述のように、リーダに、各デバイスによって投票された前の提案を確認させる最初の段階と、リーダが実行のためのクライアントコマンドを提案することができる第２の段階の、２つの段階として考察され得る。リーダは、前の提案を確認した後では、最初の段階を絶えず繰り返す必要はない。その代わりに、リーダは、第２の段階を頻繁に繰返し、複数のステップで分散コンピューティングシステムによって実行され得る一連のクライアントコマンドを提案し続けることができる。そのように、各ステップごとに分散コンピューティングシステムによって実行される各クライアントコマンドは、パクソスアルゴリズムの一例とみなされ得るが、リーダは、次のステップでの別のクライアントコマンドを提案する前に、各デバイスが所与のステップでのクライアントコマンド提案に投票するのを待つ必要はない。
【０００９】
分散コンピューティングシステムは、全体が、１つの状態マシンとしてモデル化され得る。ゆえに、完全な冗長を実施する分散コンピューティングシステムは、各デバイスが、同じ状態マシンのそれ自体の「レプリカ」をホストするように、デバイスのそれぞれに、システム全体の状態を複製させることができる。そのようなシステムは、各レプリカが同じ状態を維持することを必要とする。いくつかのレプリカはあるクライアントコマンドが実行されたと考え、第２のレプリカグループは異なるクライアントコマンドが実行されたと考える場合、そのシステム全体はもはや単一の状態マシンとして動作しない。そのような状況を回避するため、システムによる実行には、一般に、それらのレプリカの過半数が提案されたクライアントコマンドを選択することが必要とされ得る。それぞれ過半数を有する任意の２つのレプリカグループは少なくとも１つレプリカを共用するため、その少なくとも１つの共通のレプリカを利用して、それぞれ過半数のレプリカを含む２つのグループが、異なるクライアントコマンド提案を選択するのを防ぐ、パクソスアルゴリズムなどの機構が実施され得る。
【非特許文献１】Leslie Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System," The Communications of the ACM, Volume 21, Number 7, July 1978
【非特許文献２】Leslie Lamport, "The Part-Time Parliament," ACM Transactions on Computer Systems, volume 16, number 2, pages 133-169, May 1998
【非特許文献３】Leslie Lamport, "Paxos Made Simple," ACM SIGACT News, volume 32, number 4, pages 18-25, December 2001
【非特許文献４】Adya, et al., "FARSITE: Federated, available, and reliable storage for an incompletely trusted environment," Proc. 5th OSDI, pp. 1-14, Boston, MA, Dec. 2002
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、長期間運用することが期待されるシステムは、デバイスが永続的に廃棄され、またはデバイスに別の永続な障害が発生する状況を処理しなければならない。したがって、システムは、システムのその後の障害に対する許容度がその元のレベルに復元されるように、いくつかのデバイスを取り外し、他のデバイスと交換する（すなわち、状態マシンのレプリカセットを変更する）手段を設ける必要がある。そうでない場合、定足数の障害が発生すると、システムはもはや障害許容型でなくなる。障害のあるデバイスを交換すれば、システムの耐障害性が復元されて新しい障害が許容される。さらに、システムは、許容可能なデバイス障害数を増大させ、それによってより大きい耐障害性を提供するために、新しいデバイスの追加を許容する必要がある。本来のパクソスアルゴリズムは、システムが、どのようにしてプロトコルに関与する状態マシンのレプリカセットの変更を決定し得るかについての簡単な記述を与える。しかし、本来のパクソスアルゴリズムによって提示される手法は、レプリカセットの変更中に生じ得る様々な特殊な状況に対処するものではない。
【課題を解決するための手段】
【００１１】
分散コンピューティングシステムは、コンピューティングデバイスの集合を使って障害許容型として運用され得る。コンピューティングデバイスの集合は、状態マシンの同一のレプリカを実施し、パクソスアルゴリズムを使って提案を選択することにより、いくつかの障害を許容し得る。本発明の実施形態は、分散コンピューティングシステムに参加するコンピューティングデバイスの集合を、その集合にコンピューティングデバイスを追加し、またはそこから除去することによって、あるいは参加する特定のコンピューティングデバイスを指定することによって変更することを可能にする。欠陥のあるデバイスを動作可能なデバイスと交換することによって、あるいはシステム中の冗長量を増大させることによってその集合に参加するコンピューティングデバイスを変更することにより、耐障害性が増大する。
【００１２】
したがって、本発明の一実施形態では、コンピューティングデバイスの第１の集合は、デバイス間で複製されている状態マシンによって実行されるステップシーケンスを決定する責任を負う。第１の集合からこの責任を取り除き、状態マシンによって実行されるステップシーケンスでのステップを決定する責任を担う第２のデバイスの集合が定義され得る。第１の集合がその責任を負うステップの範囲と第２の集合が責任を負うステップの範囲とは相互に排他的である。
【００１３】
本発明の別の実施形態では、状態マシンによって実行されるステップシーケンスを決定する責任を負うコンピューティングデバイスの第１の集合のリーダは、その集合の後を継ぐコンピューティングデバイスの新しい集合が選択されていることを知る。その新しい集合は、指定されたステップから開始するステップシーケンスを決定する責任を負い、第１の集合のリーダは、指定されたステップの前のステップで実行されるステップとして、ヌル操作を決定させる。
【００１４】
本発明の別の実施形態では、同一の状態マシンのレプリカを実行しているコンピューティングデバイスは、１つの実行モジュールおよび１つまたは複数の同意モジュールをホストする。各デバイスの実行モジュールは、順次、複製された状態マシンのステップを実行する。各デバイスは、それがメンバである各レプリカセットに対応する同意モジュールを備える。同じマシン上の異なるレプリカセットの同意モジュールは、それぞれ、そのステップシーケンスでの選択された操作を提供するために、そのマシン上の単一の実行モジュールとやりとりする。
【００１５】
本明細書の説明は、主に、分散コンピューティングシステムにおけるコンピューティングデバイスの動作を中心に行うが、この説明は、別々のプロセッサ上や、別々のメモリ空間など、単一のコンピューティングデバイス上で実行中のプロセスにも等しく適用可能であることが理解されるであろう。ゆえに、別の実施形態は、複数プロセッサ環境において（それら複数のプロセッサが物理的に１つのコンピューティングデバイスに位置するのであれ、複数のコンピューティングデバイスに位置するのであれ）、および複数仮想マシン環境において（それら複数の仮想マシンが１つのコンピューティングデバイスによって実行されているのであれ、複数のコンピューティングデバイスによって実行されているのであれ）変更されたパクソスアルゴリズムの操作を含む。本発明のその他の特徴および利点は、添付の図を参照して進められる以下の例示的実施形態の詳細な説明を読めば明らかになるであろう。
【００１６】
特許請求の範囲では本発明の特徴を詳細に記述するが、本発明は、ならびにその目的および利点は、以下の詳細な説明を添付の図面と併せて読めば最もよく理解されると考えられる。
【発明を実施するための最良の形態】
【００１７】
分散コンピューティングシステムは、いくつかの個別のパーソナルコンピューティングデバイス、サーバコンピューティングデバイス、またはシステムに参加するのに十分なプロセッサおよび記憶能力を備える他のデバイスを備えることができる。分散コンピューティングシステムは、大幅に増大された処理能力および記憶空間を提供するために、あるいは冗長を実施し、複数のデバイスが同じ情報にアクセスできるようにするために、その構成コンピューティングデバイスの能力を集約することができる。ゆえに、分散コンピューティングシステムの１つの一般的な用法は、共通のネットワークに接続された多種多様なパーソナルコンピューティングデバイスの処理能力および記憶空間の集約である。そのような分散コンピューティングシステムは、どのデバイスが現在そのシステムの一部であるか、どのデバイス上に所与の情報セットが格納されているかなど、そのシステムに関する情報を維持することができる。この情報は、それらのデバイスがその能力および記憶空間を集約するのに必要なことがあり、その結果として、各デバイスはコピーを含み得る。システムのデバイス間での情報の同期は、以下で説明する状態マシンによって円滑化され得る。
【００１８】
代替として、分散コンピューティングシステムのより一般的な一用法が、様々な形の情報の中央記憶リポジトリとして働くことのできるネットワークサーバとしての用法である。そのような分散システムは、その構成デバイスすべての上にセントラルストアを複製して、セントラルストアと通信することを求めるあらゆるクライアントが、通信するのに好都合で効率のよいデバイスを見つけ出せるようにしようとする。さらに、システムの分散性のために、停電、洪水、政情不安などの局所的イベントはわずかなコンピューティングデバイスだけにした影響を及ぼさず、システム全体が適正に動作し、クライアントに情報およびその他のサービスへのアクセスを提供し続けることを可能にする。
【００１９】
そのような分散コンピューティングシステムは、マシンの将来の状態が現在の状態および講じられるアクションによって定義される、状態マシンとみなされ得る。その場合、分散コンピューティングシステムの各構成デバイスは、システム全体の状態マシンを独立に実行することができる。状態マシンの手法は非同期的に実施され得る。そのため、構成デバイス間の厳密な共時性は維持される必要がなく、デバイス間の同期は、それらのデバイスすべてでの初期状態を設定し、その後同じ機能を同じ順序で実行することによって達成され得る。同期を維持する一般的な方法は、分散コンピューティングシステムの構成デバイスに、次の機能を実行する前にその機能にすべて同意させ、実行された機能のリストを維持することである。そのようにして、あらゆるデバイスが同じ状態を持つことができ、あるデバイスに障害が発生した場合、それは、それが実行した最後の機能を決定し、リストから、その最後の機能以後に合意されている機能を識別し、それらの機能を実行するだけでよい。
【００２０】
サーバとして働く分散コンピューティングシステムは、多国籍企業の中央データベースや、人気のあるワールドワイドウェブサイトなど、多様なクライアントの集合に大量の情報を提供するのに特に役立ち得る。そのような状況では、多数のクライアントが、サーバとして働く分散コンピューティングシステムに情報を要求し得る。多数のデバイスでそのサーバ機能を実施することによって、そのサーバは、増大した冗長のために、全体としてはるかに障害の影響を受けにくくなる。
【００２１】
構成コンピューティングデバイスが実行する次の機能に合意するための１つの機構は、パクソスアルゴリズムと呼ばれる。パクソスアルゴリズムでは、以下でより詳細に説明するように、どのデバイスもリーダとして働き、その分散コンピューティングシステム内の他のデバイスに提案番号の示唆を送ることができる。その他のデバイスはそれに応答して、そのデバイスがすでに賛成投票している最大の提案番号を持つ提案を示し、またはそのデバイスが以前のどの提案にも賛成投票していないと示すことができる。リーダは、その他のデバイスから応答を受け取った後で、どの機能を提案するか決定し、提案した機能への投票を要求することができる。各デバイスは、それが、その要求された投票の前のいつかに、より大きい提案番号での示唆に応答していない限り、その提案に賛成投票する。定足数のデバイスがその提案に賛成投票した場合、その提案は受け入れられ、リーダは、それらのデバイスすべてに、それらが合意された機能を実行するよう要求するメッセージを送ることができる。
【００２２】
しかしながら、パクソスアルゴリズムは、他の任意の合意アルゴリズムと同様に、多数のコンピューティングデバイスが障害を許容することを必要とする。具体的には、Ｆという数の障害を許容するには、このアルゴリズムは、少なくとも２Ｆ＋１という数のコンピューティングデバイスを備える分散コンピューティングシステムを必要とする。コマンドを選択し、システムの適正な動作を続行するには、これらのデバイスのうちの単純な過半数だけがあればよい。残りのデバイスは、コマンドを選択し、システムを動作させるそれらのデバイスの１つに障害が発生するまで未使用のままとすることができる。
【００２３】
しかしながら、１つのコンピューティングデバイスに永続的な障害が発生した場合には、それを２Ｆ＋１個のデバイスの集合から除去し、それを新しいデバイスで置き換えて、パクソスアルゴリズムがＦ個のさらなる障害を許容することができるようにすることが望ましい。
【００２４】
分散コンピューティング環境
図面を見ると、本発明は、図１に示す例示的分散コンピューティングシステム１０などの分散コンピューティングシステムによって実施されるものとして示されている。図面中、類似の参照番号は類似の要素を指す。説明を容易にするためにすぎないが、以下では、本発明を、図１に示すように相互接続されたコンピューティングデバイス１１から１５を備えるシステム１０などの分散コンピューティングシステムを参照して説明する。当分野の技術者には理解されるように、本発明は、すべての分散コンピューティングシステムに適用可能であり、どんな意味でも、説明のために簡略化されている、図１の例示的分散コンピューティングシステムに限定されるものではない。
【００２５】
図１には、単一のクライアントコンピューティングデバイス２０も示されているが、本発明は、任意の数のクライアントコンピューティングデバイスを備える環境で動作することが意図されている。クライアントコンピューティングデバイス２０は、分散コンピューティングシステム１０への一般的な通信接続を備えるものとして示されている。当分野の技術者には知られているように、そのような通信接続は、任意の通信媒体およびプロトコルを使用することができ、クライアントコンピューティングデバイス２０に、分散コンピューティングシステム１０中のコンピューティングデバイスの１つまたは複数と通信させることができる。
【００２６】
また、図１には、分散コンピューティングシステム１０の一部として示されていないが、やはりシステム１０への一般的通信接続を維持するコンピューティングデバイス３０および３１も示されている。前述のように、この通信接続は、任意の通信媒体およびプロトコルを使用することができ、コンピューティングデバイス３０および３１に、分散コンピューティングシステム１０中のコンピューティングデバイスの１つまたは複数と通信させることができる。以下でより詳細に説明するように、コンピューティングデバイス３０および３１は、システム１０の一部とならずに、システム１０によって行われた実行結果を知ることができる。
【００２７】
必須ではないが、以下では本発明を、コンピューティングデバイスによって実行される、プログラムモジュールなどのコンピュータ実行可能命令の一般的状況で説明する。一般に、プログラムモジュールには、個々のタスクを実行し、または個々の抽象データ型を実施するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが含まれる。さらに、本発明が、ハンドヘルド機器、マルチプロセッサシステム、マイクロプロセッサベースの、またはプログラム可能な家庭用電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータなどを含む、多種多様なコンピューティングデバイスと共に実施され得ることも当分野の技術者は理解するであろう。前述のように、本発明は、タスクが、通信ネットワークを介してリンクされたリモート処理装置によって実行される、分散コンピューティングシステム１０などの分散コンピューティング環境でも実施され得る。分散コンピューティング環境では、プログラムモジュールは、ローカルとリモート両方のメモリ記憶装置に位置することができる。
【００２８】
図２を見ると、本発明が実施され得る例示的コンピューティングデバイス１００が示されている。コンピューティングデバイス１００は、適当なコンピューティングデバイスの一例にすぎず、本発明の範囲または機能に関するどんな限定を示唆するものでもない。例えば、例示的コンピューティングデバイス１００は、図１に示すコンピューティングデバイス１１〜１５、２０、または３０〜３１のいずれも正確に表すものではない。例示的コンピューティングデバイス１００は、これらのコンピューティングデバイスの１つまたは複数を、メモリ分割、仮想マシン、マルチプロセッサ、あるいは１つの物理的コンピューティング構造に、複数のコンピューティングデバイスに起因する以下で説明するアクションを実行させる類似のプログラミング技法などによって実施することができる。さらに、コンピューティングデバイス１００は、図２に示す周辺装置のいずれか１つまたはその組み合わせに関連するどんな依存関係や要件を持つものであるとも解釈されるべきではない。
【００２９】
本発明は、コンピュータにより実行される、プログラムモジュールなどのコンピュータ実行可能命令の一般的状況で説明することができる。一般に、プログラムモジュールには、個々のタスクを実行し、または個々の抽象データ型を実施するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが含まれる。分散コンピューティング環境では、タスクは、通信ネットワークを介してリンクされたリモート処理装置により実行され得る。分散コンピューティング環境では、プログラムモジュールは、ローカルとリモート両方のメモリ記憶装置を含むコンピュータ記憶媒体に位置し得る。
【００３０】
コンピューティングデバイス１００の構成要素には、それだけに限らないが、処理装置１２０、システムメモリ１３０、およびシステムメモリを含む様々なシステム構成要素を処理装置１２０に結合するシステムバス１２１が含まれ得る。システムバス１２１は、様々なバスアーキテクチャのいずれかを使ったメモリバスまたはメモリコントローラ、周辺バス、およびローカルバスを含む数種類のバス構造のいずれでもよい。例をあげると、それだけに限らないが、そのようなアーキテクチャには、産業標準アーキテクチャ（ＩＳＡ）バス、マイクロチャネルアーキテクチャ（ＭＣＡ）バス、拡張ＩＳＡ（ＥＩＳＡ）バス、ビデオ電子装置規格化協会（ＶＥＳＡ）ローカルバス、およびメザニンバスとも呼ばれる周辺装置相互接続（ＰＣＩ）バスが含まれる。さらに、処理装置１２０は、１つまたは複数の物理的プロセッサを含み得る。
【００３１】
コンピューティングデバイス１００は、通常、様々なコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピューティングデバイス１００からアクセスし得る任意の使用可能な媒体とすることができ、それには揮発性媒体と不揮発性媒体の両方、取り外し可能媒体と取り外し不能媒体の両方が含まれる。例をあげると、それだけに限らないが、コンピュータ可読媒体には、コンピュータ記憶媒体および通信媒体が含まれ得る。コンピュータ記憶媒体には、コンピュータ可読命令、データ構造、プログラムモジュールまたはその他のデータなどの情報を記憶するための任意の方法または技術で実施された、揮発性と不揮発性両方、取り外し可能と取り外し不能両方の媒体が含まれる。コンピュータ記憶媒体には、それだけに限らないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリなどのメモリ技術、ＣＤ−ＲＯＭ、ディジタル多用途ディスク（ＤＶＤ）などの光ディスク記憶、磁気カセット、磁気テープ、磁気ディスク記憶などの磁気記憶装置、あるいは所望の情報を記憶するのに使用でき、コンピューティングデバイス１００からアクセスし得る他の任意の媒体が含まれる。通信媒体は、通常、コンピュータ可読命令、データ構造、プログラムモジュールまたはその他のデータを、搬送波または他の搬送機構などの変調データ信号として実施し、任意の情報配信媒体を含む。「変調データ信号」という用語は、その特性の１つまたは複数が、その信号に情報を符号化するような方式で設定または変更されている信号を意味する。例をあげると、それだけに限らないが、通信媒体には、有線ネットワークや直接配線接続などの有線媒体、および音響、ＲＦ、赤外線、その他の無線媒体などの無線媒体が含まれる。上記のいずれかの組み合わせも、コンピュータ可読媒体の範囲内に含むべきである。
【００３２】
システムメモリ１３０は、読取り専用メモリ（ＲＯＭ）１３１やランダムアクセスメモリ（ＲＡＭ）１３２などの揮発性および／または不揮発性メモリの形でコンピュータ記憶媒体を含む。始動時などに、コンピューティングデバイス１００内の要素間の情報転送を支援する基本ルーチンを含む基本入出力システム（ＢＩＯＳ）１３３は、通常、ＲＯＭ１３１に格納される。ＲＡＭ１３２は、通常、処理装置１２０から直ちにアクセス可能であり、かつ／またはそれによって現在処理されているデータおよび／またはプログラムモジュールを含む。例として、それだけに限らないが、図２に、オペレーティングシステム１３４、アプリケーションプログラム１３５、その他のプログラムモジュール１３６、およびプログラムデータ１３７を示す。
【００３３】
コンピューティングデバイス１００は、他の取り外し可能／取り外し不能、揮発性／不揮発性コンピュータ記憶媒体も含み得る。例にすぎないが、図２に、取り外し不能、不揮発性磁気媒体との間で読取りまたは書込みを行うハードディスクドライブ１４１、取り外し可能、不揮発性磁気ディスク１５２との間で読取りまたは書込みを行う磁気ディスクドライブ１５１、およびＣＤ−ＲＯＭや他の光媒体などの取り外し可能、不揮発性光ディスク１５６との間で読取りまたは書込みを行う光ディスクドライブ１５５を示す。例示的動作環境で使用され得る他の取り外し可能／取り外し不能、揮発性／不揮発性のコンピュータ記憶媒体には、それだけに限らないが、磁気テープカセット、フラッシュメモリカード、ディジタル多用途ディスク、ディジタルビデオテープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭなどが含まれる。ハードディスクドライブ１４１は、通常、インターフェース１４０などの取り外し不能メモリインターフェースを介してシステムバス１２１に接続され、磁気ディスクドライブ１５１および光ディスクドライブ１５５は、通常、インターフェース１５０などの取り外し可能メモリインターフェースによってシステムバス１２１に接続される。
【００３４】
前述の、図２に示す各ドライブおよびそれに関連するコンピュータ記憶媒体は、コンピューティングデバイス１００のためのコンピュータ可読命令、データ構造、プログラムモジュールおよびその他のデータの記憶を提供する。図２では、例えば、ハードディスクドライブ１４１は、オペレーティングシステム１４４、アプリケーションプログラム１４５、その他のプログラムモジュール１４６、およびプログラムデータ１４７を格納するものとして示されている。これらのコンポーネントは、オペレーティングシステム１３４、アプリケーションプログラム１３５、その他のプログラムモジュール１３６、およびプログラムデータ１３７と同じでも、異なっていてもよいことに留意されたい。オペレーティングシステム１４４、アプリケーションプログラム１４５、その他のプログラムモジュール１４６、およびプログラムデータ１４７には、少なくともそれらが異なるコピーであることを示すために、図では異なる番号を付してある。ユーザは、キーボード１６２や、一般にマウス、トラックボール、タッチパッドなどと呼ばれるポインティングデバイス１６１といった入力装置を介してコンピューティングデバイス１００にコマンドおよび情報を入力することができる。他の入力装置（図示せず）には、マイクロホン、ジョイスティック、ゲームパッド、衛星パラボラアンテナ、スキャナなどが含まれ得る。上記その他の入力装置は、しばしば、システムバスに結合されたユーザ入力インターフェース１６０を介して処理装置１２０に接続されるが、パラレルポート、ゲームポート、ユニバーサルシリアルバス（ＵＳＢ）といった他のインターフェースおよびバス構造によっても接続され得る。モニタ１９１または他の種類の表示装置も、ビデオインターフェース１９０などのインターフェースを介してシステムバス１２１に接続される。モニタ１９１以外に、コンピュータは、スピーカ１９７やプリンタ１９６など他の周辺出力装置を含むこともでき、それらは、出力周辺インターフェース１９５を介して接続され得る。
【００３５】
コンピューティングデバイス１００は、１つまたは複数のリモートコンピュータへの論理接続を使用した、図１に示すようなネットワークで接続された環境で動作し得る。図２に、リモートコンピューティングデバイス１８０への汎用ネットワーク接続１７１を示す。汎用ネットワーク接続１７１、および図１に示すネットワーク接続は、ローカルエリアネットワーク（ＬＡＮ）、広域ネットワーク（ＷＡＮ）、無線ネットワーク、イーサネット（登録商標）プロトコルやトークンリングプロトコルに準拠したネットワーク、インターネットやワールドワイドウェブを含むその他の論理的、物理的、または無線ネットワークを含む、多種多様なネットワークおよびネットワーク接続のいずれとすることもできる。
【００３６】
ネットワーク環境で使用されるとき、コンピューティングデバイス１００は、有線または無線ネットワークインターフェースカード、モデム、または類似のネットワーク装置とすることのできる、ネットワークインターフェースまたはアダプタ１７０を介して汎用ネットワーク接続１７１に接続される。ネットワークで接続された環境では、コンピューティングデバイス１００に関連して示すプログラムモジュール、またはその一部は、リモートメモリ記憶装置にも格納され得る。図示のネットワーク接続は例示的なものであり、コンピュータ間でリンクを確立する他の手段も使用され得ることが理解されるであろう。
【００３７】
以下の説明では、特に指示しない限り、本発明を、１つまたは複数のコンピューティングデバイスによって実行される動作および操作の記号表現を参照して説明する。したがって、そのような動作および操作は、時々、コンピュータで実行されると言及されることがあり、構造化された形でデータを表す電気信号の、コンピューティングデバイスの処理装置による操作を含むことが理解されるであろう。この操作は、データを変換し、またはデータをコンピューティングデバイスのメモリシステム中の場所に維持し、それが当分野の技術者によく理解されているやり方でコンピューティングデバイスの動作を再構成し、または別の方法で変更する。データが維持されるデータ構造は、そのデータの形式によって定義される特定の属性を有するメモリの物理的場所である。しかしながら、本発明を前述の状況で説明するが、限定的であることは意図されておらず、当分野の技術者であれば、以下で説明する動作および操作がハードウェアとしても実施され得ることを理解するであろう。
【００３８】
概要
本発明によれば、分散コンピューティングシステムは、障害許容型アルゴリズムを実施しながら、そのシステムにデバイスを追加させ、そこから除去させることができる。パクソスアルゴリズムは、以下でより詳細に説明するように、ある一定数の障害を、その数の２倍を上回る数のコンピューティングデバイスが使用されるという条件で許容することのできる分散コンピューティングシステムを実施する機構を提供することができる。数学的には、変数「Ｆ」が許容され得る障害の数を表す場合、少なくとも２Ｆ＋１個のコンピューティングデバイスの分散コンピューティングシステムは、状態マシンの同一のレプリカを実行しようとすることによって、パクソスアルゴリズムを実施することができる。これら２Ｆ＋１個のコンピューティングデバイスのうち、それらの少なくとも過半数の任意の集合体、言い換えると、少なくともＦ＋１個のデバイスの任意の集合体は、定足数とすることができ、障害を許容する方式で提案を選択することができる。
【００３９】
どのコンピューティングデバイスにも障害が発生しない場合、２Ｆ＋１個のコンピューティングデバイスの集合体は、パクソスアルゴリズムに従って状態マシンを実施することができる。それらのコンピューティングデバイスの１つまたは複数に障害が発生した場合、残りＦ個のコンピューティングデバイスの１つまたは複数を使い、システムがパクソスアルゴリズムを使って障害許容型として動作し続けることを可能とすることができる。しかしながら、あるコンピューティングデバイスに永続的な障害が発生した場合には、それを２Ｆ＋１個のコンピューティングデバイスの集合体から除去し、または２Ｆ＋１個のコンピューティングデバイスの集合体に新しいコンピューティングデバイスを追加することが望ましいと考えられる。
【００４０】
本発明によって企図される一実施形態によれば、初期のコンピューティングデバイスの集合を使って、障害許容型分散コンピューティングシステムが提供される。それらのコンピューティングデバイスの１つまたは複数に障害が発生すると、そのデバイスは、初期集合から除去され、新しいコンピューティングデバイスがその集合に追加され得る。その結果として、この障害許容型システムの動作は、この障害許容型分散コンピューティングシステムがその上で動作するコンピューティングデバイスの集合を変更することができる。
【００４１】
状態マシン
図１に示す分散システム１０などの分散環境では、非同期的に動作するデバイス間の調整は困難なタスクとなり得る。これらの困難に対処する１つの機構は、ある機能の実行がその状態マシンをある状態から別の状態に動かす状態マシンの観点で分散コンピューティングシステムモデル化することである。状態マシンは、１組の状態、１組のコマンド、１組の応答、および１つの応答／状態対を各コマンド／状態対にリンクさせる機能を参照して説明され得る。状態マシンのクライアントは、その状態マシンが機能を実行するよう要求するコマンドを発行することができる。次いで、この機能は、状態マシンの状態を変更し、応答を生成することができる。
【００４２】
分散コンピューティングシステムを構成する個々のデバイスは、それぞれ、そのシステムの状態マシンを実行することができる。したがって、これらのデバイスは、初期状態を決定し、次いでその後、同じ順序で同じ機能を実行することによって調整され得る。デバイスは、単に、そのデバイスが実行した最後の機能を決定し、他のデバイスによって実行された機能の順序付きリストでその機能を探し出し、次いで、そのデバイスに、そのデバイスがまだ実行していないその順序付きリストからの機能を実行するよう指示することによって同期され得る。そのような状態マシンの手法は開示されている（非特許文献１参照）。その内容全体を、参照により本明細書に組み込むものとする。
【００４３】
パクソスアルゴリズム
状態マシンの手法を用いて、実行される機能およびそれらを実行する順序に合意することによって、図１に示す分散コンピューティングシステム１０の構成デバイス１１から１５の同期が達成され得る。実行される機能に合意する一方法は、パクソスアルゴリズムと呼ばれる。パクソスアルゴリズムは、デバイスが事前の警告なしに動作を停止し得る障害に直面してもシステム１０が適正に動作することを可能にする。パクソスアルゴリズムは、システムが全体として機能を実行する前に、少なくとも定足数のデバイスがその機能に合意することを必要とする。パクソスアルゴリズムを用いる場合、定足数は単純な過半数とすることもでき、システムの特定の要件に応じて、それを上回るデバイスを含むこともできる。しかしながら、定足数は、任意の２つの定足数が少なくとも１つ共通のデバイスを持つよう十分に大きくし得ると定義される。パクソスアルゴリズムの詳細な説明は開示されている（非特許文献２、非特許文献３参照）。それらのどんな部分も除外せず、それらが教示するすべてについて、その全体を、参照により本明細書に組み込むものとする。
【００４４】
次に、本発明の実施形態で使用されるパクソスアルゴリズムを説明するに際して、明確にするために、いくつかの新規の、または代替の用語および概念を提示する。図３を参照すると、４つのデバイス３０１〜３０４が示されている。デバイス３０１〜３０３のそれぞれは、共通の状態マシンのレプリカ３０５を実行し、共に「レプリカセット」を形成している。デバイス３０４はそのレプリカセットには含まれない。各レプリカ３０５は、同意モジュール３０６（ＡＭ）および実行モジュール３０７（ＥＭ）という２つの論理モジュールを実行している。以下で説明するように、ＡＭは、相互に連係して、状態マシンにおける各スロット（または「ステップ」）ごとに１つの操作を選択する。その場合、スロット「ｎ」とは、各状態マシンレプリカが実行すべきｎ番目の操作のための論理コンテナである。例えば、スロット３１０は実行される操作「ｆ」を含み、スロット３１１は操作「ｔ」を含むなどである。ＥＭ３０７は、連結されたＡＭ３０６から操作選択のことを知る。
【００４５】
パクソスアルゴリズムは、１つのレプリカを「リーダ」とし、スロットに選択され得る操作をそのリーダだけに提案させることによって、どの２つのＡＭも絶対に同じスロットに異なる操作を選択しないようにする。しかしながら、リーダに障害が発生することもあり、そのため、好ましくは、新しいリーダを選択するプロトコルがある。この選択プロトコルを介して、新しいリーダは、競合する選択を行わないように以前のリーダのアクションについて十分な知識を得る。
【００４６】
リーダの「任期」を「ビュー」といい、各ビューは、標準的パクソス記述で使用される「提案番号」に相当するビュー識別子（ＩＤ）によって一意に識別される。すなわち、各個別ビューごとに、単一のリーダが、そのビューの間に状態マシンによって実行されるすべての操作を提案する。各レプリカは、その現在のビューを追跡し、そのビューのリーダからだけ操作提案を受け入れる。ビューＩＤは、ビューコンテナおよび開始レプリカ識別子からなる。ゆえに、複数のレプリカが同時にビューを開始する場合、それらは異なるビューを開始することになる。図３の例では、コンピューティングデバイスＣ３０３が、表示されているビューのリーダであり、デバイスＢ３０２がこのビューを開始しており、ビューＩＤは８番である。
【００４７】
リーダは、それがその操作を提案した最後のスロットを記憶している。クライアントがリーダに新しい要求を送ると、リーダは、すべてのレプリカにＰＲＯＰＯＳＥＤメッセージを送ることにより、この要求を、最後のスロットの次のスロットでの操作とするよう提案する。レプリカは、その現在のビューのリーダからＰＲＯＰＯＳＥＤメッセージを受け取ると、それをローカルログに記録することによって準備する。次いで、レプリカはリーダにＰＲＥＰＡＲＥＤメッセージを送る。リーダは、定足数（一般にそれ自体を含む）からＰＲＥＰＡＲＥＤメッセージを受け取ると、その操作を選択し、すべてのレプリカにＣＨＯＳＥＮメッセージを送る。言い換えると、リーダは、競合する操作が決して選択されず、どんなＥＭもその操作を実行できることを約束する。
【００４８】
リーダが操作を提案した後、その操作が実行される前にネットワークおよび処理遅延がある。この時間の間、リーダは、さらなる操作を提案して、パイプライン方式によってプロセスの複数の段階の作業をオーバーラップさせることができる。
【００４９】
本発明の実施形態では、各状態マシンは、安定した記憶上でその状態を定期的にコピーし、そのため、このアルゴリズムは、レプリカのログが無限に増大するのを防ぐことができる。そのようなコピーを「チェックポイント」といい、チェックポイントのスロットは、そのコピーが行われる前に実行された最後の操作のスロットであると定義される。あるレプリカの最後のディスク上のチェックポイントのスロットをその「ローカル安定ポイント」という。
【００５０】
定期的なメッセージを介して、リーダは、レプリカのローカル安定ポイントを追跡し、レプリカに、ｑ番目に高いローカル安定ポイントである集合的な安定ポイントを知らせ続ける。その場合、ｑは定足数のサイズ（例えばＦ＋１）である。この値の意味は、最終的には定足数のレプリカが機能することになるため、必ず最終的には、最初のｃ個の操作を反映する利用可能なチェックポイントがあるはずであるということである。その場合、ｃは集合的安定ポイントである。いくつかのレプリカは、集合的安定ポイント以下のスロットでのすべての操作の結果を反映する状態を供給し得ることになるため、これらのスロットでの操作選択は記憶される必要がない。ゆえに、本発明の一実施形態では、レプリカは、「ログ切り捨て」というプロセスで、これらのスロットでのＰＲＥＰＡＲＥエントリを廃棄し、それらのログが無限に増大するのを防ぐ。任意のレプリカのログが固定の、または可変の最大ログサイズを超過するのを防ぐために、リーダは、集合的安定ポイントがスロットの最大ログサイズ内になるまで、そのスロットに操作を提案しない。
【００５１】
新しいリーダが選択され、それが、競合する操作を提案しないように以前のビューに関して十分な知識を得るためのプロセスを「ビュー変更」という。概要としては、任意のレプリカが、この概要の範囲外の手段によって、リーダに障害が発生した可能性があることを知った場合、それはビュー変更を開始することができるということである。そのレプリカは、その現在のビューＩＤより大きい新しいビューＩＤを選択し、すべてのレプリカにＶＩＥＷ−ＣＨＡＮＧＥメッセージを送る。ＶＩＥＷ−ＣＨＡＮＧＥメッセージを受け取ったレプリカは、それがすでにより大きい番号のビューにあるのでない限り、この新しいビューに入る。そのレプリカは、そのログに準備エントリを記述するＶＣ−ＲＥＰＬＹメッセージで開始元に応答する。ビュー変更開始元は、定足数からＶＣ−ＲＥＰＬＹメッセージを受け取ると、その新しいビューのリーダを選択し、それにこれらのメッセージを供給する。新しいリーダは、これらのメッセージを使って、それが競合する提案を行わないように以前のビューに関して十分な知識を得る。ビュー変更プロセスについては先のＬａｍｐｏｒｔの引用文献により詳細に記載されている。図３の例では、デバイスＢ３０２がビュー番号８のビュー変更を開始している。
【００５２】
本発明の実施形態では、定期的メッセージを介して、リーダが各レプリカに、いくつの連続した操作が選択されているか知らせる。ゆえに、あるＡＭは、そのＥＭによって必要とされる次の操作が選択されているという知らせを受け取ることができる。しかしながら、そのＡＭは、おそらく、リーダがその操作でのＰＲＯＰＯＳＥＤメッセージおよびＣＨＯＳＥＮメッセージを送ったときにそれがオフラインであったために、このスロットにどの操作が選択されたか知らないことがある。この場合、そのＡＭは、そのピアＡＭに、それらのいずれかが、その最近選択された操作のキャッシュにこの操作を持っているかどうか尋ねる。ＡＭは、そのログからの操作を含む、最近選択された操作のキャッシュを保持するが、さらに、そのログからローカルで切り捨てられた操作も含むことができる。あるＡＭがそのキャッシュにその操作を持っている場合、そのＡＭは要求側ピアＡＭにそれを提供し、その要求側ＡＭが完全な状態転送を実行することを不要にする。どのピアもこの操作を供給することができず、そのＡＭが、リーがログ切り捨てのためにその操作を廃棄したことを知っている場合、そのレプリカのＥＭは続行することができない。この時点において、そのレプリカは、より新しいレプリカから状態をフェッチする。
【００５３】
レプリカセットの変更を使用する変更されたパクソスアルゴリズム
以上からわかるように、コンピューティングデバイスのそれぞれが、使用中の共通状態マシンのレプリカをホストすることによってアルゴリズムのインスタンスに参加することが必要であるとは限らない。言い換えると、図３の例でのデバイスＤ３０４など、いくつかのデバイスは、最初は、使用される状態マシンレプリカセットのメンバでないことがある。例えば、永続的に不具合が生じており、またはその分散システムから除去されているデバイスを交換するために、そのようなデバイスをレプリカセットに追加することが求められることがある。レプリカセットを変更することによって、コンピューティングデバイスが、パクソスアルゴリズムによる考慮対象に追加され、そこから除去され得る。ゆえに、除去されたデバイスは、そこから定足数が取られる２Ｆ＋１個のデバイスに数えられない。本発明の実施形態は、レプリカセットへのコンピューティングデバイス（より正確には、その状態マシン）の追加およびそこからの除去を容易にする。
【００５４】
レプリカセットを変更する手法の一般的説明を以下に示す。状態マシンは、その状態の一部として、そのサービスを担うレプリカセットを含む。レプリカセットへの変更がａ操作後に効果を及ぼすようにいくつかの保留操作を保持するための一定のパイプラインの深さ「ａ」がある。言い換えると、レプリカセットがｎ番目のスロットで変更される場合、新しいレプリカセットは、スロットｎ＋ａ以上だけで操作を選択することによって、最大ａ個までの保留操作を許容する。ａは大きい方が望ましい。というのは、ａは操作パイプライン方式の深さを制限するからである。リーダは、操作ｎ＋ａを担うレプリカセットを知るまでその操作を提案することができず、それが操作ｎを実行するまでこれを知ることができない。
【００５５】
本発明の実施形態は、標準的なパクソスモデルを、各ビューをレプリカセット特有とするように、すなわち、決まったレプリカセットだけを参照するように変更する。このように、レプリカセットは相互に干渉し合わず、ビューは、それらが決まったレプリカセットを参照するためにより扱いやすい。ビューがレプリカセット特有であることを保証するために、本発明の実施形態は、ビューＩＤ記述を、以下で説明する「エポック」値を含むように拡張する。各デバイスは、それが現在そこでのアクティブなメンバである各レプリカセットごとに、エポックによってラベル付けされた別個の同意モジュール（ＡＭ）を実行する。あるデバイスが複数のレプリカセットに含まれる場合、その複数のＡＭは、それぞれ、それ自体のエポックで、したがって、それ自体のビューで独立に同時に動作する。
【００５６】
拡張されたビューＩＤの一例を図４ａを参照して示す。レプリカセット４３０は、コンピューティングデバイスＡ４０１、Ｂ４０２およびＣ４０３からのレプリカ４０５を備えるものと示されている。図３の例と同様に、このビューは、コンピューティングデバイスＢ４０２が開始したものであり、デバイスＣ４０３をそのリーダとして持ち、ビューＩＤ番号８を有する。しかしながら、レプリカセットのエポック値を示す別のフィールドが、そのビューの各デバイスのＡＭ４０６ごとに格納される。この例では、レプリカセット４３０のエポック値は３である。
【００５７】
次に、本発明の一実施形態で使用される、レプリカセット特有のビューを持つレプリカセット変更の使用の一例について図４ａおよび４ｂを参照して説明する。レプリカセットは、連続して作成され、Ｒiとラベル付けされる。その場合、指数ｉはそのレプリカセットのエポックであり、Ｒ0はその初期のレプリカセットである。所与のレプリカセットについて、そのセット中の各マシンは対応するＡＭを持つ。図４ａでは、レプリカセット中の各マシンは、それがレプリカセットＲ3４３０のメンバであることに対応するＡＭを持つ。これらのＡＭのそれぞれはエポック３を持つ。図４ａのＡＭ４０６のそれぞれは、ビュー＜エポック→３，ビュー→０，開始元→ｎｉｌ＞で開始したものである。時間が進むにつれて、ビュー変更が発生し、このビューＩＤが進む。例えば、最初のビュー変更がレプリカＣによって開始された場合、新しいビューＩＤは＜３，１，Ｃ＞になる。図４ａでは、いくつかのビュー変更が発生しており、そのため、ビューＩＤは＜３，８，Ｂ＞である。あるＥＭが新しいレプリカセット、図４ｂのＲ4４４０を作成する操作を実行するとき、そのＥＭは、その新しいレプリカセットのメンバに、それぞれ、適当なエポックを持つＡＭを開始するように通知する。あるマシンがＲ3４３０とＲ4４４０両方にある場合、これは、そのマシンに、２つの独立のＡＭ４０６および４４１を実行させることになる。新しいＡＭはビュー＜４，０，ｎｉｌ＞で開始する。このビューＩＤは、Ｒ3がどのビューＩＤにあるかには無関係であり、そのビューとは独立に進む。レプリカセットＲ4４４０のＡＭは、リーダとして、レプリカセットＲ4４４０中のあるＡＭを選択する。このリーダは、レプリカセットＲ3４３０のリーダと同じマシン上にある必要はない。図４ｂでは、ビュー変更がＡＭ４４０をビュー＜４，１，Ａ＞まで進めている。
【００５８】
決まったレプリカセットを参照することにより、本発明の実施形態ではビューが扱いやすい。例えば、ビュー変更には、明確に定義された参加者の集合、すなわちそのレプリカセット中のすべてのＡＭが関与する。これらは、ビュー変更開始元がＶＩＥＷ−ＣＨＡＮＧＥメッセージを送る宛先のＡＭであり、これらの過半数からのＶＣ−ＲＥＰＬＹメッセージが、次のリーダが先に進むのに十分な定足数の応答を構成する。さらに、ＡＭがいつビュー変更開始の責任を負うか、およびそれがリーダになるのに適するのはいつかがはっきりしている。すなわち、それはそれらの責任と一緒に作成され、それが破棄されるまでそれらの責任を負う。また、リーダは、どのＡＭと定期的メッセージを交換する必要があるか正確に知っている。
【００５９】
図５に注目すると、レプリカセット特有のビューを円滑化するために、同じマシン上の異なるレプリカのＡＭは、それぞれ、そのマシン上の単一のＥＭとやりとりして、選択された操作を与える。このＥＭは、変更されないパクソスアルゴリズムと同様に、スロットの順に選択された操作を実行する。各操作は、単一の明確なＡＭからもたらされる。というのは、どの２つのＡＭも絶対に同じスロットの責任を負わないからである。図５では、スロット５００は、レプリカセットＲ4を作成した操作を含むスロットであり、スロット５１５は、レプリカセットＲ5を作成した操作を含むスロットである。その固定されたパイプライン深さはａ＝１０である。そのため、レプリカセットＲ4は、スロット５１０（ｒ4＝レプリカセット作成スロット５００＋ａ）からスロット５２４（ｒ5−１）までの操作を選択する責任を負う。レプリカセットはそれが責任を負わない操作を選択しない。というのは、リーダは、それが責任を負わない操作を提案しないからである。リーダは、その連結されたＥＭが操作ｎ−ａを実行し、この実行結果が、そのリーダのレプリカセットがスロットｎに責任を負うと指定するまで、操作ｎを提案しない。したがって、ＥＭがレプリカセットＲmを作成し、そのセットにスロットｒm以降の責任を負わせる操作を実行する場合、レプリカセットＲm-1以前のＡＭは、スロットｒm以上での提案を行わなくなる。
【００６０】
レプリカセット特有のビューをさらに円滑化するために、本発明の実施形態は、リーダが新しいレプリカセットが選択されていることを知った場合、リーダにその提案パイプラインを空にさせる。そのようなリーダを「レームダック」リーダという。提案パイプラインを空にすることは、以下のようなシナリオにおいて有用である。レプリカセットＲm-1のリーダは、それが責任を負う最後の操作ｒm−１を提案し、クライアントを新しいレプリカセットに宛先変更し始める。次いで、そのリーダはクラッシュし、その後のビュー変更はその古いリーダの最近の提案すべてを失い、そのため、新しいリーダが提案を行った最後のスロットはｒm−１未満である。すべてのアクティブクライアントは新しいレプリカセットに宛先変更されているため、それらは、古いレプリカセットの新しいプライマリに要求を提出せず、操作ｒm−１には操作が提案されない。これは、状態マシンが前進しないことを意味する。というのは、スロットｒm以上での操作だけしか選択され得ず、それらは、操作ｒm−１が実行するまで実行され得ないからである。このシナリオを回避するために、本発明の実施形態では以下が企図される。リーダが、操作ｒmで別のレプリカセットが引き継ぐことになっているが、それがそこでの操作を提案した最後のスロットはｒm−１未満であることを知ると、リーダは、最後に提案したスロットとｒmの間の各スロットごとにヌル操作を提案する。これは、せいぜい、ａ−１ヌル操作を必要とするにすぎない。というのは、最後に提案されたスロットは、少なくとも、そのマシンが実行した操作の数であり、それはｒm−ａを下回らないからである。このパイプラインを空にするプロセスは、状態マシンの実行が最終的にスロットｒmに至ることを保証する。
【００６１】
レプリカセット特有のビューをさらに円滑化するために、本発明の実施形態は、古い、不要なＡＭを廃棄する。Ｒmの集合的安定ポイントが少なくともｒm−１になると、Ｒmが「設定」される。すなわち、そのメンバの定足数が開始し、集合的安定ポイントの定義により、最終的には、それらの１つがチェックポイントに、少なくともスロットｒm−１を提供できるようになる。これは、ｒm未満の操作、すなわち以前のレプリカセット（すなわち、Ｒ０、Ｒ１、・・・、Ｒm-1）が選択する責任を負うすべての操作に関するどんな情報も不要にする。ゆえに、Ｒmが設定されると、すべての以前のレプリカセットは「失効した」、すなわちもはや不要であるとみなされる。それが失効したＡＭを有することを知っている任意のマシンは、その失効したＡＭを、それらのログを含めて破棄することができる。マシンがその唯一の実行中のＡＭを破棄する場合、それは、そのＥＭも破棄することができる。すなわち、それはもはやそのサービスでのアクティブな参加者ではなくなる。
【００６２】
レプリカセット特有のビューをさらに円滑化するために、本発明の実施形態では、マシンは、破棄されたＡＭでのほんのわずかな量の不揮発性状態、すなわち、破棄されたＡＭの間で最高のエポック（「ＭａｘＤｅｆｕｎｃｔ」）、およびそれを引き継ぐエポックに対応するレプリカセット（ＲMaxDefunct+1）を保持する。そのマシンはこれらを、破棄されたＡＭとの通信を開始しようとする任意のクライアントまたはリモートＡＭに供給する。破棄されたＡＭに関する知らせを受け取ったクライアントは、後継のレプリカセットとの通信を開始し、失効したピアの知らせを受け取ったＡＭは、それ自体を破棄することを知る。
【００６３】
本発明の実施形態は、あるレプリカセットのＡＭがその後継レプリカセットが設定されることを保証し、それらのＡＭが、最終的に、それらが破棄され得るようにこの設定のことを知る機構を提供する。レプリカセットＲm-1の１つのＡＭが、そのＥＭが操作ｒm−１、すなわち、このＡＭのレプリカセットが責任を負う最後の操作を実行していることを知ると、それは、新しいレプリカセット中の各ＡＭに、定期的にＩＳ−ＳＵＣＣＥＳＳＯＲ−ＵＰ−ＴＯ−ＤＡＴＥメッセージを送るスレッドを作成する。そのようなメッセージは、その受信側のローカル安定ポイントが少なくともｒm−１であるかどうか尋ね、そうでない場合、それにそのスロット以後のチェックポイントを供給するよう提案する。このＡＭは、すでに肯定的に応答しているＡＭにはそのようなメッセージを送らない。最終的に、このＡＭは定足数の新しいレプリカセットから肯定応答を受け取り、それによって、Ｒmが設定されたことを知る。この時点において、このＡＭは、これが失効したことを知り、これ自体を破棄する。
【００６４】
Ｒm-1中のあらゆるＡＭがＩＳ−ＳＵＣＣＥＳＳＯＲ−ＵＰ−ＴＯ−ＤＡＴＥメッセージを送るため、最終的には、それらの１つがＲmを設定する。ＩＳ−ＳＵＣＣＥＳＳＯＲ−ＵＰ−ＴＯ−ＤＡＴＥメッセージを送る責任は、Ｒm-1のリーダだけに割り当てることもできる。代替として、ＩＳ−ＳＵＣＣＥＳＳＯＲ−ＵＰ−ＴＯ−ＤＡＴＥメッセージを送る責任は、Ｒm-1のリーダだけではなく、すべてのＡＭにも割り当てられる。これは、古いレプリカセットのリーダのＥＭが後ろにある場合には、新しいレプリカがその初期のチェックポイントをより早く獲得することを可能にする。また、これは、負担全部をリーダに負わせるのではなく、古いレプリカセットのＡＭの間でチェックポイントを提供する負荷を分散させる。すべてのＡＭに責任を割り当てる別の理由は、以下で説明する、証明書チェーンを使った最適化に関するものである。
【００６５】
ＥＭは、以下のシナリオで、チェックポイントをＩＳ−ＳＵＣＣＥＳＳＯＲ−ＵＰ−ＴＯ−ＤＡＴＥメッセージで暗黙的に供給する提案を使用する。ＥＭは連結されたＡＭから次の操作を獲得する必要があるが、どの連結されたＡＭもこの操作に責任を負わないものと想定する。例えば、図６では、デバイスＣ４０３上のＥＭが、例えば、Ｒ4によって管理されるスロットからの操作を必要とする場合、そのＥＭは、そのマシンがＲ4の一部でないため、依頼するＡＭを持たない。そのような場合、そのＥＭは、それが必要とする操作を上回る最低の操作番号に責任を負うＡＭ、この例ではＲ5に対応するＡＭに依頼する。このＡＭは、それが、ＥＭが必要とする操作を供給できないことを理解し、実際、ｒ5−１に先行するどんな操作も供給することができない。そこで、このＡＭはＥＭに、そのレプリカセットが責任を負わないすべての操作の結果を含むチェックポイント、すなわち、ｒ5−１以降のチェックポイントをどこで獲得すべきか知らせる。同じエポック中のそのピアＡＭの１つがそのようなチェックポイントをローカルで持っている場合、このＡＭはＥＭに、そのピアのマシン上のＥＭと連絡をとるよう知らせる。そうではなく、このＡＭが、先行するレプリカセット中の何らかのレプリカから最近のＩＳ−ＳＵＣＣＥＳＳＯＲ−ＵＰ−ＴＯ−ＤＡＴＥメッセージを受け取っている場合、それは、そのＥＭに、そのレプリカからチェックポイントを獲得するよう指示する。
【００６６】
ＩＳ−ＳＵＣＣＥＳＳＯＲ−ＵＰ−ＴＯ−ＤＡＴＥメッセージだけが新しいＡＭを作成することができる場合、それらの新しいＡＭは、ＥＭが操作ｒm−１を実行するまで開始することができないはずである。ＡＭをより早く開始させる代替の最適化として、本発明の実施形態は、ＥＭに、それが操作ｒm−ａを実行するときに、それぞれの新しいレプリカにＪＯＩＮメッセージを送信させ、それがそのセットを作成する。ＪＯＩＮメッセージを受け取ったマシンは、その新しいレプリカセットのＡＭを開始する。ＪＯＩＮメッセージは、最適化にすぎないため、肯定応答されず、再送信もされない。
【００６７】
本発明の実施形態は、後で設定されるレプリカセットに関する「後継者情報」を作成し、それを使用する。ＥＭがレプリカセットＲmを作成する操作を実行するとき、それは、レプリカセットＲm-1のローカルＡＭによって使用される後継者情報を作成する。この情報は、その後継者が責任を追う最初の操作番号、ｒm、および後継レプリカの識別情報を含む。ＡＭがｒmを必要とするのは、それがリーダになった場合、ｒm以上の番号を持つ操作を提案しないようにするためである。それが後継レプリカの識別情報を必要とするのは、それが後でＩＳ−ＳＵＣＣＥＳＳＯＲ−ＵＰ−ＴＯ−ＤＡＴＥメッセージを送ることができるようにするためである。
【００６８】
レプリカセットＲmを作成する操作ｒm−ａを実行するのではなく、ＥＭが、その操作をスキップすることができるようにする状態転送を受け取ることが可能である。ゆえに、状態フェッチを完了した後、ＥＭは、その連結されたＡＭのいずれかでの後継者情報を知っているかどうか調べ、そうである場合、それをそれらのＡＭに分配する。このために、状態は、古いレプリカセットについてでさえもｒmおよびＲmを含む。状態マシンはこの情報を無期限に保持することができる。代替として、状態マシンは、最終的にそのような情報を以下のように廃棄することもできる。リーダは、そのレプリカセットの集合的安定ポイントがスロットの最大ログサイズ内になるまでそのスロットでの操作を提案しないことを想起されたい。ゆえに、状態マシンは、ｒm−１とははるかに離れた最大ログサイズであるスロットでの操作を実行するとき、レプリカセットＲmの集合的安定ポイントは少なくともｒm−１であり、ゆえに、ｍ−１以下のエポックを持つレプリカセットは失効していると推論することができる。そのため、状態マシンは、ｍ−１以下の番号のエポックを持つレプリカセットの情報を廃棄し、失効することが分かっている最新のレプリカセットの番号だけを記憶していればよい。ゆえに、状態マシンは、いくつかのＡＭに後継者情報を供給することができないことがあるが、それらのＡＭについては、ＥＭが、それらにそれら自体を破棄するように知らせることができる。
【００６９】
本発明の実施形態は、「証明書チェーン」を使って、あるレプリカセット中のデバイスが正当であることを示す。それが新しいレプリカセットの一部であるというメッセージを受け取ったマシンは、その送信側が嘘をついていないことを検証する必要があることがある。通常、信頼は、フェイルストップ合意での問題ではない。しかしながら、レプリカセットが変更されるとき、そのようなメッセージを交換するマシンは、まだ、同じフェイルストップ合意グループ中にはない。初期のレプリカセット中のマシンは、それが、サービス証明書、すなわち、その初期のレプリカセットを指定する信頼される認証局（ＣＡ）によって署名された証明書を介してそこに属することを知っている。ＣＡは、レプリカセットが変更される間にオフラインであることもあるため、本発明の実施形態は、レプリカを使って新しいレプリカセットを証明する。
【００７０】
証明書チェーンは、証明書のシーケンスである。各証明書がある特定のレプリカセットを証明する。チェーン中の最初の証明書はサービス証明書であり、初期のレプリカセットＲ0を証明する。各証明書は、その先行するレプリカセットのメンバによって署名される。図７を参照すると、証明書チェーンの一例７００が示されている。認証局（信頼される第三者など）が、レプリカセットＲ0がデバイスＡ、Ｂ、Ｃからなるという証明書７１０を発行する。レプリカセットＲ0のメンバであるデバイスＡは、証明書７１１で、レプリカセットＲ1がデバイスＡ、Ｂ、Ｄからなることを証明する。デバイスＤは、レプリカセットＲ2がデバイスＡ、Ｄ、Ｅからなることを証明する証明書７１２を発行する。
【００７１】
マシンは、それが特定のレプリカセットにあることを示す証明書チェーンを受け取った場合、これがそうであることを確認することができる。新しいＡＭは、これをその起点チェーンとして保存する。Ｒ0中のＡＭでは、そのサービス証明書自体が起点チェーンである。あるＡＭが、その後継者レプリカセットのメンバにＡＭを作成するよう知らせる必要があるとき、それは、その新しいレプリカセットを記述する証明書に署名し、それをその起点チェーンに添付し、これを新しいＡＭの起点チェーンとして送る。
【００７２】
本発明の実施形態は、２つの任意選択の最適化を使って起点チェーンが短く保たれるようにする。第１に、１つのレプリカセットが何らかの証明書によって証明され、そのレプリカセットがそのチェーン中の何らかの後続の証明書の署名者を含む場合、その２つの間のチェーン中のすべての中間証明書が除去され得る。第２に、ＡＭは、それが別の前任者からより短いチェーンを受け取った場合、その起点チェーンを交換することができる。例えば、再度図７を参照すると、ＥがＤからチェーン７００を受け取り、後でＡが、Ａがその最新の証明書７１２に署名したことを除いてチェーン７００と同一のチェーンをＥに送った場合、Ｅは、不要な中間証明書７１１を除去してより短いチェーン７２０を生成し、次いで、その起点チェーン７００をこのより短いチェーン７２０で置き換えることができる。前任者からより短い証明書チェーンを受け取る機会が可能であるのは、前述のように、リーダだけでなく、レプリカセット中のあらゆるＡＭがＩＳ−ＳＵＣＣＥＳＳＯＲ−ＵＰ−ＴＯ−ＤＡＴＥメッセージを送るからである。
【００７３】
本発明の実施形態は、状態マシンがレプリカセットを変更するためのインターフェースを提供する。状態マシンは、操作を実行する間、ｃｈａｎｇｅ＿ｒｅｐｌｉｃａｓ（）関数を呼び出し、新しいレプリカセットに含まれるマシンの配列を指定することができる。
【００７４】
本発明の実施形態は、ポリシーを使って、いつレプリカセットを変更すべきか決定する。いくつかの実施形態では、管理者は、クライアントに、レプリカセット変更要求を提出するよう指示することによって明示的にレプリカセットを管理する。状態マシンは、管理権限の証拠がない要求を無視する。管理者は、例えば、明示的要求を使って、マシンを永続的に廃棄し、あるいは耐障害性を増大させるために新しいマシンを配備することができる。
【００７５】
いくつかの実施形態では、持続的なマシン障害に対処するため、管理者を必要とせずに、レプリカセット変更が自動的に実行される。各ＥＭは、一定の間隔で、例えば、５分ごとにサービスに特別なクライアント要求を送信し、それ自体が活動状態にあることを報告する。状態マシンは、各ＥＭが、それ自体が活動状態にあることを報告した最後の時刻からなる特別な状態を追跡する。この状態は、各レプリカ上のローカルクロックによってではなく、完全に操作によって決定され、そのため、各操作は、リーダによって割り当てられたタイムスタンプを含み、各操作は、ある一定の「時刻」に実行するといわれる。所与の時刻に操作を実行することに関するさらなる詳細が開示されている（非特許文献４）。そのどんな部分も除外せず、それが教示するすべてについて、その全体を、参照により本明細書に組み込むものとする。所与の間隔で、例えば１時間ごとに、状態マシンは、レプリカ間で最も古い最後の活動状態の時刻が１時間より前であるかどうかチェックする。そうである場合、状態マシンは、対応するデバイスに持続的な障害が発生していると想定し、ｃｈａｎｇｅ＿ｒｅｐｌｉｃａｓ（）関数を呼び出してそれをそのレプリカセットにおいて交換する。
【００７６】
また、状態マシンは、代用となる新しいデバイスを決定論的に選択する。レプリカになろうとするデバイスは、定期的に、特別なクライアント要求をサービスに送る。そのような要求は、送信者にフェイルストップサービスに参加する権限を与える認められた機関からの証明書を含む。その状態は、可能なレプリカから、それらのマシンが最後にそのような要求を行ったときのタイムスタンプへのマッピングを含む。新しいマシンを選択するために、状態マシンは、そのタイムスタンプが十分に新しいマシンの間で、擬似ランダムであるが、決定論的な選択を行う。
【００７７】
本発明の原理が適用され得る多くの可能な実施形態を考慮すれば、本明細書で図面に関連して説明した実施形態は例示のためのものにすぎず、本発明の範囲を限定するものであると解釈すべきでないことが理解されるはずである。例えば、ソフトウェアとして示した例示の実施形態のいくつかの要素は、ハードウェアとしても実施することができ、その逆もまた同様であること、あるいは例示の実施形態は、本発明の精神を逸脱することなく、その構成および詳細を変更することができることを、当分野の技術者は理解するであろう。したがって、本明細書で説明した本発明では、そのようなすべての実施形態が添付の特許請求の範囲およびその均等物の範囲内に含まれ得ることが企図されている。
【図面の簡単な説明】
【００７８】
【図１】本発明の一実施形態が実施され得る分散コンピューティングシステムの一例を一般的に示す構成図である。
【図２】本発明の一実施形態が実施され得るコンピューティングデバイスの一例を一般的に示す構成図である。
【図３】本発明の一実施形態が実施され得る複製された状態マシンのセットの一例を一般的に示す構成図である。
【図４ａ】本発明の一実施形態が実施され得る複製された状態マシンのセットの一例を一般的に示す構成図である。
【図４ｂ】本発明の一実施形態が実施され得る複製された状態マシンのセットの一例を一般的に示す構成図である。
【図５】本発明の一実施形態による、複製された状態マシンの動作スロットセットの一例を一般的に示す構成図である。
【図６】本発明の一実施形態が実施され得る複製された状態マシンのセットの一例を示す構成図である。
【図７】本発明の一実施形態による、レプリカセット証明書チェーンの一例を一般的に示す構成図である。
【符号の説明】
【００７９】
１００  コンピューティングデバイス
１２０  処理装置
１２１  システムバス
１３０  システムメモリ
１３４、１４４  オペレーティングシステム
１３５、１４５  アプリケーションプログラム
１３６、１４６  他のプログラムモジュール
１３７、１４７  プログラムデータ
１４０  取り外し不能不揮発性メモリインターフェース
１５０  取り外し可能不揮発性メモリインターフェース
１６０  ユーザ入力インターフェース
１６１  マウス
１６２  キーボード
１７０  ネットワークインターフェース
１７１  汎用ネットワーク接続
１８０  リモートコンピューティングデバイス
１９０  ビデオインターフェース
１９５  出力周辺インターフェース
１９６  プリンタ
１９７  スピーカ
【図１】
2006004434.tif 000003
【図２】
2006004434.tif 000004
【図３】
2006004434.tif 000005
【図４ａ】
2006004434.tif 000006
【図４ｂ】
2006004434.tif 000007
【図５】
2006004434.tif 000008
【図６】
2006004434.tif 000009
【図７】
2006004434.tif 000010
【外国語明細書】
2006004434000001.pdf