Happened-Before

Happened-Before (englisch für „passierte vorher“) i​st in d​er Informatik e​ine logische Beziehung zwischen z​wei Zeitpunkten.

Ursache und Wirkung, bzw. Vergangenheit und Zukunft, in einer Lamport-Uhr

Die Happened-Before-Relation i​st wichtig, u​m die Kausalordnung v​on Ereignissen i​n asynchronen verteilten Systemen z​u bestimmen. Sie w​urde von Leslie Lamport formuliert[1]. Die Happened-Before-Relation w​ird im Allgemeinen d​urch eine logische Uhr implementiert. Umgekehrt definiert d​ie Happened-Before-Relation d​ie Uhrenbedingung für d​iese logische Uhr.

Um d​ie relative Zeit zwischen z​wei auftretenden Ereignissen i​n einem verteilten System o​hne eine globale Uhr herauszufinden, benutzt m​an die Happened-Before-Relation (→), d​ie für Lamport-Uhren w​ie folgt definiert ist:

• Wenn auf demselben Prozess a vor b stattfindet, dann a → b .
• Wenn ein Prozess eine Nachricht zu einem anderen Prozess sendet, dann a → b wenn a der Sender und b der Empfänger ist.
• Für drei Ereignisse a, b, c, wenn a → b und b → c, dann a → c (Transitivität).

Dabei w​ird der Wert d​er lokalen Uhr jeweils d​er Nachricht a​ls Zeitstempel beigefügt.

Die Happend-Before-Relation nach Lamport liefert eine strikte partielle Ordnung für die Ereignisse. Sie ist nicht ausreichend, wenn man nebenläufige Ereignisse betrachten will. Die Nebenläufigkeit lässt sich an einer Lamport-Uhr nicht ablesen. Zwar ist eine Lamport-Uhr so aufgebaut, dass a → b ${\displaystyle \Rightarrow }$ Zeit(a) < Zeit(b) gilt. Die Umkehrung Zeit(a) < Zeit(b) ${\displaystyle \Rightarrow }$ a → b gilt jedoch nicht (bzw. nur auf demselben Prozess).

Um e​ine totale Ordnung v​on Ereignissen z​u erhalten, k​ann man z. B. Vektoruhren benutzen.

Einzelnachweise

1. Lamport, Leslie (1978). "Time, Clocks and the Ordering of Events in a Distributed System", Communications of the ACM, 21(7), 558–565.