Logische und physikalische Uhren

Logische Uhren ordnen Ereignisse kausal, ohne Bezug zur Echtzeit, während die Synchronisation physikalischer Uhren die Echtzeituhren separater Maschinen trotz Drift nah beieinander hält.

Definition

Eine logische Uhr weist jedem Ereignis einen ganzzahligen Zeitstempel zu, der entlang jedes Prozesses monoton ist und über die Kommunikation hinweg zunimmt, wodurch die kausale Ordnung erfasst wird; die Synchronisation physikalischer Uhren ist der Prozess der Anpassung der Hardware-Uhren von Maschinen, sodass sie annähernd dieselbe Echtzeit anzeigen.

Scope

Dieses Thema behandelt Lamports logische (skalare) Uhren und die von ihnen respektierte Happened-Before-Relation, die Konstruktion einer totalen Ordnung aus logischen Zeitstempeln sowie die Synchronisation physikalischer Uhren – Begrenzung der Drift, Austausch von Zeitstempeln zur Schätzung des Offsets und die in der Praxis verwendeten Algorithmen (Cristians Methode, Berkeley-Algorithmus, NTP). Es wird gegenübergestellt, wann kausale logische Zeit ausreicht und wann Echtzeit tatsächlich erforderlich ist.

Core questions

• Wie können Zeitstempel so zugewiesen werden, dass sie die kausale Happened-Before-Relation respektieren?
• Wie wird eine konsistente totale Ordnung von Ereignissen aus logischen Uhren aufgebaut?
• Wie genau können physikalische Uhren angesichts variabler Netzwerkverzögerung und Drift synchronisiert werden?

Key theories

Lamport-Logikuhren

Jeder Prozess führt einen Zähler, der bei jedem Ereignis inkrementiert und mit Nachrichten übertragen wird; die resultierenden Zeitstempel respektieren Happened-Before, und bei Gleichstand durch Prozess-ID wird eine totale Ordnung erzeugt, die mit der Kausalität konsistent ist.

Probabilistische und Round-Trip-Synchronisation

Cristians Methode schätzt eine entfernte Uhr, indem sie die Round-Trip-Zeit misst und eine symmetrische Verzögerung annimmt, wodurch probabilistische Grenzen für den über ein Netzwerk erreichbaren Synchronisationsfehler bereitgestellt werden.

Network Time Protocol

NTP organisiert Zeitserver in einer geschichteten Hierarchie und verwendet statistische Filterung wiederholter Offset-Messungen, um Uhren im gesamten Internet auf Millisekunden genau zu disziplinieren.

Clinical relevance

Logische Uhren ordnen Operationen in replizierten Speichern und Nachrichtenwarteschlangen, ohne der Wanduhrzeit zu vertrauen, während die physikalische Synchronisation die Grundlage für zeitstempelbasierte Datenbanken, verteiltes Tracing und Sicherheitsprotokolle bildet, die von einem begrenzten Uhrenfehler abhängen.

History

Lamports Artikel über logische Uhren aus dem Jahr 1978 definierte Zeit in verteilten Systemen als kausales statt physikalisches Konzept neu; parallel dazu entwickelten Cristian und andere die probabilistische Synchronisation, und Mills' NTP wurde zum Standardmechanismus, um Internetuhren abzugleichen.

Debates

Logische versus physikalische Zeit für die Reihenfolge von Operationen

Logische Uhren garantieren kausale Korrektheit, ohne Hardware-Uhren zu vertrauen, können aber Ereignisse nicht zur Echtzeit in Beziehung setzen; physikalische Uhren ermöglichen Echtzeit-Argumentation auf die Gefahr einer falschen Reihenfolge, wenn die Drift die Nachrichtenverzögerung überschreitet, was hybride Ansätze motiviert.

Key figures

• Leslie Lamport
• Flaviu Cristian
• David Mills

Seminal works

• lamport1978
• mills1991
• cristian1989

Frequently asked questions

Wenn a einen kleineren Lamport-Zeitstempel als b hat, ist a dann vor b geschehen?

Nicht unbedingt – ein kleinerer Zeitstempel ist mit Happened-Before konsistent, impliziert es aber nicht, da gleichzeitige Ereignisse geordnete Zeitstempel erhalten können. Um die Kausalität präzise zu bestimmen, benötigt man Vektoruhren, keine skalaren Logikuhren.