時間とグローバル状態
時間とグローバル状態は、共有クロックや瞬時的なグローバルビューが存在しない分散システムにおいて、イベントの順序付けと集合的な状態の推論がどのように行われるかに関わる。
PaperMindでテーマを探す近日公開Find papers & topics
Tools & resources
Learn & explore
動画近日公開
Definition
分散システムでは、共有クロックを持たない別々のプロセスでイベントが発生する。時間とグローバル状態の研究は、システムがイベントを因果的に順序付けし、一貫性のあるグローバル状態を捕捉することを可能にする関係とアルゴリズム（論理クロック、ベクトルクロック、スナップショット、順序付けされた配信）を提供する。
Scope
この分野は、論理クロックと先行関係、物理クロック同期、ベクトルクロックと因果関係および並行性の検出、一貫性のあるグローバルスナップショットの決定、そして信頼性の高いマルチキャストに必要な順序保証（FIFO、因果的、全順序）を扱う。これらのツールを組み合わせることで、分散システムはグローバルクロックがないにもかかわらず、「いつ」そして「どのような状態」について意味のある記述をすることが可能となる。
Sub-topics
Core questions
- 共有物理クロックなしに、異なるプロセスでのイベントをどのように順序付けることができるか？
- プロセスは、2つのイベントが因果的に関連しているか、あるいは並行しているかをどのように判断できるか？
- 計算が継続している間に、一貫性のあるグローバルスナップショットをどのように記録できるか？
- 因果関係を維持するために、メッセージ配信にどのような順序保証が必要か？
Key theories
- 先行関係と論理クロック
- Lamportの先行関係は、イベントに対する部分的な因果順序を定義し、論理（スカラー）クロックはそれに一貫性のあるタイムスタンプを割り当てる。これにより、多くのプロトコルで全順序を構築するのに十分な、クロックに依存しない順序の概念が提供される。
- ベクトルクロックと因果関係
- ベクトルクロックは論理クロックを拡張し、2つのタイムスタンプを比較することで、あるイベントが別のイベントに因果的に先行するか、あるいは2つのイベントが並行しているかを正確に捉え、精密な因果関係の追跡を可能にする。
- 一貫性のあるグローバルスナップショット
- Chandy-Lamportスナップショットアルゴリズムは、システムを停止させることなく、マーカーをチャネルに沿って伝播させることで、一貫性のあるグローバル状態（プロセス状態と転送中のメッセージ）を記録する。
Clinical relevance
論理クロックとベクトルクロックは、因果一貫性、レプリケートされたストアにおける競合検出、分散実行のデバッグを支える。一貫性のあるスナップショットは、分散チェックポイント、デッドロックおよび終了検出、ストリーム処理の障害回復を支える。
History
Lamportの1978年の論文は、論理時間と先行関係を導入し、これはコンピュータサイエンスで最も引用された成果の一つである。ChandyとLamportは1985年に一貫性のあるグローバルスナップショットを形式化し、FidgeとMatternは1980年代後半に独立してベクトルクロックを開発し、時間と状態について推論するための基礎的なツールキットを完成させた。
Key figures
- Leslie Lamport
- K. Mani Chandy
- Colin Fidge
- Friedemann Mattern
Related topics
Seminal works
- lamport1978
- chandy1985
- fidge1988
Frequently asked questions
- 分散システムはなぜ同期された物理クロックを使用できないのか？
- 物理クロックはドリフトし、可変遅延のあるネットワーク全体で完全に同期することはできないため、2つのイベントのリアルタイム順序は曖昧になる可能性がある。論理クロックとベクトルクロックは、代わりに正確性にとって実際に重要な因果順序を捉える。
- グローバルスナップショットが「一貫性がある」とはどういうことか？
- スナップショットは、メッセージの受信が含まれる場合、そのメッセージの送信も含まれる場合に一貫性がある。このような状態は、グローバルに単一の瞬間が観測されなかったとしても、実行中に発生した可能性がある。