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

分散コンピュータシステムにおけるイベントの順序を決定するために使用されるアルゴリズム

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

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

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

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

アルゴリズム

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

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

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

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

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

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

考慮事項

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

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

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

因果順序

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

意味合い

ランポートクロックは、プロセス間のイベントの部分的な順序付けを作成するために使用できます。これらの規則に従う論理クロックが与えられた場合、次の関係が成り立ちます。の場合、はが先行することを意味します。 $a\rightarrow b$ $C(a)<C(b)$ $\rightarrow \,$

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

しかし、逆説を通して、がを意味することは真です。したがって、例えばの場合、がの前に起こったということはあり得ません。 $C(a)\nless C(b)$ $a\nrightarrow b$ $C(a)\geq C(b)$ $a$ $b$

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

しかしながら、ランポートタイムスタンプは、分散システムにおけるイベントの完全な順序付けを行うために、任意のメカニズム（例えばプロセスID）を用いて順序付けを行うことで使用できます。ただし、この順序付けは人為的なものであり、因果関係を示唆するものとして依拠することはできません。

分散システムにおけるランポートの論理クロック

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

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

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

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

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

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

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

ランポートの時計では、との実際の時刻については何も言えないことに注意してください。論理時計がと示したとしても、それは実際にはが実時間で実際に起こったことを意味するわけではありません。 $a$ $b$ $C(a)<C(b)$ $a$ $b$

ランポート時計は非因果性を示しますが、すべての因果性を捉えているわけではありません。とが分かれば、またはが原因ではないことがわかりますが、のどちらがを開始したかはわかりません。 $a\rightarrow c$ $b\rightarrow c$ $c$ $a$ $b$ $c$

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

潜在的な因果関係の代替案

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

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

参照

参考文献

^ 「分散システム第3版 (2017)」DISTRIBUTED-SYSTEMS.NET . 2021年3月20日閲覧。
^ ab Lamport, L. (1978). 「分散システムにおける時間、クロック、そしてイベントの順序付け」(PDF) . Communications of the ACM . 21 (7): 558– 565. doi :10.1145/359545.359563. S2CID 215822405.
^ 「クロックと同期 — 分散システムアルファ版ドキュメント」books.cs.luc.edu . 2017年12月13日閲覧。
^ 「情報駆動型インタラクション指向プログラミング：BSPL、驚くほどシンプルなプロトコル言語」（PDF）。 2025年10月21日閲覧。

[1] 「分散システム第3版 (2017)」DISTRIBUTED-SYSTEMS.NET . 2021年3月20日閲覧。

[Lamport_1978-2] Lamport, L. (1978). 「分散システムにおける時間、クロック、そしてイベントの順序付け」(PDF) . Communications of the ACM . 21 (7): 558– 565. doi :10.1145/359545.359563. S2CID 215822405.

[3] 「クロックと同期 — 分散システムアルファ版ドキュメント」books.cs.luc.edu . 2017年12月13日閲覧。

[4] 「情報駆動型インタラクション指向プログラミング：BSPL、驚くほどシンプルなプロトコル言語」（PDF）。 2025年10月21日閲覧。