分散型システムにおける処理を調整する方法

专利摘要:
この方法は、分散型コンピュータシステムにおける処理ユニット（１０）を制御する。複数のメッセージ（２）を含む少なくとも１つのストリーム（４）がクライアントユニット（１４）により各処理ユニット（１０）へ送信される。各メッセージ（２）は、順序付けされたグループのメンバーである識別子を含む。複数のメッセージ（２）は、それらの識別子のシーケンスで送信される。制御ユニット（１２）は、アクションを実行する要求（６）を処理ユニット（１０）へ送信する。要求（６）は、順序付けされたグループのメンバーであるトリガーを含む。受信されたメッセージ（２）の識別子がトリガー以上である場合には、処理ユニット（１０）は、アクションを起動する。この方法は、処理ユニット（１０）を制御するシステム、処理ユニット（１０）、及び制御ユニット（１２）にも関連する。
公开号:JP2011510411A
申请号:JP2010543392
申请日:2008-01-25
公开日:2011-03-31
发明作者:マーティン ショール，；ユルゲン；フェリックス ハンペ，；マルクス ブリンドプケ，；ミヒャエル プロイス，；オット ロス，
申请人:グローバル インフィニプール ゲーエムベーハー；
IPC主号:G06F13-00

专利说明:

[0001] 本発明は、分散型システムにおける処理を調整する方法に関するものであり、より詳細には、分散型システムの複数の処理ユニットを制御して、それらのアクション又は幾つかのアクションを調整する方法に関するものである。また、本発明は、複数の処理ユニットを制御するように構成されたシステム、並びに、当該システムにおいて使用するよう構成された処理ユニット及び制御ユニットにも関するものである。]
背景技術

[0002] コンピュータネットワークテクノロジーにおいて、分散型コンピューティングは、複数の個々の処理要素（又はユニット）で１つのタスクを処理するものである。個々の処理要素は、共に接続された異なるコンピュータに配置され得る。各個々の処理要素は、タスクの一部分を実行する。個々の処理要素でのタスクの一部分の処理を調整することは、分散型システムを構成している個々の処理要素から到来する出力を適切に且つ一貫してまとめることを含む。]
[0003] 個々の処理要素が共通のクロックを共有する場合には、共通のタイムテーブルに従ってタスクの各部分の処理及び対応する出力の送信を実行するように共通の制御ユニットによりそれらに命令することができる。従って、個々の処理要素から到来する出力を収集する役割を果たす中央受信ユニットにより時間的に一貫した出力を得ることができる。出力は、各々、タイムスタンプを保持するメッセージであり、従って、メッセージペイロードを、それが中央受信ユニットによる受信されると、時間に関して解釈することができる。]
[0004] 例えば、個々の処理要素は、注目エリアにおいて分散された地震センサ（地震計）であり得る。これらセンサは、中央位置からブロードキャストされるクロック信号に基づくことにより共通クロックを共用し得る。特定のクロック信号を受信すると、地震センサは、測定値及び特定のタイムスタンプを含むメッセージを送信するようにプログラムされ得る。中央受信ユニットにより受信されると、測定値を、時間に関して一貫した且つ意義のある方法で処理することができる。これは、各測定値にタイムスタンプが付随するからである。これら測定値は、例えば、互いに意義があるように比較され、分析され得る。]
[0005] 個々の処理要素が共通のクロックを共用せず、各々がローカルクロックを有する場合には、ローカルクロックが互いにドリフトし得る。そして、各要素から到来する測定値を伴うタイムスタンプは、時間順の観点からは、一貫性に欠けることがある。この問題に対する１つの解決策は、ローカルクロックを同期させることである。]
[0006] 上述した「地震センサ」の例では、これは、各地震センサがローカルクロックを有し、地震センサのローカルクロックが共通の中央クロックを参照して定期的に調整されることを意味する。中央クロックは、地震センサのローカルクロックより正確で且つ安定性があると仮定される。ある時間でローカルクロックを参照して、地震センサは、測定値及び調整されたローカルクロックから得られたタイムスタンプを含むメッセージを送信するようにプログラムされ得る。したがって、中央受信ユニットは、その受信したメッセージを、時間に関して一貫した且つ意義のある方法で、処理することができる。]
[0007] このような方法の一例が、サウラブ・ガナリワル、ラム・クマー、サチン・アドラカ、及びマニ・スリバスタバの“Network-wide time synchronization in sensor networks”、 Technical report,Networked and Embedded Systems Lab, Elec. Eng. Dept., UCLA、２００２年４月（参照文献［１］）、に開示されている。より詳細には、この参照文献［１］は、ネットワークにおけるセンサのローカルクロックを同期する方法を開示している。]
[0008] 別の例が、ケイ・ローマーの“Time synchronization in ad hoc network”、Proceedings of the 2ndACMinternational symposium on mobile and ad hoc networking & computing、２００１年１０月４−５日、米国カリフォルニア州ロングビーチ（参照文献［２］）、に開示されている。より詳細には、参照文献［２］は、コンポーネントが自律的にネットワーク化されるネットワーク、例えば、いわゆるアドホックネットワークに対する時間同期化方法を開示している。]
[0009] 参照文献［１］及び［２］は、時間に関して個々のコンポーネントの出力を一貫して解釈する上で中央受信ユニットを助成するという課題及び目的に向けられた第１のクラスの方法の一例を開示している。換言すれば、これらの方法は、例えば、当該エリアの特定の位置において規則的な時点で地震波を測定するために、過去のアクションを解釈することを目的としている。]
[0010] 本発明の背景を形成する第２のクラスの方法は、分散型システムにおいて意義のあるグローバルな状態を決定することに向けられている。]
[0011] これらの方法の１つは、Ｋ．マニ・チャンデー、レスリー・ランポートの“Distributed Snapshots: Determining Global States of DistributedSystems”、ACMTransactions on Computer Systems、第３巻、第１号、１９８５年２月、第６３−７５ページ（参照文献［３］）、に開示されている。これは、処理の実行中に分散型システムのグローバル状態を決定するための方法を開示している。この方法は、分散型システムにおいて安定な特性に到達したときを検出するのに役立つもので、処理の実行が共通のクロック又はメモリを共用しないことを仮定している。各プロセスは、その状態及び到来するチャンネルの状態を記録し、そして記録されたプロセス状態及びチャンネル状態を収集してアッセンブルし、記録されたグローバルな状態を形成する。したがって、記録された意義のあるグローバルな状態を決定することができる。いずれのプロセスも、この決定方法を開始することができる。]
[0012] 参照文献［３］の方法は、分散型システムにわたる一貫した状態を記録するためのスナップショット方法とも称される。]
[0013] 上述したように、同期分散型システムにおいて過去の事象を監視するか又は非同期分散型システムにおいてグローバルな状態を検出するための方法が存在する。しかしながら、個々の処理要素のローカルクロックを同期させることが困難であるか、不可能であるか、計算上費用がかかり過ぎるか、又は望まれない場合に、分散型システムの個々の処理要素の将来のアクションを調整するための簡単な方法が望まれる。]
[0014] したがって、上述した目的を満足するか又は一部分満足する、複数の個々の処理要素のアクションを調整するための方法を提供することが望まれる。]
概要

