Zeit und globaler Zustand

Zeit und globaler Zustand befassen sich damit, wie ein verteiltes System Ereignisse ordnet und seinen kollektiven Zustand beurteilt, wenn es keine gemeinsame Uhr und keine sofortige globale Sicht gibt.

Definition

In einem verteilten System treten Ereignisse in separaten Prozessen ohne gemeinsame Uhr auf; die Untersuchung von Zeit und globalem Zustand liefert die Relationen und Algorithmen – logische und Vektoruhren, Schnappschüsse und geordnete Zustellung –, die es dem System ermöglichen, Ereignisse kausal zu ordnen und konsistente globale Zustände zu erfassen.

Scope

Dieser Bereich umfasst logische Uhren und die „Happened-before“-Relation, die Synchronisation physikalischer Uhren, Vektoruhren und die Erkennung von Kausalität und Gleichzeitigkeit, die Bestimmung konsistenter globaler Schnappschüsse sowie die für einen zuverlässigen Multicast erforderlichen Ordnungsgarantien (FIFO, kausal, total). Zusammen ermöglichen diese Werkzeuge verteilten Systemen, trotz des Fehlens einer globalen Uhr aussagekräftige Aussagen über „wann“ und „welchen Zustand“ zu treffen.

Sub-topics

• Globale Snapshots und Zustände
• Logische und physikalische Uhren
• Nachrichtenreihenfolge und Multicast
• Vektoruhren und Kausalität

Core questions

• Wie können Ereignisse in verschiedenen Prozessen ohne eine gemeinsame physikalische Uhr geordnet werden?
• Wie kann ein Prozess feststellen, ob zwei Ereignisse kausal miteinander verbunden oder gleichzeitig sind?
• Wie kann ein konsistenter globaler Schnappschuss aufgezeichnet werden, während die Berechnung fortgesetzt wird?
• Welche Ordnungsgarantien bei der Nachrichtenübermittlung sind erforderlich, um die Kausalität zu erhalten?

Key theories

Happened-before und logische Uhren

Lamports „Happened-before“-Relation definiert eine partielle kausale Ordnung von Ereignissen, und logische (skalare) Uhren weisen Zeitstempel zu, die damit konsistent sind, und bieten eine uhrenfreie Vorstellung von Ordnung, die ausreicht, um eine totale Ordnung für viele Protokolle zu erstellen.

Vektoruhren und Kausalität

Vektoruhren erweitern logische Uhren so, dass der Vergleich zweier Zeitstempel genau erfasst, ob ein Ereignis einem anderen kausal vorausgeht oder ob die beiden gleichzeitig sind, was eine präzise Kausalitätsverfolgung ermöglicht.

Konsistente globale Schnappschüsse

Der Chandy-Lamport-Schnappschussalgorithmus zeichnet einen konsistenten globalen Zustand – Prozesszustände plus Nachrichten im Transit – auf, ohne das System anzuhalten, indem er Marker entlang der Kanäle verbreitet.

Clinical relevance

Logische und Vektoruhren untermauern die kausale Konsistenz, die Konflikterkennung in replizierten Speichern und das Debugging verteilter Ausführungen; konsistente Schnappschüsse untermauern verteiltes Checkpointing, die Erkennung von Deadlocks und Terminierungen sowie die Fehlertoleranz bei der Stream-Verarbeitung.

History

Lamports Arbeit von 1978 führte die logische Zeit und die „Happened-before“-Relation ein, eines der meistzitierten Ergebnisse in der Informatik; Chandy und Lamport formalisierten konsistente globale Schnappschüsse im Jahr 1985; und Fidge und Mattern entwickelten in den späten 1980er Jahren unabhängig voneinander Vektoruhren, womit das grundlegende Instrumentarium zur Argumentation über Zeit und Zustand vervollständigt wurde.

Key figures

• Leslie Lamport
• K. Mani Chandy
• Colin Fidge
• Friedemann Mattern

Seminal works

• lamport1978
• chandy1985
• fidge1988

Frequently asked questions

Warum können verteilte Systeme nicht einfach synchronisierte physikalische Uhren verwenden?

Physikalische Uhren driften und können nicht perfekt über ein Netzwerk mit variabler Verzögerung synchronisiert werden, sodass die Echtzeitreihenfolge zweier Ereignisse mehrdeutig sein kann. Logische und Vektoruhren erfassen stattdessen die kausale Reihenfolge, die für die Korrektheit tatsächlich relevant ist.

Was macht einen globalen Schnappschuss „konsistent“?

Ein Schnappschuss ist konsistent, wenn er, wann immer er den Empfang einer Nachricht enthält, auch das Senden dieser Nachricht enthält. Ein solcher Zustand hätte während der Ausführung auftreten können, auch wenn kein einziger Zeitpunkt jemals global beobachtet wurde.