Lamport-Zeit

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

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.

Siehe auch

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) (online ; Stand: 1. August 2008; PDF, 855 kB). 

Siehe auch


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

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

  • 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

  • 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

  • Happened-Before — 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

  • Blue Star Line — Das Logo der Blue Star Line Die Blue Star Line (BSL) war eine britische Reederei mit Hauptsitz in London und betrieb einen sehr erfolgreichen Liniendienst nach Südamerika. Die Schifffahrtsdienste wurden im Laufe der Zeit bis Australien,… …   Deutsch Wikipedia

  • Logical Clock — 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

  • Uhrenbedingung — 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

  • Liste bedeutender Seeunfälle 1900 bis 1949 — Untergang der RMS Titanic am 15. April 1912 Die Liste bedeutender Seeunfälle 1900 bis 1949 enthält Unfälle der Seeschifffahrt in der Zeit von 1900 bis 1949, bei denen es zum Verlust von Menschenleben kam oder hoher Sachschaden entstanden ist, in… …   Deutsch Wikipedia

  • Liste der Biografien/Lai–Lam — Biografien: A B C D E F G H I J K L M N O P Q …   Deutsch Wikipedia

Share the article and excerpts

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