[0015] このような方法は、請求項１により提供される。この方法の好適な実施形態は、従属請求項に記載されている。]
[0016] ２つの別の態様を含む本発明の方法は、例えば、分散型システムに使用されるコンピュータ処理ユニットのような処理ユニットを制御するように構成される。これは、クライアントユニットにより処理ユニットの各々へ複数のメッセージを含む少なくとも一つのメッセージストリームを送信するための第１の送信手順を含む。各メッセージは識別子を含み、その識別子は、順序付けされたグループのメンバーである。]
[0017] 本発明の方法の第１の態様では、複数のメッセージは、第１のメッセージが第２のメッセージの前に送信される場合に、第１のメッセージの識別子が第２のメッセージの識別子より小さくなる順序で送信される。本発明の方法の第２の態様では、メッセージは、第１のメッセージが第２のメッセージの前に送信される場合に、第１のメッセージの識別子が第２のメッセージの識別子より大きくなる順序で送信される。]
[0018] 双方の態様において、この方法は、アクションを実行するための要求を制御ユニットによって全ての処理ユニットへ送信するための第２の送信手順を更に含む。要求は、トリガーを含み、このトリガーは、順序付けされたグループのメンバーである。この方法は、更に、処理ユニットごとに、処理ユニットによりメッセージの少なくとも１つのストリームを受信するための第１の受信手順と、処理ユニットにより要求を受信するための第２の受信手順と、判定及び起動手順とを含む。]
[0019] 本発明の方法の第１の態様では、上記判定及び起動手順は、メッセージを受信する際に、メッセージの識別子がトリガー以上に大きいか否かを処理ユニットにより判定し、メッセージの識別子がトリガー以上に大きい場合には、処理ユニットによりアクションを起動するための判定及び起動手順である。本発明の方法の第２の態様では、前記判定及び起動手順は、メッセージを受信する際に、メッセージの識別子がトリガー以下に小さいか否かを処理ユニットにより判定し、メッセージの識別子がトリガー以下に小さい場合には、処理ユニットによりアクションを起動するための判定及び起動手順である。]
[0020] この方法は、処理ユニットによって実行されるアクションを調整することを目的とする。即ち、この方法は、分散型システムにおいて一連のアクションをいつ実行すべきかを調整することを目的とする。このため、本発明の方法は、特定のアクションをいつ実行すべきか決定するよう処理ユニットを支援する手段を提供する。]
[0021] 例えば、特定のアクションは、分散型製造システムにおける製造パラメータの変更、分散型記憶システムにおけるバックアップの実行、コンピュータユニットの遮断、（同時継続中の出願ＰＣＴ／ＥＰ２００７／０６０５４４号の意味の中で）分散型記憶システムにおけるバージョンの生成、記憶エンティティの状態の変更、例えば、読み取り／書き込みから読み取り専用への変更、或いはそれらアクションの組合せである（これらに限定されない）。]
[0022] この方法は、ローカルクロックの同期を必要とせずに、この調整を可能にする。アクションの調整は、時間的同期なしに処理ユニット間で行われる。絶対的な時間基準スケールはセットされない。むしろ、順序グループの各メンバーであるトリガーが、処理ユニットによりアクションを起動するための相対的な基準スケールを与える。]
[0023] この方法は、更に、処理を停止する必要なくこの調整を行えるようにする（調整プロセスは、処理と同時に実行される）。また、分散処理を妨げることなく分散型システムの処理ユニットにわたってアクションを実行することが可能である。]
[0024] これをどのように達成するかについて以下に詳細に説明する。以下の説明では、一例として、本発明の方法をより良く理解するために、順序付けされたグループは、整数のグループであると仮定する。また、良く理解するために、この説明は、本発明の方法の上述した第１の態様に本質的に限定される。しかしながら、当業者であれば、本発明の方法の第１及び第２の双方の態様について、説明を順序付けされたグループへと一般化することができよう。ここで、順序付けされたグループとは、変換不変量である部分順序“≦”（この記号“≦”は、“〜以下”の演算子である）が設けられたグループＧとして定義される。換言すれば、“≦”は、Ｇにおける全てのｘ、ｙ及びｚに対し、ｘ≦ｙの場合に、ｘｚ≦ｙｚであり且つｚｘ≦ｚｙである。]
[0025] ここで、整数である順序付けされたグループ、及び第１の態様に限定して、説明を開始する。この方法は、クライアントユニットにとって一意の整数、即ち、連続番号を使用する。クライアントユニットにより処理ユニットへ送信されるメッセージのストリームは、昇順の整数を含む。これは、第１のメッセージが第２のメッセージより前に送信される場合に第１のメッセージの識別子が第２のメッセージの識別子より小さくなる順序でメッセージが送信されると共に、整数が識別子として使用されるからである。即ち、複数のメッセージは、それらの識別子が昇順で送信される。]
[0026] 識別子、即ち、連続番号は、メッセージ識別番号として機能する。さらに、それらは、分散型システムの基準心拍を与え、処理ユニットによって実行されるべきアクションを調整するのに使用される。]
[0027] 制御ユニットは、アクションを実行するための要求を各処理ユニットへ送信する。要求されるアクションは、例えば、各処理ユニットに記憶される情報のバックアップを実行するか、又は、上述した他のオペレーション、例えば、バージョンの生成、を実行することであり得る。要求は、整数であるトリガーを含む。トリガーは、例えば、値“ｋ”の整数であり得る。アクションを実行するための要求を、値“ｋ”のトリガーと共に送信することにより、制御ユニットは、ｋ以上の識別子又は連続番号をもつメッセージをクライアントユニットから受信したときにアクションを実行するように、各処理ユニットに要求（命令）する。]
[0028] クライアントユニットは、メッセージの少なくとも１つのストリームを各処理ユニットへ送信する。メッセージは、例えば、処理ユニット内に分散態様で記憶されたデータエンティティのコンテンツの変更を含み得る。上述したように、各メッセージは更に、整数である識別子を含む。この識別子は、メッセージの連続番号を構成する。]
[0029] クライアントユニットから処理ユニットへのメッセージのストリームは、メッセージがそれらの各識別子の昇順に送信されるというものである。降順の使用も可能であり、この場合には、判定及び起動手順は、メッセージの識別子がトリガー以下であるかどうか判定し、メッセージの識別子がトリガー以下である場合に、アクションが起動される。整数に限定される場合には、増加順の使用は、第１の態様に対応し、減少順の使用は、第２の態様に対応する。上述したように、この説明は、ここでは、第１の態様に限定されている。当業者であれば、この説明を第２の態様へと一般化することができよう。]
[0030] さらに、クライアントユニットから処理ユニットへのメッセージの各ストリームは、そのストリームにおけるメッセージの順序が保持されるというものである。換言すれば、識別子、即ち連続番号ｎ（ｎは整数）をもつメッセージと、識別子ｎ＋ｉ（ｉは０より大きな整数）をもつメッセージとが、ストリームにおいて連続して送信され、即ち識別子ｎをもつメッセージが、識別子ｎ＋ｉをもつメッセージの前に送信される場合には、それらメッセージが処理ユニットによりこの順序で受信される。ストリームは、ＦＩＦＯ（先入れ先出し）順序である。]
[0031] ＦＩＦＯ順序のストリームは、メッセージが送信されるチャンネルがメッセージの順序を保存しない場合には、再順序付けメカニズムを通して実施することができる。]
[0032] 一実施形態では、クライアントユニットは、メッセージの２つ以上のストリームを同じ処理ユニットへ送信する。この実施形態では、受信したメッセージ、即ち複数のストリームから受信したメッセージは、処理ユニットが判定及び起動手順を実行する前に識別子により再順序付けされる。]
[0033] 各処理ユニットは、アクションを実行するための要求を受け取るように構成され、更に、メッセージのストリームを受け取るようにも構成される。アクションを実行するための要求を受け取ると、処理ユニットは、その要求からトリガーを取得し、当該トリガーを保持し、例えば、記憶する。ストリームにおけるメッセージを受信すると、処理ユニットは、メッセージに含まれている識別子がトリガー以上であるか否かを判定する。メッセージに含まれている識別子がトリガー以上である場合には、アクション（例えば、バックアップの生成、又はバージョンのリファレンシング）が実行される。アクションは、例えば、上述したように、（処理ユニットがデータ記憶ユニットである場合には）バックアップの生成であり、又はバージョンのリファレンシング、即ち記憶ユニットのある時点の状態を再生成するのに必要な情報を記録することである。]
[0034] 本発明の方法は、要求（即ち、アクションを実行するための要求）に関連したアクションの絶対的時間基準及び処理ユニットにわたるトリガーに対する同期を保証するものではない。]
[0035] その理由は、次の通りである。一方では、クライアントユニットから処理ユニットへのストリームは、遅延の保証を与えず、また、与える必要がない。他方では、保持されるトリガーをｎである場合に、メッセージを識別子ｎと共にクライアントユニットにより１つの処理ユニットへ送信することができる。処理ユニットは、次いで、識別子がトリガーに等しいので、アクションを起動し、即ちその実行を開始する。次いで、識別子ｎ＋ｉをもつメッセージがクライアントユニットにより別の処理ユニットへ送信された後に数秒（それ以上又は以下）が経過する。他の処理ユニットは、識別子ｎ＋ｉをもつメッセージを受信すると、識別子ｎ＋ｉが、保持されたトリガーｎより大きいか否かを判定し、次いで、アクションを起動する。その結果、第１の処理ユニットにより実行されるアクションと第２の処理ユニットにより実行されるアクションは、同時に実行されず、即ち絶対的時間基準又は共通基準クロックに対して同時に実行されない。しかしながら、アクションは、メッセージを送信する特定のクライアントユニットに関する限り、分散型システムの心拍として働くメッセージ識別子に対して調整される。]
[0036] 換言すれば、この方法は、クライアントユニットからメッセージが送信される順序に対して調整を行う。ある処理ユニットが他の処理ユニットに影響を及ぼさず、即ちその意味で処理ユニットが互いに独立していると仮定する。したがって、相対的な調整によって、処理ユニットのアクションをクライアントユニットの観点から有意義に調整する。]
[0037] さらに、次のような付加的な仮定がなされ得る。調整されたアクションは、一般的に、それらが起動、即ち実行される、又は起動及び実行されねばならない絶対的時間に危機的に依存してはならない。これを前提に、この方法は、コンセンサス（合意）発見手順と共に使用して、アクションを実行すべき時間フレームを制御することができる。アクションを実行すべき時間フレームを制御するための、又はより一般的には、アクションの起動及び実行に関連した１つ以上のパラメータを制御するための本発明の方法の一実施形態によるコンセンサス発見手順を以下に説明する。]
[0038] 一実施形態では、この方法は、例えば、指定の又は暗示された条件の下で処理ユニットがアクションの実行を合意するか否かを判定するためのコンセンサス発見手順を含む。この実施形態では、制御ユニットは、各処理ユニットにメッセージを送信して、それらがアクションの実行に合意するか否かを尋ねる。このメッセージを、ここでは、初期化メッセージと称する。]
[0039] この初期化メッセージに応答して、各処理ユニットは、それがアクションの実行に合意するか否かを制御ユニットに指示する。これを前提に、一実施形態では、指示がないときに、アクションの実行を承諾したと解釈する。処理ユニット又は処理ユニットの少なくとも一部分（例えば、それらの所定の割合）がアクションの実行に合意する場合に、制御ユニットは、合意確認を処理ユニットへ送信し、アクションを実行できることを通知する。合意確認は、上述したように、トリガーを含む、アクションを実行する要求を含み得る。或いは、トリガーを含む、アクションを実行する要求が初期化メッセージに含まれ得る。それ故、第２の送信手順は、判定及び起動手順が実行される前、したがって、調整されたアクションが実際に実行される前に、初期化部分及び合意確認部分（又は調整部分）の２つの部分に分割され得る。]
[0040] 本発明の方法の一実施形態のコンセンサス発見手順を以下に説明する。]
[0041] この実施形態によれば、この方法は、更に、各処理ユニットがアクションの実行を合意するか否かを要求するための初期化メッセージを、制御ユニットにより各処理ユニットへ送信するための初期化手順を含む。更に、この方法は、処理ユニットごとに、初期化メッセージを処理ユニットにより受信するための第３の受信手順と、初期化メッセージに関連したアクションの実行に処理ユニットが合意するか否かを処理ユニットにより判定するための合意判定手順と、を含む。判定及び起動手順は、処理ユニットの全て又は少なくとも一部分が初期化メッセージに関連したアクションの実行に合意することを制御ユニットが判定した場合に実行される。]
[0042] 制御ユニットは、処理ユニットの全て又は幾つか、或いは、例えば、その所定の割合が、調整されたアクションの実行に合意しないことを判定し得る。これは、指定の又は暗示された条件、即ち初期化メッセージに指定されるか又は処理ユニットにプログラムされた条件が満足されないことが処理ユニットの全て又は幾つかにより判定された場合に生じ得る。次いで、制御ユニットは、非合意確認メッセージを処理ユニットへ送信して、調整されたアクションを実行しないように命令し、また、任意であるが、初期化メッセージを破棄するように命令し得る。]
[0043] 一実施形態では、コンセンサス発見手順は、トリガーのネゴシエーションを含む。この実施形態では、例えば、制御ユニットは、トリガーを提案する初期化メッセージを処理ユニットへ送信する。次いで、処理ユニットは、条件が満足されるか否かを判定し得る。条件は、記憶スペース、処理リソース、応答性、状態安定性等の観点でアクションを実行するための利用可能性を含み得る。また、条件は、処理ユニットが、別のクライアントユニットによりロック又は予約されないこと、異常状態にないこと、等も含み得る。]
[0044] 一実施形態では、１つのクライアントユニットのみがメッセージのストリームを処理ユニットへ送信する。]
[0045] 別の実施形態では、複数のクライアントユニットがメッセージのストリームを処理ユニットへ送信する。この後者の実施形態では、アクションは、クライアントユニットごとに調整される。１つ以上のアクションの調整は、一度に１つのクライアントユニットに対して行われるか、又は順序付けされたグループが重畳しなければ、複数のクライアントユニット対して行われる。１つのクライアントユニット又は複数のクライアントユニットに対して同時に保留中のアクションが存在することがある。]
[0046] 一実施形態では、トリガーの受信を含む第２の受信手順が、処理ユニットにロックを発生する。これは、調整されたアクションを起動すべきときに、あるクライアントユニットのアクションが別のクライアントユニットのアクションにより妨げられないことを保証するために使用され得る。]
[0047] 一実施形態では、各々アクションを実行するための多数の要求が、制御ユニットにより処理ユニットへ送信される。この実施形態では、複数の対応するトリガーが処理ユニットに同時に保持される。判定及び起動手順は、メッセージを受信したときに、メッセージの識別子がいずれかのトリガー以上であるか否かを処理ユニットにより判定し、メッセージの識別子がいずれかのトリガー以上である場合には、満たすと検出されたトリガーに対応するアクション又は複数のアクションを処理ユニットにより起動するためのインストラクションを含む。]
[0048] 一実施形態では、処理ユニットが分散型記憶システムを形成し、各処理ユニットに対するアクションを起動することは、例えば、アクションを起動するときに、それらのコンテンツのバックアップを開始するか、バージョンを生成するか、記憶エンティティの状態を、例えば、読み取り／書き込みから読み取り専用へ変更するか、或いはそれらの組合せを含む（これらに限定されない）。この実施形態は、例えば、中央の、より安定した、より正確なクロックを参照して各処理ユニットのローカルクロックを調整することを含む複雑な同期手順を必要とせずに、分散型データ記憶装置においてバックアップを実行することを可能とする。]
[0049] 一実施形態では、アクションは、アクションが起動されるときに処理ユニットの状態に関するメッセージを送信することを含み、メッセージは、トリガーを含む。これにより、中央受信ユニットが、クライアントユニットから処理ユニットへ送信されるメッセージの順序に対して一貫した方法で、受信したメッセージを比較し分析することが可能となる。この実施形態は、絶対的な時間基準又は中央クロックを参照して処理ユニットのローカルクロックの時間を同期させることを必要としない。当業者であれば、この実施形態の状況、より一般的には、本発明の状況における「状態(state)」という語は、絶対的な時間基準に対するシステムの同期特性を意味しないことが理解されよう。]
[0050] 一実施形態では、第２の受信手順（処理ユニットにより要求を受け取るための）、及び受信したトリガーを記憶するための記憶手順は、いずれかの対応するアクションを起動する前に２つ以上のトリガーを受け取って記憶することができる。この実施形態は、複数の処理ユニットの複数のアクションを簡単な方法で調整することができる。]
[0051] 処理ユニットは、例えば、移動ユニット、ワイヤレスユニット、ワイヤードユニット、組立ライン作業における製造ユニット、センサ、データストリームのソース、又は分散型システム内のデータ記憶ユニットであってもよい。]
[0052] 本発明の方法は、分散型システムにおいてタスクの各部分を実行する処理ユニットのローカルクロックの同期を必要とせずに、コンピュータ装置のアクションを調整するために、コンピュータ環境に適用することができる。また、本発明の方法は、処理ユニットに記憶されたデータのバックアップの生成、又は分散型記憶システムにおける新規バージョンの生成を調整又は編成するために、データ記憶環境にも適用することができる。また、本発明の方法は、次々の製造品目の製造パラメータを制御するために、製造環境にも適用することができる。]
[0053] 一実施形態では、アクションを実行するための要求がタイムアウトを含む。処理ユニットは、アクションを実行するための要求をタイムアウトと共に受け取る。タイムアウトが満了となる前に、要求に含まれているトリガー以上の識別子をもつメッセージを処理ユニットが受信しない場合には、保持されたトリガーが破棄される。従って、判定及び起動手順は、アクションを起動せずに完了となる。この実施形態により、異常状態の場合に、特定のトリガーの時間にアプリケーションを制限することが可能となる。]
[0054] また、本発明は、処理ユニットを制御するように構成されたシステム、並びに、このようなシステムに使用するよう構成された処理ユニット及び制御ユニットにも関するものであり、これらは、対応する独立請求項に規定されている。システム、処理ユニット及び制御ユニットの好適な実施形態は、従属請求項に記載されている。]
[0055] 以下、添付図面を参照して、本発明の実施形態を詳細に説明する。]
図面の簡単な説明

