ランポート時計（らんぽーとどけい）

ランポート時計とは

ランポート時計は、1978年にレスリー・ランポートによって提案された分散システムにおけるイベントの順序付けアルゴリズムです。物理的な時計に依存せず、プロセス間でのメッセージ交換を通じて論理的な順序付けを行います。これにより、分散システム全体で一貫したイベントの順序を決定することが可能になります。

仕組み

各プロセスは、自身の論理時計を持ちます。イベントが発生するたびに、論理時計はインクリメントされます。プロセスAがプロセスBにメッセージを送信する場合、プロセスAは自身の論理時計の値をメッセージに含めて送信します。プロセスBはメッセージを受信すると、自身の論理時計をメッセージに含まれる値よりも大きく更新します。このプロセスを繰り返すことで、システム全体でイベントの順序が決定されます。

特徴

• 物理的な時計に依存しない: 各プロセスの時計の精度や同期状態に依存しません。
• 因果関係の順序付け: 因果関係にあるイベントは、論理的に正しい順序で並べられます。
• 同時実行イベント: 同時に発生したイベントについては、順序は決定されません。

応用例

ランポート時計は、分散データベース、分散ロック、分散合意アルゴリズムなど、様々な分散システムで利用されています。特に、イベントの順序が重要なシステムにおいて、その有効性が発揮されます。

限界

ランポート時計は、完全な因果順序付けを提供するわけではありません。同時実行イベントの順序は決定されないため、特定のアプリケーションでは不十分な場合があります。より厳密な順序付けが必要な場合は、ベクトル時計などの他のアルゴリズムが使用されます。