(57)【要約】いつでもシードノードからの位置のリングの形成を確実にするシステムと方法。ブートストラップ段階は、ノードのライフサイクルに含まれるが、ネットワークにおける分割脳の状態の反対の影響を軽減するためである。そのようなブートラップ段階の間に、既存のリングが発見された場合、シードノードは、ノンシードノードがするのと同様の方法で、既存のリングと結合できる。リングが検出されない場合は、ブートストラップ段階は、シードノードを「スーパーシードノード」として選択することを試みるが、そこでは、リングは、その後最初のノードとして、そのような新しいスーパーシードノードに形成されることができる。
2012507076.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータにより実行される方法であって、
コンピュータ可読媒体に記録されたコンピュータが実行可能な命令を実行するためのプロセッサを利用して、
フェデレーションリングに関連付けられたシードノードの定足数によるスーパーシードノードを選択することであって、前記スーパーシードノードは、新しいリングを形成する権利を有していることと、
シードノードのライフサイクル中にブートストラップ段階を引き起こして、いつでもスーパーシードノードにより正確にノードのセットに関連付けられた１のリングが形成できることを確実にすることと、
を実行することを含むこと特徴とする方法。
【請求項２】
前記ブートストラップ段階の間に１のシードノードを前記スーパーシードノードとして選択することをさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
ノードとシードノードの間で設立されたグローバルリースに基づいたノードの存在を明示することをさらに含むことを特徴とする請求項１に記載の方法。
【請求項４】
定足数内のすべてのシードノードの期間が満了した後スーパーシードノードにより新しいリングを設立することをさらに含むことを特徴とする請求項３に記載の方法。
【請求項５】
シードノードについてのＴＴＬ（有効期限）を指定することをさらに含むことを特徴とする請求項３に記載の方法。
【請求項６】
前記ノードに割り当てられたチケットのタイプに基づいたノードのための行動のタイプを指定することをさらに含むことを特徴とする請求項２に記載の方法。
【請求項７】
前記ノードに関連付けられたグローバルチケットの定足数を失うことにおいてノードを終了させることをさらに含むことを特徴とする請求項３に記載の方法。
【請求項８】
前記ノードによりグローバルチケットを発行させる権利を放棄することをさらに含むことを特徴とする請求項３に記載の方法。
【請求項９】
前記ノードが終了した後に前記ノードによりフェデレーションリングを再結合することを試みることをさらに含むことを特徴とする請求項７に記載の方法。
【請求項１０】
グローバルリースのタイムアウトの最大限の持続を選択することをさらに含むことを特徴とする請求項７に記載の方法。
【請求項１１】
定足数の中のすべてのシードノードからのグローバルチケットが満了したことを確実にした後に新しいリングを形成することをさらに含むことを特徴とする請求項７に記載の方法。
【請求項１２】
他のシードノードに定期的にメッセージを送ることにより前記他のシードノードの経過を追うことをさらに含むことを特徴とする請求項７に記載の方法。
【請求項１３】
シードノードによりスーパーシードノードとしてブートストラップ段階を去ることをさらに含むことを特徴とする請求項７に記載の方法。
【請求項１４】
定足数内のすべてのシードノードの有効期間をスーパーチケットに対応する有効期間に設定することをさらに含むことを特徴とする請求項１３に記載の方法。
【請求項１５】
シードノードにおいてリースを維持するための強制力を利用することをさらに含むことを特徴とする請求項１３に記載の方法。
【請求項１６】
ノードについてのグローバルリースを更新することをさらに含むことを特徴とする請求項１３に記載の方法。
【請求項１７】
ノードについての既存のチケットを新しいチケットに交換することをさらに含むことを特徴とする請求項１３に記載の方法。
【請求項１８】
コンピュータにより実行されるシステムであって、
信頼を築かれたノードの収集を表示するフェデレーションコンポーネントと、
ノードのライフサイクルにおいてブートストラップ段階の状況を引き起して、いつでもスーパーシードノードにより正確な１の新しいリングが形成できることを確実にするリング構造コンポーネントと、
を備えることを特徴とするシステム。
【請求項１９】
前記ノードの前記ライフサイクルを指定するグローバルチケットをさらに備えることを特徴とする請求項１８に記載のシステム。
【請求項２０】
コンピュータにより実行されるシステムであって、
信頼を築かれたノードの収集を表示する手段と、
ノードのライフサイクルにおいてブートストラップ段階を開始して、いつでもスーパーシードノードにより正確な１の新しいリングが形成できることを確実にする手段と、
して機能するコンピュータにより実行されるコンポーネント、を備えることを特徴とするシステム。
【発明の詳細な説明】
【背景技術】
【０００１】
コンピュータ技術の発展（例えば、マイクロプロセッサのスピード、メモリの容量、データ転送の処理能力、ソフトウェアの機能性など）は、一般的には、様々な産業におけるコンピュータアプリケーションの増加の一因となってきた。より高性能のサーバーシステム、しばしばサーバーの配列として構成されるサーバーシステムは、通常、例えばＷＷＷ（ワールドワイドウェブ）など、外部資源から発したサービスの要求を提供される。
【０００２】
利用できる電子データの量が増大するため、使い勝手が良くすばやいデータの検索および取り出しを促進する扱いやすい方法により、そのようなデータを記録することが重要になる。今日、通常の扱い方は、電子データを一以上のデータベースに記録することである。典型的なデータベースは、例えばコンピュータプログラムがすばやく検索でき要求されたデータの一部を選択できるように構成されたデータにより、組織化された情報の収集物として照会されることができる。
【０００３】
その上、そのような環境において、フェデレーション（ｆｅｄｅｒａｔｉｏｎ）は、互いの信頼を構築し、組織又はサービスプロバイダ自体の間でのユーザーの個人情報の共有を可能にする、組織又はサービスプロバイダのグループを照会する。例えば、フェデレートされた個体は、個々が集団の境界線の間をますます高頻度の割合で移動することを認識する分散されたコンピュータの構成物である。連合アイデンティティの実際のアプリケーションは、異機種環境にあるいくつかのシステムを同時に扱うことが必要である大きな多国籍の集団により表現される。
【０００４】
一般に、フェデレーションやリングを起源とする第１のノード（例えば、スーパーシードノード）が、もともとはじめに１のリングが要求されたが何かの事情で多数のリングを作成したとき、問題はよく起こることがある。そのうえ、さらなる複雑性は、分離脳の状態、つまり、互いを識別することなしに同時に２つのリングが存在する状態において、起こることがある。この問題は、さらに、下層のコミュニケーションチャンネルが信頼性があると判断されないときに困難を生じることがあり、例えば、ネットワークにおける分離を与えることもある。加えて、伝統的なシステムは、既存のノードがないことを最初に確実にするために典型的に管理者を必要とする手動の処理を採用し、その後、シードノードに、スーパーシードノードとして作動するように明確に命令する。
【発明の概要】
【０００５】
以下は、本明細書で説明される態様の基本的な理解を提供するために簡易化した要約を示す。この概要は、この主張された主題の広範的な概要ではない。主張された主題の重要又は鍵となる要素を識別することおよびそれについての範囲を詳しく説明することを意図するものではない。この唯一の目的は、後に示されるより詳細な説明の前提として簡易化した様式でいくつかの概念を示すことである。
【０００６】
この主題の革新的な方法は区分された環境、リングインフォーメーションコンポーネントを介した環境において、シードノードの定足数のために所定の条件を施行し、正確なひとつのリングが、１のノードのセットと関連付けられて、シードノードから与えられた時間において形成されることができることを確実にする。そのようなリングインフォーメーションコンポーネントは、ノードのライフサイクルにおいて、「ブートストラップ」段階のような状況を引き起こし、分割脳の状況（例えば２つのリングが、ネットワークにおいて互いを認識することなしに形成されるとき）の不利な効果を軽減する。そのノードのセットは、所定のアプリケーションと関連付けることができ、および／又は、例えばユーザーが識別することができる。ブートストラップの段階の間、既存のリングが検出された場合、シードノードはノンシードノードがするような方法と同様の方法で既存のリングに結合することができる。一方、リングが検出されない場合は、ブートストラップ段階はシードノードを、新しいリングを形成できる「スーパーシードノード」として選択することを試みる。また、そのような新しいスーパーシードノードは新しいリングの最初のノードを表している。スーパーシードノードそれ自体は、新しいリングをスタートさせる根拠としてのシードノードを表す。
【０００７】
特定の態様にしたがって、リングインフォメーションコンポーネントは１のリングの作成および／または存在を、以下の状況を実施することによって、確実にする。すなわち、１）ブートストラップ段階の間、正確に１のシードノードがスーパーシードノードとして選択される。２）スーパーシードノードはシードノードの定足数により選択される。３）スーパーシードノードは定足数のすべてのシードノードからのグローバルチケットが終了することを確実にした後に新しいリングを形成できる。加えて、この主題の革新的な方法は、さらに、ノードと設計されたシードノードの集合との間のグローバルリースを定め、ノードはシードノードの定足数とともに、アクティブリースを有していれば存在できる。
【０００８】
関連する態様において、シードノードは、新しいリングを形成する最初のノードを選択してシードノードの間で通信できる。それに応じて、既存のリングが、それとともに関連するグローバルリースによって決まることができる。１の態様において、シードノードは、２種類のチケット、すなわちグローバルチケットとスーパーチケットを発行することができるが、これは以下の制限を有している。１）ＴＴＬ（ｔｉｍｅ  ｔｏ  ｌｉｖｅ）の要件であって、関連しているＴＴＬが存在し、所定の期間の経過後に消滅するもの。２）行動の要件であって、行動が受信側のノードおよび送信側のシードノードから保障されるもの（チケットのタイプによって行動のタイプが決定される）。３）転送の要件であって、チケットが１のノードから他のノードへ渡されることができるもの。４）回復の要件であって、どのチケットもそれが発行される前に存続されることを必要とするので、ノードの再起動を乗り越えることができる（例えば、チケットの発行は、発行するノードが明確な責任を取ることを約束していることを示し、その結果、何の約束が提供されたかを記憶しなければならない）。５）満了の指示の要件であって、チケットが受信ノードにおいて満了した後に、ノードが発行したときに満了するものである。
【０００９】
更なる実施例に従って、グローバルチケットは、受信ノードにシードノードが発行されることにより次の状態で表される。１）フェデレーションにおける固有のグローバルチケットの定足数が存在できないことが確かでない限り、シードノードは新しいリングを形成しようとしない。また、２）グローバルチケットの定足数が失われることで、ノードそれ自体が終了し、リングが再結合される。同様に、スーパーチケットは、シードノードからシードノードに、「ブートストラップ」段階の間だけ発行される。それは、新しいリングが生成されるときである。そのようなブートストラップ段階の間、ノードは、典型的にスーパーチケットが抱えているノードにグローバルチケットを発行することが可能となるだけである。それ自体は、それとともに関連するスーパーチケットの転送において、ノードはグローバルチケットを発行する権利を放棄する。
【００１０】
前述および関係する後述の達成によって、請求された主題の示されたいくつかの態様は、以下の表現と追加された図によって本明細書に表現される。これらの態様は、主題を実行する様々な方法を表示するが、その方法のすべてが、主題が請求する範囲内に限定されることを意図するものではない。他の利点および今までにない特徴は、図面との関係を考慮して、以下の詳細な説明から明らかになるであろう。
【図面の簡単な説明】
【００１１】
【図１】この主題の革新部分の態様に関連して、フェデレーションのための複数のシード／ノンシードノードをもつシステムのブロック図を示すものである。
【図２】この主題の革新部分の態様に関連して、複数のノードと関連してチケットを利用するシステムのブロック図を示すものである。
【図３】この主題の革新部分の態様に従って、ノード間のチケットの交換を示すものである。
【図４】この主題の革新部分の例示的な態様に従って、ブートストラップ段階を実行するリング構成コンポーネントを示すものである。
【図５】この主題の革新部分の態様に従って、例示的なブートストラップ段階を示すものである。
【図６】更なる態様に従って、定足数内のチケット交換の手順を示すものである。
【図７】更なる態様に従って、リング形成の手順を示すものである。
【図８】更なる態様に従って、メッセージ交換の特定の方法を示すものである。
【図９】この主題の革新部分と関連して、利用可能なコンポーネントの回復を示すものである。
【図１０】この主題の革新部分の様々な態様を実施するための、例示的な環境を示すものである。
【図１１】この主題の革新部分の態様に従って、ノードの構成のために使用されることができる更なる例示的なコンピューティング環境の略ブロック図を示すものである。
【発明を実施するための形態】
【００１２】
この主題の革新的な部分の様々な態様は、付属の図面を参照にしてここに説明され、図において、同様の数字は完全に同様の又は対応する要素を表している。しかしながら、図と、それに加えて関連する詳細な説明は、公開された特別な形式へ主題の請求に限定されることを意図するものではないことが、理解されるであろう。むしろ、意図しているものは、主題の請求の趣旨および範囲に含まれるすべての変更したもの、同様のもの、交換したものに渡っている。
【００１３】
図１は、いつでも、正確に１のリングが、それとともに関連付けられたシードノードから形成されることができることを確実にする、リング構造のコンポーネント１１５を採用するシステム１００のブロック図を示している。一般的に、そのようなリングは、さらにダイナミックで拡張性のあるネットワークを形成するために、互いに協力するノードの１のセットからなるフェデレーションを表し、そのようなリングにおいては、情報は体系的かつ効果的に広まり配置される。
【００１４】
例えば、フェデレーションにおいて共有するノードは、反射的で、非対称で、過渡的な、全体の、ノード固有の領域を超えて定義された２項関係を使用して、分類されたリストを含むことができる。例えば、分類されたリストの端部は結合でき、その結果ノードそれ自体がリングを形成する。このようにして、ノード自体を分類されたリストの中心にあるものとして各々のノード自体が見えるようにリスト中の各々のノードを提供する。もうひとつの例として、リストは、ノードがリストをどのような方向にも横切ることができるようなものと、２重にリンクさせることができる。その上、１対１のマッピング機能をノードアイデンティティの数値の領域からノード自体へ定義することができる。そのようなマッピング機能は、マッピングがきつくないときに数値の領域内のノードの点在からなる。
【００１５】
もうひとつの例において、フェデレーションにおいて共有するすべてのノードは、０から適切に選択された上限までの自然数を割り当てられ、そのような範囲は、例えば、ノードに割り当てられた番号に空白が存在することができるような、連続する必要のないものも含まれている。そのようなノードに割り当てられた番号は、さらに、リングにおけるそれ自身のアイデンティティとして作動する。その上、マッピング機能は、２つのノードアイデンティティの間に置かれている番号を、数値的に番号が最も近いアイデンティティを有するノードへマッピングすることにより、スペースの数の空白からなる。それに応じて、各ノードに分配された番号を均一に与えることにより、リングのセグメントが均一に投入されることを確実にできる。加えて、後続オペレーション、先行オペレーション、近傍計算を表示するノードをモジュロ計算を使用することにより効果的に実行することができる。
【００１６】
システム１００はさらにグローバルリース１０１により表されたすべてのノード（１〜ｎ、ｎは整数）からシードノードまでのリースの実行が可能である。このように、この主題の革新部分は、フェデレーションにおける各ノードはすべてのシードノードにおいてリースを維持することを必要とし、そこでは、フェデレーションが周知のシードノードのセット（１〜ｍ、ｍは整数である）を有している。グローバルリースの最長期間はさらにグローバルリースのタイムアウト時期Ｇ（例えば、所定の存続時間）によって明確に特定される。
【００１７】
関連する態様において、ノードがグローバルリースの定足数より少なく残されると、典型的にそれはすぐに終了（たとえば、自動的に停止する）しなければならず、再びリングの再接続を試みる。そして、典型的に、シードノードの定足数が終了するとリングはそれ以降Ｇの期間中に終了できることが確実となる。これによって、シードノードの定足数が新しいリングの形成を決定する場合、それはＧの期間が終了後達成されることができ、一方で前のリングのすべてのノードが去ることを確実にする。そして、このようなシードノードの定足数はスーパーシードノードとして１のシードノードを選択でき、安全にリングを形成できる。
【００１８】
図２は、この主題の革新部分の更なる実例に従って、典型的なシステム２００を示している。図示のとおり、各シードノードにより、期間の限られたチケットの２つのタイプ、グローバルチケット２０２とスーパーチケット２０４を、発行することができる。一般に、各チケットは以下の制限に従っている。１）関連するＴＴＬでそれが終了した後のもの。２）受信したノードおよび送信元のシードノードからの行動を確実にするものであって、行動のタイプがチケットのタイプにより決定されるもの。３）チケットが１のノードからもうひとつのノードへ渡されることができる。４）すべてのチケットが、それが発行される前に存続することが必要とされるため、そのチケットはノードの再起動を切り抜けることができる（例えば、チケットが発行されることは、発行するノードが明確な責任を取ることを約束していることを示し、その結果、何の約束が提供されたかを記憶しておかなければならない）。５）チケットは、受信ノードにおいてそれが満了した「後」に、発行したノードにおいて満了するべきである。
【００１９】
その上、図２に示したように、シードノードは２つのタイプのシードノードを生成できる。  
１．グローバルチケット：各シードノードはフェデレーションにおけるすべてのノードにグローバルチケットを発行させる。グローバルチケットと関連付ける２つの保障が存在する。  
ａ）シードノードはフェデレーションにおいて独自のグローバルチケットの定足数が存在できないことが明白でない限り新しいリングを形成することを試さないであろう。 
ｂ）ノードは終了するか自己消滅し、グローバルチケットの定足数を失ってリングを再結合する。 
２．スーパーチケット：このようなチケットは、新しいリングが生成されているときに、シードノードからシードノードへ、またブートストラップ段階（以下詳細に説明される）の間のみにおいて発行される。ブートストラップ段階の間、ノードはそのスーパーチケットを抱えているノードのためのグローバルチケットの発行が可能となるだけである。そのスーパーチケットを渡すことに関してノードはグローバルチケットを発行させるその権利を失う。
【００２０】
図３は、この主題の革新部分の特定の態様のひとつにしたがって、ノードＡ３０２とノードＢ３０４との間の、特定のチケット交換を示している。受信ノードの満了の後の発行したノードの満了の制限に対処することを、確実にするために、メッセージへの反応を通して、チケットを転送することができる。例えば、図３は、ノードＢは、ノードＡから、チケットを入手することを要求すると仮定する。最初および３１０において、ノードＢは、ノードＡに、ＴSENDを含む要求メッセージを、送ることができるが、ＴSENDは、ノードＢのクロックにおいてメッセージが贈られる時間を、表している。ノードＡは、Ｂへの返答メッセージにおいてチケット３１１をＴSENDと一緒に添付する。ノードＢがチケット３１１を受け取ったとき、ノードＢは、チケットにおいてＴCURRENTからＴSENDを差し引いて時間を減らす。チケットの発行がＴCURRENTからＴSEND間に限定されることにより時間が経過するため、チケットが、Ａで満了する前に、Ａで満了できることを確実にできる。
【００２１】
図４はこの主題の革新部分の特別な態様に従ってブートストラップ段階４０２を実行するリング情報コンポーネント４０２を含むシステム４００を示している。このようなブートストラップ段階４１２は、シードノードのライフサイクルの開始と関連付けることができ、いつでも１のリングのみが存在することを確実にする。さらに、このようなブートストラップ段階４１２の間、既存のリングが検出された場合、シードノードはノンシードノードと同様の方法で、既存のリングと結合できる。さもなければ、このような段階は１のシードノードをスーパーシードノードとして選択することを試みる。その後、最初のノードとして、新しいスーパーシードノードとともに、新しいリングが生じる。その上、１のリングのみがシステムに存在することを確実にするために以下の状況が課される。  
１ａ）ブートストラップ段階の間に１のシードノードがスーパーシードノードとして選択される。  
１ｂ）スーパーシードはシードノードの定足数により選択されることのみできる。  
１ｃ）スーパーシードはノード定足数におけるすべてのシードノードからのグローバルチケットが満了したことを保障した後のみにおいては新しいリングを形成することができる。
【００２２】
同様に、ブートトラップ段階の後、それがグローバルリースの定足数を失った場合、ノードはそれ自身終了しなければならずリングを再結合しなければならない。それに応じて、任意の時点で、１のリングのみがシステム中に存在できる。例えば、最初のブートストラップ段階で、前のリングが存在しない。そのため、ただ１のスーパーシードノードの選択は１のリングの存在を確実にできる（上記１ａの制限事項）。もうひとつの例としては、次のブートストラップ段階が検討されたとき、スーパーシードノードの選択の後、新しいリングが、リングを結合するための最初のノードとして、ただ生成だけする。その上、スーパーシードノードは、シードノードの定足数により選択されることのみできる（１ｂの制限事項）。シードノードの定足数がスーパーシードノードを選択した場合、定足数が前のリングを離れることが示される。スーパーシードノードが新しいリングで作成される以前に、シードノードの定足数が最後のグローバルチケットを発行させたときから時間Ｇが経過することを確実にできる。加えて、それはリングの前のインスタンスが消滅することをさらに確実にでき、それゆえほとんど１のリングの存在を表示している。
【００２３】
ブートストラップ段階
図５は、上述された制限の実行を促進する典型的な手順５００を示している。この典型的な方法が、さまざまな事象および／または動作を表した一連のブロックとして本明細書で示され説明されるが、この主題の革新部分は、そのようなブロックの示された順序に限定されない。例えば、ある動作および事象が、この革新部分にしたがって、本明細書に示された順序とは別に、異なる順序および／または他の動作または事象と同時に起こる。同様に、必ずしも示されたすべてのブロック、事象または動作が、順序をこの主題の核心部分にしたがって実行することを必要としているわけではない。そのうえ、示され、説明されていない他のシステムまたは装置と関連するだけでなく、この核心部分に従い、例示された方法と他の方法が、本明細書に示され説明された方法とも関連して、実行されることが、認識できるであろう。一般的に、シードノードは、ブートストラップ段階において、いつでもスタートすることができる。そのような段階および５１０における間、５２０において、他のすべてのシードノードに、周期的にＳＥＥＤＰＩＮＧメッセージを送ることにより、他のシードノードの状態の経過を追う。すべてのシードノードは、その最新の段階を伝達しながら、ＳＥＥＤＰＩＮＧＲＥＳＰＯＮＣＥメッセージに反応する。シードノードが、もうひとつのシードノードが５３０で決定したように、フェデレーションにおいて、すでに結合されていることを認識している場合、シードノードは、５４０において、ブートストラップ段階をただ離れるのみであり、結合段階に入ることができるが、その結合段階において、リングの結合のためのメッセージ交換の一部として、ＪＯＩＮメッセージを送るであろう。その他または５５０において、シードノードはブートストラップ段階に残る。
【００２４】
一般的に、すべてのシードノードは、のスーパーチケットの経過を追う。典型的に、スーパーシードが、ブートストラップ段階に入ったとき、自身のスーパーチケットを所有するであろう。（例外は、シードノードがスーパーチケットを他のシードノードに発行させ、その後スーパーチケットが満了する前に再起動させたときであり、そこでは他のシードノードにスーパーチケットが与えられるため、再スタートの後どのようなスーパーチケットももはや所有しない。シードノードは以前発行したスーパーチケットが満了した後スーパーチケットを再び所有する。）その上、スーパーチケットを転送することができる。ノードがＳＥＥＤＰＩＮＧメッセージを受け取ったとき、ノードがブートストラップの段階にあり、送信者側のノードｉｄが、自身のノードｉｄより小さい場合であるとき、ノードは（もしいくらかでもあれば）、自身の有するすべてのチケットを、送信者に返答されたＳＥＥＤＰＩＮＧＲＥＳＰＯＮＳＥメッセージにおいて、転送するであろう。スーパーチケットが転送されたとき、対応するグローバルチケットの満了時間は、転送される。
【００２５】
同様に、６１０において、シードノードが（例えば、少なくとも）、スーパーチケットの定足数を所有することを決定し、６２０において、定足数内のシードノードにより発行したすべてのグローバルチケットが満了するとき、６３０において、スーパーシードノードとして、ブートストラップ段階を離れることができる。シードノードは、また、図７における手順７００の動作７１０に示すように、６４０において対応するスーパーチケットの満了期間として定められた期間において、定足数のすべてのシードノードの代わりに、グローバルチケットを発行させるであろう。７２０において、シードノードはその後リングを形成し、７３０において他のすべてのシードノードがブートストラップ段階をはなれ、７４０における結合段階に入ることができるため、通知メッセージを他のすべてのシードノードに送るであろう。
【００２６】
グローバルリースの維持
追加の態様にしたがって、ノードは、ブートラップ段階と結合段階において、グローバルリースを有することを必要としない。結合段階の最後において、結合しているノードは、ＪＯＩＮＲＥＳＰＯＮＳＥメッセージから、グローバルリースを受け取るであろう。この点から、これまでにグローバルリースの定足数を失っている場合には、ノードは、処理を終了するか自己消滅しなければならない。グローバルリースは、最初は、シードノードにより生成され、その後（直接的または間接的に）他のノードへ転送される。アクティブなスーパーチケットを発行させたシードノードは、グローバルチケットを発行させたその権利を失うことが、認識される。しかしながら、例外が存在し、その例外は、シードノードが、自身により発行した最新のグローバルチケットよりも新しいグローバルチケットの受け取りを認識し、そのグローバルチケットが、その最近のスーパーチケットが発行されたとき（ただしスーパーチケットが消滅する前）よりも新しいものであることを認識した場合には、シードノードは、そのスーパーチケットがシードノードにより消費されるに違いなく、スーパーシードは、シードノードに代わってグローバルチケットを与えるに違いないと結論付けることができる。この場合、シードノードは、シードノードが発行させたグローバルチケットを無視し、あたかもスーパーチケットがすでに満了したかのように、グローバルチケットを与えることができる。この最適化なしに、このシードノードの正当なグローバルチケットがリング全体の中に存在しない十分に小さい時間ウィンドウが存在することが、確実となり、そのため、グローバル期間の損失の可能性が高い。
【００２７】
下に詳解されたものは、すべてのノードにおいてどれだけのグローバルリースが更新されるかに関するものである。グローバルチケットがシードノードにより発行するだけであるため、チケットは、フェデレーションにおけるすべてのノードに達する必要がある。ひとつの態様においては、各ノードを、すべてのシードノードにおいてリースを維持させる強引な選択を強制することができる。更なる態様にしたがって、リースは、存在するメッセージと抱き合わせることができる。そのようなメッセージは、
１．障害の発見のために隣接したノードの間で交換されたリースメッセージ
２．ノードが経路指定テーブルを更新するために送らなければならないＵＰＤＡＴＥ／ＵＰＤＡＴＥＲＥＳＰＯＮＳＥメッセージ
を含むことができる。
【００２８】
その上、応答メッセージは、１のノードからもうひとつのノードへ転送されているチケットを含むことができる。さらに、どのノードも、グローバルチケットを含んでいるテーブルを維持し、それらのチケットを順々に回すメッセージを、使用することができる。
【００２９】
図８は、この主題の革新部分の態様に従って、ノードの間のメッセージ交換の特定の手順８００を示している。最初におよび８１０において、「ＥＳＴＡＢＬＩＳＨ  ＬＥＡＳＥ」／「ＲＥＮＥＷ  ＬＥＡＳＥ」／「ＵＰＤＡＴＥ」メッセージのそれぞれは、送信時間ＴSENDを含むことができる。その後、「ＥＳＴＡＢＬＩＳＨ  ＬＥＡＳＥ」／「ＲＥＮＥＷ  ＬＥＡＳＥ」／「ＵＰＤＡＴＥ」メッセージを受け取ることおよび応答（「ＬＥＡＳＥ  ＲＥＳＰＯＮＳＥ」／「ＵＰＤＡＴＥ  ＲＥＳＰＯＮＳＥ」）を送ることを決定することに関して、８２０において、ノードは、ノードが有するチケットおよびＴSENDを、メッセージ応答に添付することができる。８３０でおよびチケットを受け取ることに関して、ノードは、チケットにおける期間を、ＴCURRENTからＴSENDを差し引いて縮小する。その後および８４０において、ノードはシードノードに対応する既存のチケットを検査できる。それに応じて、新しいチケットの期間が既存のチケットにおける期間よりも長い場合、８６０において、既存のチケットは新しいチケットにより交換される。
【００３０】
関連する態様において、チケットがその存続期間のＴGoToSeedNode内にあるとき、そのようなノードは、シードノードから直接新しいチケットを取得することを試みることができる。その上、任意のチケットの存続期間において、ノードがチケットの定足数が満了したことを検出した場合、ノードは、終了または消滅し、リングの再結合を試みる。
【００３１】
図９は、この主題の革新部分の追加の態様に関連する、リカバリコンポーネント９０４を実行する、区分されたアプリケーションのフレームワークのシステム９００を示している。リカバリコンポーネント９０４は、ルーティングノードにより、リカバリプロトコルを開始できる。プローブメッセージは、それがもうひとつのルーティングノードに届くまで、ノードごとに送られることができるが、そのノードは、その後プローブメッセージが送信元に届くまで、ノードごとに再びプローブメッセージを送り返すことができる。その上、パスが戻ったすべてのノードは、送り返されたメッセージを取得する前に、ノードが、転送されるトークンを承認するのを防ぐために、そのリカバリバージョンをインクリメントできる。
【００３２】
そのようなシステムの下で、ノードＮは、その後継Ｓと先行Ｐのノード（ここで、Ｓ、Ｎ、Ｐは整数）との間のｉｄの範囲の所有権を請求する。所有権の範囲を、モジューロ計算を使用して、（Ｎ−（Ｎ−Ｐ）／２、Ｎ＋（Ｓ−Ｎ）／２］と決定することができる。Ｐ、ＮおよびＳのノードは、１のノードのみが目的のｉｄに送られたメッセージを受け入れることを確実にすることと一致することを、示すことができ、そこでは、そのような一致はリングの一貫性を暗示する。リングの一貫性は、それ自身では、安全なプロパティを満たすのに十分でないことが認識できる。例えば、区分されたリングが、個々には一致するが、安全なプロパティを妨害する。この主題の革新部分の様々な態様は、典型的に、当初からの発展から、リングの区分を防ぐ。
【００３３】
すべてのノード９０１はトークンの操作のための連続する番号を維持する。連続する番号は「０」に初期化でき、すべてのトークンの操作のためにインクリメントされる。トークンの操作はトークンの作成、トークンの分割、トークンの合併およびトークンの回復である。すべてのトークンの転送されたメッセージは転送されたトークンを受信ノードにより受け入れることのできる、目的とするトークンの連続する番号を特定する。受信ノードは、特定された目的とする連続する番号が、その現在のトークンの連続する番号と一致しない場合には、転送されたトークンを受け入れることができない。例えば、リングにおける最初のシードノードは、全体のＩＤスペースのために、有効なトークンを生成し、自動的にルーティングノードに変わる。その上、他の任意の結合しているノードは、結合しているノードのＩＤを所有しているため、そのトークンを、既存の最も近いルーティングノードから取得することを試みる。結合しているノードは、トークンの要求のメッセージを、自身のＩＤに送ることにより、最も近いノードを決める。ルーティンノードが、ルーティンノードでないノードから、トークンの要求メッセージをｘ（ｘは整数から始まる）のＩＤで受け取ったとき、それは、ルーティンノードの有効なトークンを分割する点として、自身のＩＤの中間点およびｘを使用して２つに分割し、他のトークンを保有している間に、ｘを含むトークンを、結合しているノードに転送する。
【００３４】
ルーティンノードが、新しい先行または後継のルーティングノードを、ｘのＩＤで、検出したときはいつでも、自身のトークンが、新しいノードに近づくＩＤのスペースを含むことを検証するために、ルーティングノードを検査する。そうである場合、それは、トークンを分割する点として、それ自身のＩＤの中間点およびｘを使用して、２つに分割し、他のトークンを保有している間に、ｘを含むトークンを新しいノードに転送する。どのルーティンノードも、そのような動作を行う機会を、無限に有しているため、すぐ隣のノードと、通信することができる。
【００３５】
加えて、ルーティングノードがリングを離れることを要求したとき、それはそのトークンを分割する点として先行又は後継のＩＤを中間点として使用して２つに分割し、２つのトークンを先行または後継のノードにそれぞれ転送する。その上、ノードは、トークンを所有していない場合、入ってくるトークンを受け入れることができ、入ってくるトークンの範囲は、自身のＩＤを含んでいるか、またはそのトークンは入ってくるトークンの近くにある。ノードが、トークンを受け入れることができない場合、ノードは、トークンを拒絶し、可能であれば、入ってくるトークンの範囲の近くであることが認識されたノードを示唆する。それ故、首尾よくそのトークンをその後継および先行のノード双方から取得したルーティンノードは、オペレーティングノードとみなされる。オペレーティングノードは、また、ルーティングノードであり、それが再起動するまで、オペレーティングノードのままであることが認識される。
【００３６】
このアプリケーションが使用されているため、「コンポーネント」や「システム」という言葉は、ハードウェア、ハードウェアとソフトウェアの組み合わせ、ソフトウェア、実行中のソフトウェアのどれかを表していることが意図される。例えばコンポーネントは、プロセッサにおいて実行されている処理、プロセッサ、オブジェクト、実行ファイル、実行するスレッド、プログラムおよび／又はコンピュータとすることができるが、それには限定されない。実例として、サーバーで実行されているアプリケーションも、サーバーもコンポーネントとすることができる。１またはそれ以上のコンポーネントは、処理および／または実行スレッド中に存在することができ、コンポーネントは、１のコンピュータをローカライズでき、および／または、２またはそれ以上のコンピュータに、分割されることができる。
【００３７】
その上、この主題の革新部分の全部または一部はそれに関して公開された発明を実施するためのコンピュータを操作するためのソフトウェア、ファームウェア、ハードウェアまたはその結合を作成するための一般的なプログラミングおよび／またはエンジニアリングの技術を使用してシステム、メソッド、装置または製品として実行される。例えば、コンピュータ可読媒体は、磁気記憶媒体（例えば、ハードディスク、フロッピーディスク、磁気ストライプ・・・）、光ディスク（ＣＤ、ＤＶＤ・・・）、スマートカードおよびフラッシュメモリデバイス（メモリカード、スティックメモリ、ドライブキー・・・）を含むことができるが、それに限定されない。さらに、搬送波は電子メールを送受信したりインターネットやＬＡＮのようなネットワークにアクセスしたりするのに使用されるコンピュータ可読電子データを送信するのに利用されることができることが認識されるはずである。もちろん、当業者はこの主題の請求する範囲および趣旨から逸脱することなく多くの変更がなされてこの機器構成となることを認識できるであろう。
【００３８】
本明細書に公開されたさまざまな態様の状況を提供するために、図１０と１１は、以下の詳細と同様に、公開された主題が実行できるさまざまな適切な環境の簡潔で、一般的な説明を提供することを意図する。この主題は、上記において、１および／または複数のコンピュータが実行するコンピュータプログラムのコンピュータが実行可能な命令の一般的なコンテクストにおいて説明されてきたが、当業者は、本発明が、他のプログラムモジュールとの組み合わせにおいても実行されうることが認識できるであろう。一般的に、プログラムモジュールは、ルーティン、プログラム、コンポーネント、データ構成およびそれと同様のものを含むが、これらは、特別なタスクおよび／又は特別な理論上のデータタイプを実行するものである。
【００３９】
その上、当業者は、この革新的なメソッドを、シングルプロセッサ又はマルチプロセッサのコンピュータシステム、ミニコンピューティングデバイス、メインフレームコンピュータを、パーソナルコンピュータ、携帯端末（例えば、携帯情報端末（ＰＤＡ）、電話、時計・・・）、マイクロプロセッサを用いる又はプログラミング可能な家電製品又は工業電子機器、などと同様に含んでいる他のコンピュータシステムの設定においても実施することができることを認識できるであろう。図で示したこの態様は、また、通信ネットワークを通してリンクされた、離れた処理デバイスによりタスクが実行される、区分されたコンピューティング環境においても実施されうる。しかし、この発明のすべてではないが、いくつかの態様は、スタンドアロンのコンピュータにおいて実行できる。区分されたコンピューティング環境において、プログラムモジュールは、ローカル接続および離れたメモリデバイスの双方に接続されうる。
【００４０】
図１０を参照にして、本発明のさまざまな実施態様を実行するためのコンピュータ１０１２を含む例示した環境１０１０が説明される。コンピュータ１０１２は、プロセシングユニット１０１４、システムメモリ１０１６、およびシステムバス１０１８を含む。システムバス１０１８は、システムメモリ１０１６またはプロセシングユニット１０１４を含むがそれに限定されないシステムコンポーネントを連結する。プロセシングユニット１０１４は、さまざまな利用可能なプロセッサのどれかになることができる。２重のマイクロプロセッサと他のマルチプロセッサのアーキテクチャーを、プロセシングユニット１０１４として利用することができる。
【００４１】
システムバス１０１８は、１１ビットバス、ＩＳＡ（Ｉｎｄｕｓｔｒｉａｌ  Ｓｔａｎｄｅｒｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ）、ＭＳＡ（Ｍｉｃｒｏ−Ｃｈａｎｎｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ）、ＥＩＳＡ（Ｅｘｔｅｎｄｅｄ  ＩＳＡ）、ＩＤＥ（Ｉｎｔｅｌｌｉｇｅｎｔ  Ｄｒｉｖｅ  Ｅｌｅｃｔｒｏｎｉｃｓ）、ＶＬＢ（ＶＥＳＡ  Ｌｏｃａｌ  Ｂｕｓ）、ＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｌｌｉｇｅｎｔ）、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）、ＡＧＰ（Ａｄｖａｎｃｅｄ  Ｇｒａｐｈｉｃｓ  Ｐｏｒｔ）、ＰＣＭＣＩＡ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ  Ｍｅｍｏｒｙ  Ｃａｒｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ａｓｓｏｃｉａｔｉｏｎ  ｂｕｓ）、そしてＳＣＳＩ（Ｓｍａｌｌ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍｓ  Ｉｎｔｅｒｆａｃｅ）を含むがそれに限定されないさまざまな利用可能なバスアーキテクチャーを使用している、メモリバスまたはメモリコントローラ、周辺機器のバスまたは外部のバス、および／またはローカルバスを含むいくつかのタイプのバス構造とすることができる。
【００４２】
システムメモリ１０１６は、揮発性メモリ１０２０と不揮発性メモリ１０２２を含んでいる。基本入出力システム（ＢＩＯＳ）は、起動中のような、コンピュータ１０１２内の要素の間の情報を転送する基本ルーティンを含んでおり、不揮発性メモリ１０２２に記録される。例えば、不揮発性メモリ１０２２は、ＲＯＭ（ｒｅａｄ  ｏｎｌｙ  ｍｅｍｏｒｙ）、ＰＲＯＭ（ｐｒｏｇｒａｍａｂｌｅ  ＲＯＭ）、ＭＰＲＯＭ（ｅｌｅｃｔｒｉｃａｌｌｙ  ＰＲＯＭ）、ＥＥＰＲＯＭ（ｅｌｅｃｔｒｉｃａｌｌｙ  ＰＲＯＭ）またはフラッシュメモリを含んでいる。揮発性メモリ１０２０は、ＲＡＭ（ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）を含んでいるが、これは外部のキャッシュメモリとして作動する。例として、限定せずに、ＲＡＭは、ＳＲＡＭ（ｓｙｎｃｈｒｏｎｏｕｓ  ＲＡＭ）、ＤＲＡＭ（ｄｙｎａｍｉｃ  ＲＡＭ）、ＳＤＲＡＭ（ｓｙｎｃｈｒｏｎｏｕｓ  ＤＲＡＭ）、ＤＤＲ  ＳＤＲＡＭ（ｄｏｂｌｅ  ｄａｔａ  ｒａｔｅ  ＳＤＲＡＭ）、ＥＳＤＲＡＭ（ｅｎｈａｎｃｅｄ  ＳＤＲＡＭ）、ＳＬＤＲＡＭ（Ｓｙｎｃｈｌｉｎｋ  ＤＲＡＭ）、ＤＲＲＡＭ（ｄｉｒｅｃｔ  Ｒａｍｂｕｓ  ＲＡＭ）のような、多くの形式を利用できる。
【００４３】
コンピュータ１０１２はまた、取り外し可能な／取り外し不可能な、揮発性の／不揮発性のコンピュータ記録媒体を含む。図１０はディスクストレージ１０２４を示しているが、ここにおいてはこのディスクストレージ１０２４は磁気ディスクドライブ、フロッピーディスクドライブ、テープドライブ、Ｊａｚドライブ、Ｚｉｐドライブ、ＬＳ−６０ドライブ、フラッシュメモリーカードまたはメモリースティックを含んでいるがそれに限定されない。さらに、ディスクストレージ１０２４は、ＣＤ−ＲＯＭドライブ、ＣＤ−Ｒドライブ、ＣＤ−ＲＷドライブまたはＤＶＤ−ＲＯＭドライブのような光ディスクのドライブを含むがそれに限定されない他の記録媒体と離れた、または組み合わせた、記録媒体を含むことができる。ディスク記録デバイス１０２４のシステムバス１０１８への結合を容易にするために、取り外し可能または取り外し不可能なインターフェースは、一般的にインターフェース１０２６のように使用される。
【００４４】
図１０は、適切な操作環境１０１０で説明されたユーザーとベーシックコンピュータ資源との中間で作動するソフトウェアを説明することが認識される。そのようなソフトウェアは、操作システム１０２８を含んでいる。操作システム１０２８は、ディスク記録装置１０２４に記録できるが、コンピュータシステムの資源を制御し、分配するように行動する。システムアプリケーション１０３０は、システムメモリ１０１６またはディスク記録装置１０２４のどちらかに記録されたプログラムモジュール１０３２およびプログラムデータ１０３４を通して、操作システム１０２８による資源の管理を利用する。本明細書で説明される様々なコンポーネントを、様々な操作システムまたは操作システムの組み合わせで実行できる。
【００４５】
ユーザーは、入力デバイス１０３６を通して、コマンドまたは情報をコンピュータ５１２に入力する。入力デバイスは、マウス、トラックボール、スタイラスペン、タッチパッド、キーボード、マイクロホン、ジョイスティック、ゲームパッド、衛星受信アンテナ、スキャナ、ＴＶチューナカード、デジタルカメラ、デジタルビデオカメラ、ウェブカメラ、またはそれと同様のものを含むがそれに限定されない。これらまたは他の入力デバイスは、プロセシングユニット１０１４をシステムバス１０１８を通してインターフェースポート１０３８を介して接続する。インターフェースポート１０３８は、例えば直列ポート、並列ポート、ゲームポートおよびＵＳＢを含んでいる。出力デバイス１０４０は入力デバイス１０３６と同様のタイプのポートを使用する。それゆえに、例えばＵＳＢポートは、コンピュータ１０１２への入力を提供し、コンピュータ１０１２からの出力情報を出力デバイス１０４０へ提供するために使用できる。出力アダプター１０４２は、特別なアダプターを必要とする出力デバイス１０４０の中に、モニター、スピーカーおよびプリンターのようないくつかの出力デバイス１０４０があるということを説明するために提供される。出力デバイス１０４０は、実例として、限定されずに、出力デバイス１０４０とシステムバス１０１８との間を接続する手段を提供するビデオおよびサウンドカードを含む。他のデバイスおよび／またはデバイスのシステムは、リモートコンピュータ１０４４のような入力および出力両方の機能を提供することがわかるはずである。
【００４６】
コンピュータ１０１２は、ネットワークで結ばれた環境においてリモートコンピュータ１０４４のような１またはそれ以上のリモートコンピュータの理論上の接続を使用して操作できる。リモートコンピュータ１０４４は、パーソナルコンピュータ、サーバー、ルーター、ネットワークＰＣ、ワークステーション、家電製品のマイクロプロセッサ、ピアデバイスまたは他の共通ネットワークノードおよびそれと同等のものとすることができ、一般的にコンピュータ１０１２と関連して説明される要素の多くまたはすべてを含む。簡潔にするために、リモートコンピュータ１０４４とともにメモリ記憶装置１０４６のみが説明される。リモートコンピュータ１０４４は、ネットワークインターフェース１０４８を通してコンピュータ１０１２と理論的に接続され、その後、通信接続１０５０を介して、物理的に接続される。ネットワークインターフェース１０４８は、ＬＡＮ（ローカルエリアネットワーク）やＷＡＮ（ワイドエリアネットワーク）のような通信ネットワークにわたっている。ＬＡＮの技術は、ＦＤＤＩ（光ファイバー分散データインターフェース）、ＣＤＤＩ（メタルケーブル分散データインターフェース）、イーサネット／ＩＥＥＥ８０２．３、トークンリング／ＩＥＥＥ８０２．５およびこれと同等のものを含む。ＷＡＮの技術は、２地点間リンク、ＩＳＤＮ（総合デジタル通信網）のような回路交換網、さらに変化したものとして、パケット交換網およびＤＳＬ（デジタル加入者回線）を含むが、それに限定されない。
【００４７】
通信接続１０５０は、ネットワークインターフェース１０４８とバス１０１８との接続に利用するハードウェア／ソフトウェアを示している。通信接続１０５０は、コンピュータ１０１２の内部を明確に図示するために示されるが、それはまた、コンピュータ１０１２の外部ともなりうる。ネットワークインターフェース１０４８の接続のためのソフトウェア／ハードウェアの必需品は、例示のみを目的として、通常の電話のモデム、ケーブルモデムおよびＤＳＬモデム、ＩＳＤＮアダプター、およびイーサネットカードのような内外の技術を含む。
【００４８】
図１１は、フェデレーションの一部としてノードを実行するために利用できる、サンプルのコンピューティング環境１１００の略ブロック図である。システム１１００は、１またはそれ以上のクライアント１１１０を含んでいる。クライアント１１１０は、ハードウェアおよび／またはソフトウェア（例えば、スレッド、プロセス、コンピューティングデバイス）とすることができる。
【００４９】
システム１１０はまた、１またはそれ以上のサーバー１１３０を含んでいる。サーバー１１３０はまた、ハードウェア／ソフトウェア（例えば、スレッド、プロセス、コンピューティングデバイス）とすることができる。サーバー１１３０は、例えば本明細書で説明されたコンポーネントを利用することにより変換を実行するために、スレッドを保管する。クライアント１１１０とサーバー１１３０との間の１の可能な通信は、２またはそれ以上のコンピュータプロセスの間で送信されるために適応されたデータパケットの形をとっている。システム１１００は、クライアント１１１０とサーバー１１３０との間の通信を容易にするために利用されることができる、通信フレームワーク１１５０を含む。クライアント１１１０は、情報の局所をクライアント１１１０に記録しておくために利用されることができる、１またはそれ以上のクライアントデータストア１１６０と、動作可能なように接続されている。同様に、サーバー１１３０は、情報の局所をサーバーデータストア１１４０に記録しておくために、１又はそれ以上のサーバーデータストア１１４０と動作可能なように接続される。
【００５０】
上述したものは、さまざまな例示的な態様を含む。もちろん、これらの態様を説明する目的のためにすべての考えられるコンポーネントの組み合わせや手順を説明することは不可能であるが、当業者は、多くの更なる組み合わせや置換が可能であることを認識できるであろう。それに応じて、本明細書で説明された態様は、付加された請求の趣旨および範囲の中に収まるすべての修正、改良、および変更を含んでいることを意図する。
【００５１】
その上、「含む」という用語が詳細な説明および特許請求の範囲で使用される限りにおいて、そのような用語は、特許請求の範囲において暫定的な言葉として利用されたときに「備える（Ｃｏｍｐｒｉｓｉｎｇ）」と解釈されるものとして、「備える（Ｃｏｍｐｒｉｓｉｎｇ）」という用語と同様に包含的であることが意図される。
【図１】
2012507076.tif 000003
【図２】
2012507076.tif 000004
【図３】
2012507076.tif 000005
【図４】
2012507076.tif 000006
【図５】
2012507076.tif 000007
【図６】
2012507076.tif 000008
【図７】
2012507076.tif 000009
【図８】
2012507076.tif 000010
【図９】
2012507076.tif 000011
【図１０】
2012507076.tif 000012
【図１１】
2012507076.tif 000013
【国際調査報告】
2012507076.tif 000014
2012507076.tif 000015