ランポートタイムスタンプ

ランポートタイムスタンプアルゴリズムは、分散コンピュータ システムでイベントの順序を決定するために使用される単純な論理クロック アルゴリズムです。異なるノードまたはプロセスは通常完全に同期されていないため、このアルゴリズムは、最小限のオーバーヘッドでイベントの部分的な順序付けを提供し、概念的には、より高度なベクトル クロックメソッドの開始点を提供します。このアルゴリズムは、作成者であるLeslie Lamportにちなんで名付けられました。

リソース同期などの分散アルゴリズムは、多くの場合、イベントを機能させるために何らかの順序付け方法に依存します。たとえば、2 つのプロセスとディスクがあるシステムについて考えます。プロセスは互いにメッセージを送信し、アクセスを要求するディスクにもメッセージを送信します。ディスクは、メッセージを受信した順序でアクセスを許可します。たとえば、プロセス は書き込みアクセスを要求するメッセージをディスク に送信し、次にプロセス に読み取り命令メッセージを送信します。プロセス はメッセージを受信し、結果として独自の読み取り要求メッセージをディスク に送信します。タイミングの遅延によりディスクが両方のメッセージを同時に受信した場合、ディスクはどちらのメッセージが他方より前に発生したかを判断できます。つまり、同じプロセス内に留まりながら前進する方法と、メッセージの送信から受信までをたどる方法の 2 種類の一連の移動によって からに到達できる場合、前に発生します。論理クロック アルゴリズムは、このようなイベントの順序に関する事実を判断するメカニズムを提供します。 2つのイベントが、直接またはサードパーティのプロセスを介して間接的にメッセージを交換しない異なるプロセスで発生した場合、2つのプロセスは同時実行されていると言い、2つのイベントの順序については何も言えないことに注意してください。^[1]${\displaystyle A}$${\displaystyle B}$${\displaystyle B}$${\displaystyle A}$ ${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$

ランポートは、以前に発生した順序を数値で捉えることができるシンプルなメカニズムを発明しました。ランポート論理クロックは、各プロセスで維持される数値ソフトウェア カウンター値です。

概念的には、この論理クロックは、プロセス間で移動するメッセージに関してのみ意味を持つクロックと考えることができます。プロセスがメッセージを受信すると、その送信元と論理クロックを再同期します。上記のベクター クロックは、この考え方を任意の数の並列かつ独立したプロセスのコンテキストに一般化したものです。

アルゴリズムはいくつかの簡単なルールに従います:

1. プロセスは、各ローカル イベント (メッセージ送信イベントなど) の前にカウンターを増分します。
2. プロセスがメッセージを送信する場合、ステップ 1 を実行した後、メッセージにカウンター値が含まれます。
3. メッセージを受信すると、必要に応じて、受信者のカウンタが現在のカウンタと受信メッセージのタイムスタンプの大きい方に更新されます。その後、カウンタは1ずつ増加し、メッセージが受信されたとみなされます。^[2]

疑似コードでは、送信アルゴリズムは次のようになります。

# イベントは既知です
時間 = 時間 + 1;
# イベント発生
送信(メッセージ、時間);

メッセージを受信するアルゴリズムは次のとおりです。

(メッセージ、タイムスタンプ) = 受信();
時間 = max(タイムスタンプ、時間) + 1;

同じプロセスで発生する2 つの異なるイベント と があり、が特定のイベントのタイムスタンプである場合、 がと決して等しくならないことが必要です。 ${\displaystyle a}$${\displaystyle b}$${\displaystyle C(x)}$${\displaystyle x}$${\displaystyle C(a)}$${\displaystyle C(b)}$

したがって、次のことが必要です。

• 論理クロックは、イベントとイベントの間に少なくとも 1 つのクロック「ティック」（カウンターの増分）が存在するように設定されます。${\displaystyle a}$${\displaystyle b}$
• マルチプロセスまたはマルチスレッド環境では、異なるプロセスで同時に発生する可能性のあるイベントを区別できるように、プロセス ID (PID) またはその他の一意の ID をタイムスタンプに添付する必要がある場合があります。${\displaystyle a}$${\displaystyle b}$

任意の 2 つのイベント、およびについて、がに影響を与える可能性がある場合、 の Lamport タイムスタンプはの Lamport タイムスタンプよりも小さくなります。 どちらが先に発生したかがわからない 2 つのイベントが発生する可能性もあります。その場合、イベントが互いに影響を与えることはできなかったことを意味します。と が互いに影響を与えられない場合、どちらが先に発生したかは問題ではありません。 ${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$${\displaystyle b}$

ラムポート クロックは、プロセス間のイベントの部分的な順序付けを作成するために使用できます。これらのルールに従う論理クロックが与えられた場合、次の関係が真になります: の場合、は以前に発生した を意味します。 ${\displaystyle a\rightarrow b}$${\displaystyle C(a)<C(b)}$${\displaystyle \rightarrow \,}$

この関係は一方向にのみ適用され、クロック整合性条件と呼ばれます。つまり、あるイベントが別のイベントの前に来る場合、そのイベントの論理クロックは他のイベントの前に来ます。双方向の強いクロック整合性条件(の場合) は、ベクトル クロックなどの他の手法によって取得できます。単純な Lamport クロックのみを使用すると、クロックから部分的な因果順序しか推測できません。 ${\displaystyle C(a)<C(b)}$${\displaystyle a\rightarrow b}$

しかし、逆説 を介して、 がを意味することは真です。したがって、たとえば の場合、は以前に起こったであるはずがありません。 ${\displaystyle C(a)\nless C(b)}$${\displaystyle a\nrightarrow b}$${\displaystyle C(a)\geq C(b)}$${\displaystyle a}$ ${\displaystyle b}$

別の言い方をすると、 はより前に起こったか、またはより前に起こった順序付けにおいてと比較できないが、より後には起こっていない可能性があることを意味します。 ${\displaystyle C(a)<C(b)}$${\displaystyle a}$ ${\displaystyle b}$${\displaystyle b}$${\displaystyle a}$${\displaystyle b}$

ただし、Lamport タイムスタンプは、何らかの任意のメカニズム (プロセスの ID など) を使用して同点を区別することで、分散システム内のイベントの全体的な順序付けを作成するために使用できます。ただし、この順序付けは人為的なものであり、因果関係を暗示するものとして頼りにすることはできません。

分散システムでは、システム内のエンティティ (通常はプロセスと考えられる) 間で時間を同期することは実際には不可能です。そのため、エンティティは通信するイベントに基づいて論理クロックの概念を使用できます。

2 つのエンティティがメッセージを交換しない場合は、共通のクロックを共有する必要はおそらくありません。これらのエンティティで発生するイベントは同時イベ​​ントと呼ばれます。

同じローカル マシン上のプロセス間では、システムのローカル クロックに基づいてイベントを順序付けることができます。

2 つのエンティティがメッセージ パッシングによって通信する場合、送信イベントは受信イベントの前に発生すると言われ、イベント間の論理的な順序を確立できます。

分散システムは、システム内のイベント間に部分的な順序関係がある場合、部分的な順序を持っていると言われます。システム内のすべてのイベント間の因果関係である「全体性」を確立できる場合、システムは全順序を持っていると言われます。

単一のエンティティで 2 つのイベントが同時に発生することはありません。システムが全順序を持つ場合、システム内のすべてのイベントの順序を決定できます。システムがプロセス間で部分順序を持つ場合 (これは Lamport の論理クロックが提供するタイプの順序です)、相互作用するエンティティ間の順序のみを判断できます。Lamport は、同じタイムスタンプ (またはカウンター) を持つ 2 つのイベントの順序付けについて次のように述べています。「同点の場合は、プロセスの任意の全順序付けを使用します。」^[2]したがって、分散システム内では 2 つのタイムスタンプまたはカウンターが同じになる場合がありますが、論理クロック アルゴリズムを適用すると、発生するイベントは常に少なくとも厳密な部分順序を維持します。 ${\displaystyle <}$

ランポート クロックは、分散システム内のすべてのイベントが完全に順序付けられる状況をもたらします。つまり、 の場合、 が実際に より前に発生したと言えます。 ${\displaystyle a\rightarrow b}$${\displaystyle a}$${\displaystyle b}$

ランポートの時計では、との実際の時間については何も言えないことに注意してください。論理時計が と言った場合、それは実際には実時間で が実際にそれより前に起こったことを意味しません。 ${\displaystyle a}$${\displaystyle b}$${\displaystyle C(a)<C(b)}$${\displaystyle a}$${\displaystyle b}$

ランポート時計は非因果関係を示しますが、すべての因果関係を捉えているわけではありません。 と を知ることは、またはを引き起こしていないことを示しますが、 のどちらが を開始したかはわかりません。 ${\displaystyle a\rightarrow c}$${\displaystyle b\rightarrow c}$${\displaystyle c}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$

この種の情報は、分散システムでイベントを再生しようとするとき（クラッシュ後の回復を試みる場合など）に重要になることがあります。1つのノードがダウンした場合、メッセージ間の因果関係がわかっていれば、それらのメッセージを再生し、因果関係を尊重してそのノードを必要な状態に戻すことができます。^[3]

以前に起こった関係は、真の因果関係ではなく、潜在的な因果関係を捉えています。2011-12 年に、Munindar Singh は、情報プロトコルと呼ばれる、真の因果関係に基づく宣言的なマルチエージェント アプローチを提案しました。情報プロトコルは、分散システムを構成するエージェント間の通信の制約を指定します。^[4]ただし、情報プロトコルは、メッセージの順序を指定する代わりに (たとえば、コンピューティングでプロトコルを表現する一般的な方法である状態マシンを介して)、エージェント (プロトコルのエンドポイント) が送信できる通信間の情報依存関係を指定します。エージェントは、通信と状態が関連する情報依存関係を満たす場合にのみ、ローカル状態 (通信履歴) で通信を送信できます。たとえば、e コマース アプリケーションの情報プロトコルでは、パラメータ ID (一意化子)、アイテム、価格を含む見積もりを送信するには、売り手は状態から ID とアイテムを既に知っている必要がありますが、任意の価格を生成できることを指定します。情報プロトコルの注目すべき点は、送信は制約されているが、受信は制約されていないことです。具体的には、エージェントはどのような順序でも通信を受信できます。受信は単に情報をもたらすだけであり、遅延させる意味はありません。つまり、情報プロトコルは、UDPなどの順序付けされていない通信サービス上で実行できます。

より大きなアイデアは、アプリケーション セマンティクス、つまり、メッセージの内容に基づいて分散システムを設計するというアイデアであり、エンドツーエンド原則に関係するアイデアです。現在のアプローチは、セマンティクスをほとんど無視し、通信サービスでアプリケーションに依存しない (「構文的」) メッセージ配信と順序の保証を提供することに重点を置いています。ここで、潜在的な因果関係などのアイデアが役立ちます。しかし、アプリケーション セマンティクスを実行する適切な方法があれば、そのような通信サービスは必要ありません。順序付けされていない、信頼性のない通信サービスで十分です。情報プロトコル アプローチの真の価値は、アプリケーション セマンティクス アプローチの基礎を提供することです。

• マトリックスクロック
• ベクトルクロック
• バージョンベクター