[0056] 本発明による方法の一実施形態の概略的構成を示す図である。
調整プロセスを実際に実行する前に初期化プロセスを含む本発明の方法の別の実施形態の概略的構成を示す図である。
調整プロセスを実際に実行する前に初期化プロセスを含む本発明の方法の別の実施形態の概略的構成を示す図である。
実際の用語で本発明を説明するための本発明の例を示す図である。
実際の用語で本発明を説明するための本発明の例を示す図である。
実際の用語で本発明を説明するための本発明の例を示す図である。
実際の用語で本発明を説明するための本発明の例を示す図である。
本発明の方法の一実施形態の初期化プロセスのフローチャートである。
本発明の実施形態によるクライアントユニットを概略的に示す図である。
本発明の実施形態によるクライアントユニットを概略的に示す図である。
本発明の実施形態による制御ユニットを概略的に示す図である。
本発明の実施形態による制御ユニットを概略的に示す図である。
本発明の実施形態による処理ユニットを概略的に示す図である。
本発明の実施形態による処理ユニットを概略的に示す図である。]
詳細な説明

[0057] 以下、特定の実施形態を参照して本発明を詳細に説明する。これらの特定の実施形態は、当業者に良好な理解を与えるが、特許請求の範囲によって規定される本発明の範囲を何ら限定するものではない。特に、以下の説明全体にわたって独立して述べる実施形態は、相互に排他的とならない羽仁で、更に別の実施形態を形成するように組み合わせることができる。]
[0058] 図１は、本発明による方法の一実施形態の概略的構成を示している。クライアントユニット１４は、複数のメッセージ２を含むストリーム４を２つの処理ユニット１０へ送信する。図示した構成では、メッセージ２の厳密に１つのストリーム４がクライアントユニット１４から処理ユニット１０の各々へ発生される。] 図１
[0059] 図示しないが、３つ以上の処理ユニット１０が存在し得る。また、複数のメッセージ２を含む２つ以上のストリーム４がクライアントユニット１４から処理ユニット１０の各々に発生されることもある（いずれも図示せず）。この場合（メッセージ２の２つ以上のストリーム４がクライアントユニット１４から処理ユニット１０の各々に発生される）、メッセージ２が判定及び起動手順において処理ユニット１０により処理される順序が、クライアントユニット１４からメッセージ２が送信される順序に対応するよう保証するために、再順序付けメカニズムが提供され得る。]
[0060] クライアントユニット１４によって送信されるメッセージ２の各々は、識別子、即ち、連続番号を含む。識別子は、例えば、メッセージ２のヘッダの所定のフィールドに含まれ得る。この識別子は、ここに示す実施形態では、整数である。メッセージ２は、増加する（昇順の）識別子と共にストリーム４において送信される。]
[0061] 例示的シナリオについて以下に説明する。クライアントユニット１４は、最初、値“ｋ”の識別子をもつメッセージ２を第１の処理ユニット１０（図１の左下）へ送信する。ここで、“ｋ”は整数である。次いで、クライアントユニット１４は、第２のメッセージ２を第１の処理ユニット１０へ送信する。この第２のメッセージ２は、値“ｋ＋１”の識別子を含む。次いで、クライアントユニット１４は、値“ｋ＋２”の識別子をもつメッセージ２を第２の処理ユニット１０（図１の右下）へ送信する。次いで、クライアントユニット１４は、値“ｋ＋３”の識別子を各々もつ２つのメッセージ２を第１の処理ユニット１０及び第２の処理ユニット１０の双方へ実質的に同時に送信する。次いで、クライアントユニット１４は、値“ｋ＋４”の識別子をもつメッセージ２を第１の処理ユニット１０へ送信し、等々となる。] 図１
[0062] 図１のストリーム４に隣接する矢印は、クライアントユニット１４から処理ユニット１０へのメッセージ２の送信方向を示す。ストリーム４は、先入れ先出し（ＦＩＦＯ）順序であるのに加えて、一方向性である。] 図１
[0063] 一実施形態では、メッセージ２は、ストリーム４のソースとして働くクライアントユニット１４により、この場合にはデータ記憶ユニットである処理ユニット１０に分散的に記憶されたデータエンティティに対してなされた変更に関する情報を含む。しかしながら、当業者であれば、これは、一実施形態に過ぎないことが理解されよう。処理ユニット１０は、データ記憶ユニット以外の処理ユニット１０であってもよい。]
[0064] 制御ユニット１２は、アクションを実行する要求６を各処理ユニット１０へ送信するように構成されている。全体的な目的は、処理ユニット１０により、調整された方法でアクションを実行することである。アクションを実行するためのこの要求６は、トリガーを含む。トリガーは、例えば、メッセージ２のヘッダの所定フィールドに含まれ得る。トリガーは、本実施形態では、整数である。]
[0065] 各処理ユニット１０は、制御ユニット１２により送信されるトリガーを保持する。従って、処理ユニット１０は、クライアントユニット１４からストリーム４のメッセージ２を受け取ると、メッセージ２に含まれている識別子が保持したトリガー以上であるか否かを判定する。メッセージ２に含まれている識別子が保持したトリガー以上である場合には、処理ユニット１０は、アクションを起動する。アクションを起動し実行するための命令は、処理ユニット１０に記憶されるか、又は制御ユニット１２から送信される要求６においてトリガーと共に送信され得る。]
[0066] 任意であるが、処理ユニット１０は、アクションが起動された後にトリガーを破棄してもよい。これにより、アクションのその後の起動が望まれない場合に、これを回避することができる。]
[0067] クライアントユニット１４は、ポータブルコンピュータ（図示されたような）、ワークステーション、サーバー、又はストリーム４の他のソースであってもよい。クライアントユニット１４は、自動的に動作してもよく、又は、ユーザインターフェイスを介して人間により作動されてもよい。プロセスは、ユーザにとって透過的であってもよい。即ち、ストリーム４、メッセージ２、処理ユニット１０、制御ユニット１２、等は、クライアントユニット１４にアクセスするユーザ又はコンピュータシステムにより一般的には存在しないものとして認識され得る。クライアントユニット１４の外観、機能、及び振舞いは、ストリーム４、メッセージ２、処理ユニット１０、制御ユニット１２、等の物理的な存在が、クライアントユニット１４にアクセスするユーザ又はコンピュータシステムにより一般的に認知されないようなものである。]
[0068] ストリーム４は、メッセージ２の順序が保存されるならば、いかなるネットワークプロトコルで実施されてもよく、インターネットのようなネットワークを介して渡されてもよく、又は、多数の処理要素を有するコンピュータ内でメッセージ２が単に送信されるものであってもよい。ストリーム４がコンピュータ内で送信されるだけである場合には、クライアントユニット１４は、ユーザインターフェイスであり、処理ユニット１０は、分散型記憶システムのような分散型システムに使用される個々のコンポーネントとして構成され得る。]
[0069] 制御ユニット１２は、クライアントユニット１４により実行されるコンピュータ実施アプリケーションのフレームワーク内で適切なアクションを適切に開始するためにクライアントユニット１４と通信する。一実施形態では、制御ユニット１２及びクライアントユニット１４は、単一のユニットを形成する。]
[0070] この方法は、ストリーム４の待ち時間により影響されない。換言すれば、この方法は、ストリーム４におけるメッセージ２の送信遅延により影響されない。従って、ストリーム送信に対して遅延を保証する必要はない。]
[0071] 本発明の方法及びシステムの一実施形態では、当該方法及びシステムが、パケットロス又はパケット破壊に対抗できるようにするために、回復メカニズム又は欠陥許容メカニズムが設けられる。これは、本発明の幾つかの適用分野における要件を緩和する。当業者であれば、例えば、ＡＣＫ（確認）信号を送信するよう構成されたパケット確認技術を使用してこれを実行できることが分かるであろう。]
[0072] 図２ａ及び２ｂは、本発明の方法の一実施形態の概略的な構成を示している。この実施形態では、調整されたアクションを実行すべきか否かのコンセンサスを検出するプロセスを示す。図２ａは、調整されたアクションを起動して実行する準備ができた状態に到達する前の、コンセンサス発見、ネゴシエーション、又は合意判定を示している。図２ｂは、トリガーがネゴシエートされた後の調整されたアクションの実行の概略的構成を示している。] 図２ａ 図２ｂ
[0073] 先ず、図２ａを参照する。制御ユニット１２は、初期化メッセージ８を処理ユニット１０へ送信することによって調整プロセスを初期化する。より詳細には、２つの初期化メッセージ８が、各処理ユニット１０へ、１つずつ、送信される。初期化メッセージ８を受け取ると、各処理ユニット１０は、任意であるが初期化メッセージ８に述べられた条件を満足するか否かをテストすることにより、初期化メッセージ８に関連したアクションを実行できるか否かを判定する。] 図２ａ
[0074] 処理ユニット１０は、アクションを実行できる状態にある場合には、初期化メッセージ８に対する応答である合意メッセージを制御ユニット１２へ返送する（処理ユニット１０から発して制御ユニット１２へ至る矢印）。]
[0075] 対照的に、処理ユニット１０は、調整要求を満足できない場合には、非合意応答を制御ユニット１２へ送信する。これは、例えば、処理ユニット１０が異常状態にあるか、或いは処理ユニットがロック又は予約されているか、想定されるアクションを実行するのに充分なメモリスペースがない、等々の場合に、衝突する既存のトリガーが別のクライアントユニット１４（図示せず）に関して保留となっているために生じ得る。]
[0076] 処理ユニット１０から受け取られる応答に基づき、制御ユニット１２は、処理ユニット１０により実行されるべきアクションを実際に要求すべきか否かを判断する。全ての処理ユニット１０が、制御ユニット１２に、想定されるアクションを実行できる旨を応答した場合に、制御ユニット１２は、アクションを実行するための要求を送信するか、又はアクションを起動するように準備しなければならないこと、即ち判定及び起動手順を開始しなければならないことを示す確認メッセージを送信する。幾つかの処理ユニット１０しか、アクションを実行するための調整されたプロセスの開始に合意しなかったことを制御ユニット１２が判定した場合には、制御ユニット１２は、合意した処理ユニット１０の数が、クライアントユニット１４により実行されるアプリケーションの状況において充分であるか否かを判定する。充分である場合には、制御ユニット１２は、アクションを有効に実行されるべきであるという確認メッセージを送信する。充分でない場合には、制御ユニット１２は、処理ユニット１０へ非合意メッセージを送信して、調整されたアクションを実行すべきでないことを処理ユニット１０に指示する。]
[0077] 一実施形態では、非応答の処理ユニット１０は、非合意処理ユニット１０として処理される。即ち、処理ユニット１０は、非応答の処理ユニット１０を、それが非合意メッセージを送信したかのように取り扱う。]
[0078] 調整を開始するとき、即ち調整されたアクションを実行すべきか否かのコンセンサスを検出するプロセス内で、制御ユニット１２は、クライアントユニット１４と情報を交換し得る。情報は、例えば、その下でアクションを実行すべき動作条件（入力）、又はアクションの調整を実行できるか否か（出力）に関するものであり得る。クライアントユニット１４は、その内部処理を、上述した交換に基づいて適応させ得る。]
[0079] 制御ユニット１２は、調整されたアクションを実行すべきでないと決定すると、しばらくして、新たな初期化メッセージ８を送信して、調整されたアクションの初期化を再びネゴシエーションするように試み得る。]
[0080] 図２ｂは、クライアントユニット１４から処理ユニット１０へのメッセージ２の流れ、及び受信ユニット１６へのメッセージ１８の流れを示している。受信ユニット１６は、アクションを起動した結果として処理ユニット１０から生じるメッセージ１８を収集し分析する役割を果たす。一実施形態では、このような受信ユニット１６は存在しない。] 図２ｂ
[0081] トリガーが各処理ユニット１０に保持される場合、処理ユニット１０が、クライアントユニット１４から発生するストリーム４におけるメッセージ２を、トリガー以上の識別子と共に受け取ると、メッセージ１８が受信ユニット１６へ送信される。処理ユニット１０から受信ユニット１６へ送信されるメッセージ１８は、トリガーを含むことが好適である。これにより、クライアントユニット１４からのメッセージ２の一連の送信に関してメッセージ１８のコンテンツの一貫した処置が可能となる。]
[0082] 一実施形態では、クライアントユニット１４から発生するメッセージ２は、処理ユニット１０に分散的に記憶されたデータユニットに対してなされる変更に関する情報を含む。特定のメッセージ２が、処理ユニット１０に保持されたトリガー以上の識別子を含む場合には、処理ユニット１０は、当該処理ユニット１０に含まれている情報のバックアップを開始する。次いで、バックアップが検出され得る位置及びトリガーを含むか、又はバックアップが実行されたことの確認及びトリガーを含むメッセージ１８を受信ユニット１６へ送信する。]
[0083] 図３ａ及び３ｂは、本発明の方法の一実施形態においてアクションを起動するメカニズムを示すテーブルの一例を示している。クライアントユニット１４は、値“１”から“８”の識別子を昇順でもつ８個のメッセージ２を送信するものと仮定する。さらに、第１の処理ユニット１０（図３ａ及び３ｂの“第１の処理ユニット”）及び第２の処理ユニット１０（図３ａ及び３ｂの“第２の処理ユニット”）は、値“３”のトリガーに対応するアクションを実行するように制御ユニット１２により命令されているものと仮定する。さらに、クライアントユニット１４は、値“１”、“２”及び“３”の識別子を各々もつ３つの連続するメッセージ２を第１の処理ユニット１０へ送信するものと仮定する。次いで、クライアントユニット１４は、値“４”の識別子をもつメッセージ２を第２の処理ユニット１０へ送信し、次いで、値“５”の識別子をもつメッセージ２を第１の処理ユニット１０へ送信し、等々となる。] 図３ａ
[0084] トリガーは、上述したように、値“３”の整数であるから、第１の処理ユニット１０は、値“３”の識別子をもつメッセージ２を受け取ると、アクションを開始する。というのは、その識別子がトリガーに等しいからである。対照的に、第２の処理ユニット１０は、値“４”の識別子をもつメッセージ２を受け取ると、アクションを開始する。というのは、それが、値“３”のトリガー以上の識別子をもつ、第２の処理ユニット１０により受け取られる第１のメッセージ２だからである。]
[0085] 図３ａのテーブルの右側に示されたアスタリスクは、トリガーが値“３”の整数であることを示している。図３ａのテーブルの行は、メッセージのクライアント送信シーケンスを表しているが、図３ｂは、クライアントユニット１４から第１及び第２の両処理ユニット１０へのメッセージ２の例示の受信順序を絶対時間で（即ち、共通の基準クロックを参照して）示している。図３ｂに示すように、値“４”の識別子をもつメッセージ２の前に値“３”の識別子をもつメッセージ２がクライアントユニット１４によって送信されたが、絶対時間では、値“４”の識別子をもつメッセージ２が第２の処理ユニット１０により受信された後に値“３”の識別子をもつメッセージ２が第１の処理ユニット１０により受信される。これは、クライアントユニット１４から第１の処理ユニット１０へ発生されるストリーム４が、クライアントユニット１４から第２の処理ユニット１０へ発生されるストリーム４より大きな待ち時間を受けたからである。] 図３ａ 図３ｂ
[0086] 上述したように、値“３”の識別子をもつメッセージ２を受信した後に第１の処理ユニット１０においてアクションが起動される。これは、この識別子が、値“３”のトリガーに等しいからである。第２の処理ユニット１０では、値“４”の識別子をもつメッセージ２を受信した際にアクションが起動される。これは、この識別子が、値“３”のトリガーより大きいからである。図３ｂのテーブルの右側に示す２つのアスタリスクは、この例では、絶対時間で、アクションが、各々、第２の処理ユニット１０（テーブルの第２行に隣接するアスタリスク）及び第１の処理ユニット１０（テーブルの第５行に隣接するアスタリスク）において起動されるときを示している。絶対時間では、第１の処理ユニット１０においてアクションが起動される前に、第２の処理ユニット１０においてアクションが起動される。しかしながら、クライアントユニット１４の観点から、絶対時間で厳密に処理ユニット１０においていつアクションがトリガーされるかは問題でない。問題は、アクションが、クライアントユニット１４から送信されるメッセージ２の識別子（又は連続番号）に関して調整された態様で起動されることである。識別子に関するこの調整は、本発明の方法により保証され、従って、例えば、分散型データエンティティに対してなされた変更に対応するクライアントユニットの送信シーケンスに関して一貫性を与える。] 図３ｂ
[0087] 図３ｂの２つのアスタリスクは、第１及び第２の処理ユニット１０における調整されたアクションが異なる絶対時間において実行されることを示し、一方、図３ａに示す１つのアスタリスクは、クライアントユニットの観点から（即ち、クライアントユニットの送信シーケンスに関して）、アクションが処理ユニット１０により調整された態様で実行されることを示している。第２の処理ユニット１０は、値“３”の識別子をもつメッセージ２を受信しないので、その状態は変化せず、それ故、値“４”の識別子をもつメッセージ２を受信するときにアクションを実行することは、値“３”の識別子をもつメッセージ２の、第２の処理ユニット１０による仮説的な受信（即ち、実行されない）に対応する状態と一貫している。] 図３ａ 図３ｂ
[0088] 図４ａ及び４ｂは、２つの同時トリガーを伴う別の例を示している。第１のトリガーは、値“３”を有し、一方、第２のトリガーは、値“５”を有する。アクションはそれぞれ、これらトリガーの１つに対応する。第１のアクションは、値“３”のトリガーを受信した際に起動され、第２のアクションは、値“５”のトリガーを受信した際に起動される。] 図４ａ
[0089] クライアントユニットの観点からの（即ち、クライアントユニットの送信シーケンスを参照した）アクションの起動順序を図４ａに示す。値“３”の第１のトリガーが満足されたときの状態を、テーブルに隣接する１つのアスタリスクにより示している。値“５”の第２のトリガーが満足されたときの状態を、テーブルに隣接する二重アスタリスクにより示している。] 図４ａ
[0090] 絶対時間で、第１の処理ユニット１０によるアクションの起動前に、値“３”の第１のトリガーに対応するアクションが、第２の処理ユニット１０により起動される。同様に、第１の処理ユニット１０によるアクションの起動前に、値“５”のトリガーに対応するアクションが、第２の処理ユニット１０により起動される。絶対時間で、値“３”のトリガーに対応するアクションが第１の処理ユニット１０により実行される前に、値“５”のトリガーに対応するアクションが第２の処理ユニット１０により実行されることは、問題でない。問題は、絶対時間基準（利用できないと仮定する）ではなく、クライアント送信シーケンスに対して調整することである。]
[0091] 図２ｂに戻ると、識別子が２つのクラスのメッセージにおいて使用されていることが明らかである。識別子は、クライアントユニット１４から処理ユニット１０へ発生するメッセージ２に使用されねばならない。また、識別子は、（アクションを起動するときに）処理ユニット１０から受信ユニット１６へ発生するメッセージ１８に使用され得る。] 図２ｂ
[0092] 任意であるが、処理ユニット１０は、単にアクションが起動されるときより多くのメッセージ１８を受信ユニット１６へ送信してもよい。例えば、アクションの起動時にメッセージ１８を送信した後に、処理ユニット１０は、処理ユニット１０の内部クロックに対して規則的な間隔でその後のメッセージ１８を送信してもよく、処理ユニット１０から受信ユニット１６へ送信されるその後のメッセージ１８ごとに識別子の値が増分され得る。]
[0093] 第３のクラスのメッセージは、調整プロセスの初期化手順に使用されるもので、制御ユニット１２から処理ユニット１０へ送信されるメッセージ８、及び処理ユニット１０から制御ユニット１２へ送信されるメッセージ（図示せず）である。]
[0094] どのクラスのメッセージも、満了値を含んでいてもよい。満了値をむかえた後に、システムのいずれかのユニットによってメッセージが破棄され得る。]
[0095] 図５は、本発明の一実施形態により処理ユニット１０及び受信ユニット１６の間で調整をネゴシエートするための初期化手順を示すフローチャートである。] 図５
[0096] 制御ユニット１２は、調整プロセスを開始する（Ｓ２１）。このため、初期化メッセージ８が、処理ユニット１０へ、また、任意であるが、受信ユニット１６へ送信される（Ｓ２２ａ）。次いで、処理ユニット１０は、ローカルで即ち処理ユニット１０内で、想定される調整を受諾できるか否かを判定し（Ｓ２２ｂ）、また、任意であるが、受信ユニット１６は、ローカルで即ち受信ユニット１６内で、想定される調整を受諾できるか否かを判定する（Ｓ２２ｃ）。これらの手順（図５に「ローカル受諾」手順と示されている）は、初期化メッセージ８において指定された幾つかの条件が満足されるか否かをテストすることを含み得る。次いで、処理ユニット１０及び受信ユニット１６は、それらが想定される調整を受諾できるか否かを指示するための応答を制御ユニット１２へ送信することにより判定の結果を表す。] 図５
[0097] 次いで、制御ユニット１２は、調整を実行するための合意があるか否かを判定する（Ｓ２３）。合意がある場合には、制御ユニット１２は、調整を実行すべきであるという確認を処理ユニット１０及び受信ユニット１６へ送信する（Ｓ２４）。その多の場合、即ち、合意がない場合には、制御ユニット１２は、例えば、調整を実行すべきであることを指示するために処理ユニット１０及び受信ユニット１６へ破棄メッセージ（図示せず）を送信することにより、処理ユニット１０及び受信ユニット１６に通知することができる。]
[0098] 図６ａに概略的に示すクライアントユニット１４、図７ａに概略的に示す制御ユニット１２、及び図８ａに１つを概略的に示す処理ユニット１０は、本発明によるシステムの一実施形態を示すものである。これらの図面を参照して、このシステムを以下に詳細に説明する。] 図６ａ 図７ａ 図８ａ
[0099] システムは、処理ユニット１０を制御するために構成されている。システムは、複数の処理ユニット１０（図８ａ）を備えている。システムは、更に、メッセージ２を含む少なくとも１つのストリーム４を各処理ユニット１０へ送信する（第１の送信ユニット１４２から始まる矢印で示す）ように構成された第１の送信ユニット１４２を含むクライアントユニット１４（図６ａ）を備えている。各メッセージ２は識別子を含み、識別子は順序付けされたグループのメンバーであり、メッセージ２は、第１のメッセージ２が第２のメッセージ２の前に送信される場合に、第１のメッセージ２の識別子が第２のメッセージ２の識別子より小さくなるか、或いは第１のメッセージ２の識別子が第２のメッセージ２の識別子より大きくなる、という順序で送信される。] 図６ａ 図８ａ
[0100] このシステムは、更に、アクションを実行するための要求６を全ての処理ユニット１０へ送信する（第２の送信ユニット１２２から始まる矢印で示す）ように構成された第２の送信ユニット１２２を含む制御ユニット１２（図７ａ）を備えている。要求６はトリガーを含み、トリガーは、順序付けされたグループのメンバーである。] 図７ａ
[0101] 各処理ユニット１０（図８ａ）は、メッセージ２を含む少なくとも１つのストリーム４を受け取る（第１の受信ユニット１０２へ通じる矢印で示す）ように構成された第１の受信ユニット１０２を備えている。各処理ユニット１０は、更に、要求６を受け取る（第１の受信ユニット１０４へ通じる矢印で示す）ように構成された第２の受信ユニット１０４を備えている。最後に、各処理ユニット１０は、更に、メッセージ２を受信するときに（第１の受信ユニット１０２へ通じる矢印で示す）、メッセージ２の識別子がトリガー以上であるか否かを判定し、メッセージ２の識別子がトリガー以上である場合には、アクションを起動するか、或いは、メッセージ２を受信するときに、メッセージ２の識別子がトリガー以下であるか否かを判定し、メッセージ２の識別子がトリガー以下である場合に、アクションを起動するように構成された判定及び起動ユニット１０６を備えている。] 図８ａ
[0102] 図６ｂは、入力及び出力（Ｉ／Ｏ）ユニット１４４が更に設けられたクライアントユニット１４の一実施形態を示している。入力及び出力（Ｉ／Ｏ）ユニット１４４は、コンピュータプロセス又は人間と対話する（第１の受信ユニット１０４から始まりそこへ通じる二重矢印により示す）ために使用される。後者のケースでは、入力及び出力（Ｉ／Ｏ）１４４は、キーボード、コンピュータスクリーン、マウス、等のユーザインターフェイスである。クライアントユニット１４は、コンピュータ処理ユニット（ＣＰＵ）及びメモリユニット（ランダムアクセスメモリＲＡＭ、等）を備え、これらは、図示されていない。] 図６ｂ
[0103] 図７ｂは、初期化ユニット１２４が更に設けられた制御ユニット１２の一実施形態を示している。初期化ユニット１２４は、上述したように、各処理ユニット１０がアクションの実行に合意するか否かを要求するための初期化メッセージ８を各処理ユニット１０へ送信する（初期化ユニット１２４から始まる矢印で示す）ように構成されている。] 図７ｂ
[0104] 図８ｂは、第３の受信ユニット１０８及び合意判定ユニット１１０が更に設けられた処理ユニット１０の一実施形態を示している。第３の受信ユニット１０８は、上述したように、初期化メッセージ８を受信する（第３の受信ユニット１０８から延びる矢印で示す）ように構成されている。合意判定ユニット１１０は、（第３の受信ユニット１０８から始まり且つ合意判定ユニット１１０へ通じる矢印で示すように、とりわけ、初期化メッセージ８を使用して）処理ユニット１０が初期化メッセージ８に関連したアクションの実行に合意するか否かを判定する。] 図８ｂ
[0105] 一実施形態では、本発明の方法及びシステムは、分割統治方式（Divide and conquer algorithm（２００７年１１月２５日）を参照されたい。ウキペディア、ザ・フリー・エンサイクロペディアにおいて、http://en.wikipedia.org/w/index.php?title=Divide and conqueralgorithm&oldid=173796198から２００７年１２月３日１０：１２に検索）に適用され、例えば、反復的に実施される。大きな分散型コンピュータシステムにおいて調整された態様でアクションを実行すべき場合には、この方法を分割統治的に分割することにより、調整されたアクションの実行のスピードアップが得られて、性能を改善することができる。]
[0106] アクションを実行するための要求を制御ユニット１２により送信し、合意又は非合意応答を収集するタスクは、（制御ユニット１２の機能、及び、おそらくは処理ユニット１０の機能も実施する）ノードのサブセットへ反復的に委譲される。したがって、ネットワークにわたる（メッセージの量、ひいては、全ネットワークを通して送信されるデータの量により測定される）通信オーバーヘッドが減少され得る。本発明のこの実施形態を実行するときにノードのサブセットを個々に調整することにより、調整要求を並列化することで、待機時間量を短縮が減少され得る。この実施形態による方法を反復的に適用又は使用する他のオプションを実施することもできる。]
[0107] これは、規範的な交通信号管理システムにより説明することができる。このようなシステムにおいて、各個々の交通信号内で実行されるソフトウェア或いはそこに記憶されたパラメータ又はパラメータのセットを更新することより成るアクションを、調整された態様で実行することが必要とされる。２つの都市の各々が２つのノードで接続され、一方、都市自体の中のノードが各々少なくとも４つのノードで強く接続される。実行すべき調整されたアクションに対して、アクションを実行するための要求が都市ノード「フランクフルト」により送信される。都市ノード「フランクフルト」は、その要求を都市ノード「ダルムシュタッド」及び「カッセル」へ送信し、一方、都市ノード「ダルムシュタッド」は、その要求を都市ノード「コブレンツ」及び「フライブルグ」へ送信し、等々となる。先ず、各都市ノードを独立して調整し、次いで、予備的結果（合意又は非合意）を２つの隣接都市ノードへ送信することにより、アクションが調整される。換言すれば、ツリーのノードが各々調整されたシステムであるツリー構造が構築される。]
[0108] 本発明の方法は、調整を達成するために全システムのうちの影響のあるコンポーネント及び記憶エンティティ、即ち処理ユニット１０での入力／出力（Ｉ／Ｏ）処理に割り込む必要がないという効果を有する。処理ユニット１０での入力／出力（Ｉ／Ｏ）処理に割り込むことは、制御の観点から更なる問題を誘発することがある。例えば、調整を実行する間にタイムアウトから生じる誤った入力／出力（Ｉ／Ｏ）タイムアウト、等を取り扱うための付加的な処理能力を設けることが必要となることがある。]
[0109] ここでは、「ユニット」という語を使用したが（例えば、「クライアントユニット」「処理ユニット」「制御ユニット」又は「受信ユニット」）、ユニットの構成要素をどのように分散させるかに関して制約はない。即ち、ユニットの構成要素は、意図された機能をもたらすための異なるソフトウェア又はハードウェアコンポーネント又は装置に分散させることができる。更に、幾つかのユニットは、それらの機能を合成された単一のユニットにより実行するために統合することができる。例えば、制御ユニット１２及び受信ユニット１６は、それらの意図された機能を合成した態様で与えるように統合することができる。同様に、ユニットの他の合成も考えられ、例えば、クライアントユニット１４及び制御ユニット１２の合成、クライアントユニット１４、制御ユニット１２及び受信ユニット１６の合成、或いは制御ユニット１２及び１つの特定の処理ユニット１０の合成も考えられる。]
[0110] 以上のことから、「システム」という語は、ここでは、全体が一体化された相互作用、協働、又は相互依存性の技術的ユニット又はエンティティのセットとして広く理解されるべきである。]
[0111] 以上、本発明を詳細に説明したが、詳細な例は、当業者に良好な理解を与えるものに過ぎず、本発明の範囲を限定するものではない。本発明の範囲は、特許請求の範囲に規定される。]

