Lamport-Uhr

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 oder gleich dem aktuellen Stand der eigenen Uhr ist, dann wird die Uhr auf den Wert des Zeitstempels+1 gesetzt.

Beispiel der Anwendung einer Lamport-Uhr

Die Routine zum Verschicken einer Nachricht sieht also (in Pseudocode) folgendermaßen aus:

Uhr = Uhr+1;
Zeitstempel = Uhr;
sende(Nachricht, Zeitstempel);

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:

$n1 n2 \Rightarrow C(n1) < C(n2)$

Das nennt man auch die Happened-Before-Relation nach Lamport, geschrieben:

$n1 \Rightarrow n2$

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 aufwändigeren Vektoruhren.

Der Algorithmus Basic Timestamp Ordering verwendet die Lamport-Uhr, um verteilte Transaktionen zu synchronisieren.

Literatur

• Leslie Lamport: Time, clocks, and the ordering of events in a distributed system. In: Communications of the ACM. 21, Nr. 7, Juli 1978, ISSN 0001-0782, S. 558–565, doi:10.1145/359545.359563 (PDF, 855 kB, online, abgerufen am 1. August 2008).