Lamport-Uhr

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).

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Lamport — bezeichnet folgende Personen: Leslie Lamport (* 1941), US amerikanischer Mathematiker, Informatiker und Programmierer Allan Lamport (1903–1999), 50. Bürgermeister von Toronto Siehe auch: Lamport Uhr …   Deutsch Wikipedia

  • Lamport-Zeit — 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… …   Deutsch Wikipedia

  • Lamport Zeit — 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… …   Deutsch Wikipedia

  • Lamport Hash — Leslie Lamport Leslie Lamport (* 7. Februar 1941 in New York) ist ein US amerikanischer Mathematiker, Informatiker und Programmierer. Lamport schloss 1960 am Massachusetts Institute of Technology mit dem Bachelor in Mathematik ab. 1963 erlangte… …   Deutsch Wikipedia

  • Logische Uhr — Eine Logische Uhr ist eine Komponente eines Computersystems, die dafür verwendet wird, Ereignissen einen eindeutigen Zeitstempel zu geben. Anders als bei einer „normalen“ Echtzeituhr, die die physikalische Zeit misst, ist der einzige Anspruch an… …   Deutsch Wikipedia

  • Leslie Lamport — (* 7. Februar 1941 in New York) ist ein US amerikanischer Mathematiker, Informatiker und Programmierer. Lamport schloss 1960 am Massachusetts Institute of Technology mit dem Bachelor in Mathematik ab. 1963 erlangte er an de …   Deutsch Wikipedia

  • Geschah-Bevor — Ursache und Wirkung, bzw. Vergangenheit und Zukunft, in einer Lamport Uhr Happened Before (englisch für „passierte vor“) ist in der Informatik eine logische Beziehung zwischen zwei Zeitpunkten. Die Happened Before Relation ist wichtig um die… …   Deutsch Wikipedia

  • Geschah-Bevor-Relation — Ursache und Wirkung, bzw. Vergangenheit und Zukunft, in einer Lamport Uhr Happened Before (englisch für „passierte vor“) ist in der Informatik eine logische Beziehung zwischen zwei Zeitpunkten. Die Happened Before Relation ist wichtig um die… …   Deutsch Wikipedia

  • Happened-Before-Relation — Ursache und Wirkung, bzw. Vergangenheit und Zukunft, in einer Lamport Uhr Happened Before (englisch für „passierte vor“) ist in der Informatik eine logische Beziehung zwischen zwei Zeitpunkten. Die Happened Before Relation ist wichtig um die… …   Deutsch Wikipedia

  • Vektoruhr — Eine Vektoruhr 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 eines Zeitstempels eine… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”