Lamport-Uhr - LinkFang.de





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 partielle kausale Ordnung zuzuweisen.

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.

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:

[math]n1 \rightarrow n2 \Rightarrow C(n1) \lt C(n2)[/math]

Wobei [math]n1 \rightarrow n2[/math] für die Happened-Before-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ä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


Kategorien: Uhr | Verteiltes System

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Lamport-Uhr (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.