Quelltext der Seite Lamport-Uhr

Die '''Lamport-Uhr''' (nach dem amerikanischen [[Mathematiker]] und [[Informatiker]] [[Leslie Lamport]]) ist eine [[Software]]komponente (oder ein [[Netzwerkprotokoll|Protokoll]]) zum Zuweisen von eindeutigen [[Zeitstempel]]n an [[Nachricht]]en. Sie ist also eine [[Logische Uhr]], die es erlaubt, den [[Ereignis]]sen in einem [[Verteilte Systeme|Verteilten System]] aufgrund ihres Zeitstempels eine [[Partielle Ordnung#Halbordnung|partielle]] [[Kausalordnung|kausale]] Ordnung zuzuweisen.

Dabei geht man folgendermaßen vor: Jeder [[Prozess (Computer)|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.

[[Datei:Lamport-Uhr.svg|mini|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'' [[Logische Uhr#Uhrenbedingung und Kausalordnung|Konsistenzbedingung für Uhren]]:

: <math>n1 \rightarrow n2  \Rightarrow  C(n1) < C(n2)</math>

Wobei ''<math>n1 \rightarrow n2</math>'' für die [[Happened-Before]]-[[Relation (Mathematik)|Relation]] nach Lamport steht.

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äufigkeit|nebenläufig]] sind. Eine Lösung für dieses Problem bieten die etwas aufwändigeren [[Vektoruhr]]en.

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

== Siehe auch ==
* [[Erweiterte Lamportzeit]]
== Literatur ==
* {{Literatur |Autor=Leslie Lamport |Titel=Time, clocks, and the ordering of events in a distributed system |Sammelwerk=Communications of the ACM |Band=21 |Nummer=7 |Datum=1978-07 |ISSN=0001-0782 |Seiten=558–565 |Sprache=en |Online=http://research.microsoft.com/users/lamport/pubs/time-clocks.pdf |Format=PDF |KBytes=855 |DOI=10.1145/359545.359563 |Abruf=2008-08-01}}

[[Kategorie:Verteiltes System]]
[[Kategorie:Uhren]]