論理クロックと物理クロック

論理クロックは、実時間とは無関係に因果関係によってイベントを順序付けますが、物理クロック同期は、ドリフトがあるにもかかわらず、個々のマシンの実時間クロックを互いに近い状態に保ちます。

Definition

論理クロックは、各イベントに、各プロセスに沿って単調であり、通信を介して増加する整数タイムスタンプを割り当て、因果順序を捉えます。物理クロック同期は、マシンのハードウェアクロックを調整して、ほぼ同じ実時間を読み取るようにするプロセスです。

Scope

このトピックでは、ランポートの論理（スカラー）クロックと、それらが尊重する「先行発生」関係、論理タイムスタンプからの全順序の構築、および物理クロック同期（ドリフトの制限、オフセットを推定するためのタイムスタンプの交換、実際に使用されるアルゴリズム（クリスチャンの方法、バークレーアルゴリズム、NTP））について説明します。因果的な論理時間が十分な場合と、実時間が本当に必要な場合を対比させます。

Core questions

• 因果的な先行発生関係を尊重するようにタイムスタンプを割り当てるにはどうすればよいですか？
• 論理クロックからイベントの一貫した全順序はどのように構築されますか？
• 可変ネットワーク遅延とドリフトを考慮して、物理クロックはどの程度厳密に同期できますか？

Key theories

ランポートの論理クロック

各プロセスは、すべてのイベントでインクリメントされ、メッセージで伝達されるカウンターを保持します。結果として得られるタイムスタンプは先行発生を尊重し、プロセス識別子によって同順位を解消することで、因果関係と整合する全順序が得られます。

確率的およびラウンドトリップ同期

クリスチャンの方法は、ラウンドトリップ時間を測定し、対称的な遅延を仮定することでリモートクロックを推定し、ネットワーク上で達成可能な同期エラーの確率的境界を提供します。

ネットワークタイムプロトコル

NTPは、タイムサーバーを階層的な階層に編成し、繰り返されるオフセット測定の統計的フィルタリングを使用して、インターネット全体のクロックをミリ秒以内に調整します。

Clinical relevance

論理クロックは、ウォールクロック時間を信頼することなく、レプリケートされたストアやメッセージキュー内の操作を順序付けます。一方、物理同期は、タイムスタンプ順のデータベース、分散トレーシング、および境界のあるクロックエラーに依存するセキュリティプロトコルの基盤となります。

History

ランポートの1978年の論理クロックに関する論文は、分散システムにおける時間を物理的な概念ではなく因果的な概念として再定義しました。並行して、クリスチャンらが確率的同期を開発し、ミルズのNTPはインターネットクロックを同期させるための標準的なメカニズムとなりました。

Debates

操作の順序付けにおける論理時間と物理時間

論理クロックは、ハードウェアクロックを信頼することなく因果的な正確性を保証しますが、イベントを実時間に関連付けることはできません。物理クロックは、ドリフトがメッセージ遅延を超える場合に誤った順序付けのリスクを伴いながら、実時間推論を可能にするため、ハイブリッドアプローチが動機付けられます。

Key figures

• Leslie Lamport
• Flaviu Cristian
• David Mills

Seminal works

• lamport1978
• mills1991
• cristian1989

Frequently asked questions

aのランポートタイムスタンプがbよりも小さい場合、aはbより前に発生しましたか？

必ずしもそうではありません。タイムスタンプが小さいことは先行発生と整合しますが、それを意味するわけではありません。なぜなら、並行するイベントは順序付けられたタイムスタンプを受け取る可能性があるからです。因果関係を正確に判断するには、スカラー論理クロックではなく、ベクトルクロックが必要です。