权利要求:

請求項1
処理ユニット（１０）を制御する方法であって、クライアントユニット（１４）により、複数のメッセージ（２）を含む少なくとも１つのストリーム（４）を各処理ユニット（１０）へ送信するための第１の送信手順であり、各メッセージ（２）は、識別子を含み、前記識別子は、順序付けされたグループのメンバーであり、前記複数のメッセージ（２）は、第１のメッセージ（２）が第２のメッセージ（２）の前に送信される場合に、該第１のメッセージ（２）の識別子が該第２のメッセージ(２)の識別子より小さくなるか、又は、該第１のメッセージ（２）の識別子が該第２のメッセージ（２）の識別子より大きくなるような順序で送信される、該第１の送信手順と、制御ユニット（１２）により、アクションを実行する要求（６）を全ての処理ユニット（１０）へ送信するための第２の送信手順であり、前記要求（６）は、トリガーを含み、前記トリガーは、順序付けされたグループのメンバーである、該第２の送信手順と、を含み、更に、前記処理ユニット（１０）の各々に対して、該処理ユニット(１０)によりメッセージ（２）を含む前記少なくとも１つのストリーム（４）を受信するための第１の受信手順と、前記処理ユニット（１０）により前記要求（６）を受信するための第２の受信手順と、メッセージ（２）を受信した際に、メッセージ（２）の識別子が前記トリガー以上であるか否かを前記処理ユニット(10)により判定し、メッセージ（２）の識別子が前記トリガー以上である場合に、前記処理ユニット（１０）によりアクションを起動するか、或いはメッセージ（２）を受信した際に、メッセージ（２）の識別子が前記トリガー以下であるか否かを前記処理ユニット(10)により判定し、メッセージ（２）の識別子が前記トリガー以下である場合に、前記処理ユニット（１０）によりアクションを起動するための判定及び起動手順と、を含む、方法。
請求項2
前記順序付けされたグループは、整数のセットであり、前記第１の送信手順において、前記複数のメッセージは、それらの識別子の昇順で送信されるか、又は、前記複数のメッセージは、それらの識別子の降順で送信される、請求項１に記載の方法。
請求項3
前記処理ユニット（１０）は、分散型記憶システムを形成し、各処理ユニット（１０）においてアクションを起動することは、そのコンテンツのバックアップを開始すること、バージョンを生成すること、記憶エンティティの状態を、例えば、読み取り／書き込みから読み取り専用へ切り換えること、上述したオペレーションの組合せ、のうちのいずれか１つを含む、請求項１又は２に記載の方法。
請求項4
前記起動することは、前記アクションが起動されるときの前記処理ユニット（１０）の状態に関するメッセージ（１８）を送信することを含み、前記メッセージ（１８）は、トリガーを含む、請求項１〜３の何れか一項に記載の方法。
請求項5
前記要求（６）に含まれている前記トリガーを前記処理ユニット（１０）によって記憶するための記憶手順を更に備え、前記第２の受信手順及び記憶手順は、いずれかの対応するアクションを起動する前に２つ以上のトリガーを受け取って記憶することができる、請求項１〜４の何れか一項に記載の方法。
請求項6
各処理ユニット（１０）がアクションの実行に合意するか否かを要求する初期化メッセージ（８）を前記制御ユニット（１２）により各処理ユニット（１０）へ送信するための初期化手順を更に含み、前記処理ユニット（１０）の各々に対して、前記初期化メッセージ（８）を該処理ユニット（１０）により受信するための第３の受信手順と、前記初期化メッセージ（８）に関連したアクションの実行に合意するか否かを前記処理ユニット（１０）により判定するための合意判定手順と、を含み、前記判定及び起動手順は、前記処理ユニット（１０）の全て又は少なくとも一部分が前記初期化メッセージ（８）に関連したアクションの実行に合意することを前記制御ユニット（１２）が決定した場合に実行される、請求項１〜５の何れか一項に記載の方法。
請求項7
処理ユニット（１０）を制御するように構成されたシステムであって、複数の処理ユニット（１０）と、複数のメッセージ（２）を含む少なくとも１つのストリーム（４）を各処理ユニット（１０）へ送信するように構成された第１の送信ユニット（１４２）を含むクライアントユニット（１４）と、を備え、各メッセージ（２）は、識別子を含み、前記識別子は、順序付けされたグループのメンバーであり、前記複数のメッセージ（２）は、第１のメッセージ（２）が第２のメッセージ（２）の前に送信される場合に、該第１のメッセージ（２）の識別子が該第２のメッセージ（２）の識別子より小さくなるか、又は、該第１のメッセージ（２）の識別子が該第２のメッセージ（２）の識別子より大きくなるような順序で送信され、アクションを実行する要求（６）を全ての処理ユニット（１０）へ送信するように構成された第２の送信ユニット（１２２）を含む制御ユニット（１２）を更に備え、前記要求（６）は、トリガーを含み、前記トリガーは、順序付けされたグループのメンバーであり、更に、前記処理ユニット（１０）の各々は、複数のメッセージ（２）を含む前記少なくとも１つのストリーム（４）を受信するように構成された第１の受信ユニット（１０２）と、前記要求（６）を受信するように構成された第２の受信ユニット（１０４）と、メッセージ（２）を受信した際に、該メッセージ（２）の識別子が前記トリガー以上であるか否かを判定し、識別子が前記トリガー以上である場合に、アクションを起動するように構成されるか、又はメッセージ（２）を受信した際に、該メッセージ（２）の識別子が前記トリガー以下であるか否かを判定し、識別子が前記トリガー以下である場合に、アクションを起動するように構成された判定及び起動ユニット（１０６）と、を備える、システム。
請求項8
前記順序付けされたグループは、整数のセットであり、前記第１の送信ユニット（１４２）は、前記複数のメッセージを、それらの識別子の昇順で送信するか、又は、前記複数のメッセージを、それらの識別子の降順で送信するように構成されている、請求項７に記載のシステム。
請求項9
前記処理ユニット（１０）は、分散型記憶システムを形成し、各処理ユニット（１０）においてアクションを起動することは、そのコンテンツのバックアップを開始すること、バージョンを生成すること、記憶エンティティの状態を、例えば、読み取り／書き込みから読み取り専用へ切り換えること、上述したオペレーションの組合せ、のうちのいずれか１つを含む、請求項７又は８に記載のシステム。
請求項10
前記起動することは、アクションが起動されるときの前記処理ユニット（１０）の状態に関するメッセージ（１８）を送信することを含み、前記メッセージ（１８）は、トリガーを含む、請求項７〜９の何れか一項に記載のシステム。
請求項11
前記処理ユニット（１０）は、前記要求（６）に含まれているトリガーを記憶するように構成された記憶ユニットを更に備え、前記第２の受信ユニット（１０４）及び記憶ユニットは、いずれかの対応するアクションを起動する前に２つ以上のトリガーを受け取って記憶できるように構成されている、請求項７〜１０の何れか一項に記載のシステム。
請求項12
前記制御ユニット（１２）は、各処理ユニット（１０）がアクションの実行に合意するか否かを要求する初期化メッセージ（８）を各処理ユニット（１０）へ送信するように構成された初期化ユニット（１２４）を更に備え、前記処理ユニット（１０）の各々は、前記初期化メッセージ（８）を受信するように構成された第３の受信ユニット（１０８）と、前記初期化メッセージ（８）に関連したアクションの実行に合意するか否かを判定するように構成された合意判定ユニット(110)と、を更に備え、前記判定及び起動ユニット（１０６）は、前記処理ユニット（１０）の全て又は少なくとも一部分が前記初期化メッセージ（８）に関連したアクションの実行に合意することを前記制御ユニット（１２）が決定した場合にアクションを実行するように構成されている、請求項７〜１１の何れか一項に記載のシステム。
請求項13
処理ユニット（１０）及び少なくとも１つの他の処理ユニット（１０）を制御するためのシステムに使用されるよう構成された処理ユニット（１０）であって、該システムは、複数のメッセージ（２）を含む少なくとも１つのストリーム（４）を各処理ユニット（１０）及び少なくとも１つの他の処理ユニット（１０）へ送信するように構成された第１の送信ユニット（１４２）を含むクライアントユニット（１４）を備え、各メッセージ（２）は、識別子を含み、前記識別子は、順序付けされたグループのメンバーであり、前記複数のメッセージ（２）は、第１のメッセージ（２）が第２のメッセージ（２）の前に送信される場合に、該第１のメッセージ（２）の識別子が該第２のメッセージ（２）の識別子より小さくなるか、又は、該第１のメッセージ（２）の識別子が該第２のメッセージ（２）の識別子より大きくなるような順序で送信され、アクションを実行する要求（６）を前記処理ユニット（１０）及び少なくとも１つの他の処理ユニット（１０）へ送信するように構成された第２の送信ユニット（１２２）を含む制御ユニット（１２）を更に備え、前記要求（６）は、トリガーを含み、前記トリガーは、順序付けされたグループのメンバーであり、更に、前記処理ユニット（１０）は、複数のメッセージ（２）を含む前記少なくとも１つのストリーム（４）を受信するように構成された第１の受信ユニット（１０２）と、前記要求（６）を受信するように構成された第２の受信ユニット（１０４）と、メッセージ（２）を受信した際に、該メッセージ（２）の識別子が前記トリガー以上であるか否かを判定し、識別子が前記トリガー以上である場合に、アクションを起動するように構成されるか、又はメッセージ（２）を受信した際に、該メッセージ（２）の識別子が前記トリガー以下であるか否かを判定し、識別子が前記トリガー以下である場合に、アクションを起動するように構成された判定及び起動ユニット（１０６）と、を備える、処理ユニット（１０）。
請求項14
前記順序付けされたグループは、整数のセットであり、前記第１の送信ユニット（１４２）は、前記複数のメッセージを、それらの識別子の昇順で送信するか、又は、前記複数のメッセージを、それらの識別子の降順で送信するように構成されている、請求項１３に記載の処理ユニット（１０）。
請求項15
前記少なくとも１つの他の処理ユニット（１０）と共に、分散型記憶システムを形成し、各処理ユニット（１０）においてアクションを起動することは、そのコンテンツのバックアップを開始すること、バージョンを生成すること、記憶エンティティの状態を、例えば、読み取り／書き込みから読み取り専用へ切り換えること、上述したオペレーションの組合せ、のうちのいずれか１つを含む、請求項１３又は１４に記載の処理ユニット（１０）。
請求項16
前記起動することは、アクションが起動されるときの前記処理ユニット（１０）の状態に関するメッセージ（１８）を送信することを含み、前記メッセージ（１８）は、トリガーを含む、請求項１３〜１５の何れか一項に記載の処理ユニット（１０）。
請求項17
前記要求（６）に含まれているトリガーを記憶するように構成された記憶ユニットを更に備え、前記第２の受信ユニット（１０４）及び記憶ユニットは、いずれかの対応するアクションを起動する前に２つ以上のトリガーを受け取って記憶できるように構成されている、請求項１３〜１６の何れか一項に記載の処理ユニット（１０）。
請求項18
前記制御ユニット（１２）は、各処理ユニット（１０）がアクションの実行に合意するか否かを要求する初期化メッセージ（８）を各処理ユニット（１０）及び少なくとも１つの他の処理ユニット（１０）へ送信するように構成された初期化ユニット（１２４）を更に備え、前記処理ユニット（１０）は、前記初期化メッセージ（８）を受信するように構成された第３の受信ユニット（１０８）と、前記初期化メッセージ（８）に関連したアクションの実行に合意するか否かを判定するように構成された合意判定ユニット（１１０）と、を更に備え、前記判定及び起動ユニット（１０６）は、前記処理ユニット（１０）の全て又は少なくとも一部分が前記初期化メッセージ（８）に関連したアクションの実行に合意することを前記制御ユニット（１２）が決定した場合にアクションを実行するように構成されている、請求項１３〜１７の何れか一項に記載の処理ユニット（１０）。
請求項19
処理ユニット（１０）を制御するためのシステムに使用するように構成された制御ユニット（１２）であって、前記システムは、複数のメッセージ（２）を含む少なくとも１つのストリーム（４）を各処理ユニット（１０）へ送信するように構成された第１の送信ユニット（１４２）を含むクライアントユニット（１４）を備え、各メッセージ（２）は、識別子を含み、前記識別子は、順序付けされたグループのメンバーであり、前記複数のメッセージ（２）は、第１のメッセージ（２）が第２のメッセージ（２）の前に送信される場合に、該第１のメッセージ（２）の識別子が該第２のメッセージ（２）の識別子より小さくなるか、又は、該第１のメッセージ（２）の識別子が該第２のメッセージ（２）の識別子より大きくなるような順序で送信され、前記制御ユニット（１２）は、アクションを実行する要求（６）を全ての処理ユニット（１０）へ送信するように構成された第２の送信ユニット（１２２）を備え、前記要求（６）は、トリガーを含み、前記トリガーは、順序付けされたグループのメンバーであり、更に、前記処理ユニット（１０）の各々は、複数のメッセージ（２）を含む前記少なくとも１つのストリーム（４）を受信するように構成された第１の受信ユニット（１０２）と、前記要求（６）を受信するように構成された第２の受信ユニット（１０４）と、メッセージ（２）を受信した際に、該メッセージ（２）の識別子が前記トリガー以上であるか否かを判定し、識別子が前記トリガー以上である場合に、アクションを起動するように構成されるか、又はメッセージ（２）を受信した際に、メッセージ（２）の識別子が前記トリガー以下であるか否かを判定し、識別子が前記トリガー以下である場合に、アクションを起動するように構成された判定及び起動ユニット（１０６）と、を備える制御ユニット（１２）。
請求項20
各処理ユニット（１０）がアクションの実行に合意するか否かを要求する初期化メッセージ（８）を各処理ユニット（１０）へ送信するように構成された初期化ユニット（１２４）を更に備え、前記処理ユニット（１０）の各々は、前記初期化メッセージ（８）を受信するように構成された第３の受信ユニット（１０８）と、前記初期化メッセージ（８）に関連したアクションの実行に合意するか否かを判定するように構成された合意判定ユニット（１１０）と、を更に備え、前記判定及び起動ユニット（１０６）は、前記処理ユニット（１０）の全て又は少なくとも一部分が前記初期化メッセージ（８）に関連したアクションの実行に合意することを前記制御ユニット（１２）が決定した場合にアクションを実行するように構成されている、請求項１９に記載の制御ユニット（１２）。