Lamport-Uhr
aus Wikipedia, der freien Enzyklopädie
Die Lamport-Uhr (nach dem amerikanischen Mathematiker und Informatiker Leslie Lamport) ist eine Softwarekomponente (oder ein Protokoll) zum Zuweisen von eindeutigen Zeitstempeln an Nachrichten. Sie ist also eine Logische Uhr, die es erlaubt, den Ereignissen in einem Verteilten System aufgrund ihres Zeitstempels eine Kausalordnung zuzuweisen (Sequentialisierung).
Dabei geht man folgendermaßen vor: Jeder Prozess hat einen Zähler (die Uhr), der bei jedem Ereignis (insbesondere beim Senden und Empfangen von Nachrichten) erhöht wird. Zudem wird der aktuelle Stand des Zählers an jede Nachricht als Zeitstempel angehängt. Wird nun eine Nachricht empfangen, deren Zeitstempel größer ist als der aktuelle Stand der eigenen Uhr, dann wird die Uhr auf den Wert des Zeitstempels+1 gesetzt.
Die Routine zum Verschicken einer Nachricht sieht also (in Pseudocode) folgendermaßen aus:
Zeitstempel = Uhr; sende(Nachricht, Zeitstempel); Uhr = Uhr+1;
Die Routine zum Empfangen einer Nachricht:
(Nachricht, Zeitstempel) = empfange(); Uhr = max(Zeitstempel, Uhr) + 1;
Sortiert man im Nachhinein alle empfangenen Nachrichten (n1, n2 usw.) nach ihrem Zeitstempel (C(n1), C(n2) usw.), dann ist garantiert, dass, falls die Nachricht n1 einen Einfluss auf die Nachricht n2 hatte, der Zeitstempel von n1 kleiner ist als der Zeitstempel von n2. Das entspricht der schwachen Konsistenzbedingung für Uhren:
Das nennt man auch die Happened-Before-Relation nach Lamport, geschrieben:
Lamport-Uhren erfüllen jedoch nicht die starke Konsistenzbedingung für Uhren. Insbesondere kann man an den Zeitstempeln einer Lamport-Uhr nicht ablesen, welche Ereignisse kausal unabhängig, das heißt nebenläufig sind. Eine Lösung für dieses Problem bieten die etwas aufwendigeren Vektoruhren.
Siehe auch erweiterte Lamportzeit.
