Quelltext der Seite Happened-Before

[[Datei:Lamport-Uhr.svg|mini|280px|Ursache und Wirkung, bzw. Vergangenheit und Zukunft, in einer [[Lamport-Uhr]]]]
'''Happened-Before''' (englisch für „passierte vorher“) ist in der [[Informatik]] eine logische Beziehung zwischen zwei Zeitpunkten.

Die Happened-Before-Relation ist wichtig, um die [[Kausalordnung]] von Ereignissen in [[asynchronität|asynchronen]] [[Verteiltes System|verteilten Systemen]] zu bestimmen. Sie wurde von [[Leslie Lamport]] formuliert<ref>Lamport, Leslie (1978). [https://amturing.acm.org/p558-lamport.pdf "Time, Clocks and the Ordering of Events in a Distributed System"], ''Communications of the ACM'', 21(7), 558–565.</ref>. Die Happened-Before-Relation wird im Allgemeinen durch eine [[logische Uhr]] implementiert. Umgekehrt definiert die Happened-Before-Relation die [[Uhrenbedingung]] für diese logische Uhr.

Um die relative Zeit zwischen zwei auftretenden Ereignissen in einem verteilten System ohne eine globale Uhr herauszufinden, benutzt man die Happened-Before-Relation (→), die für [[Lamport-Uhr]]en wie 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 ([[Transitive Relation|Transitivität]]).

Dabei wird der Wert der lokalen Uhr jeweils der Nachricht als [[Zeitstempel]] beigefügt.

Die Happend-Before-Relation nach Lamport liefert eine [[Striktordnung|''strenge'']] [[Halbordnung]] für die Ereignisse. Sie ist nicht ausreichend, wenn man [[nebenläufigkeit|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 <math>\Rightarrow</math> Zeit(a) &lt; Zeit(b) gilt. Die Umkehrung Zeit(a) &lt; Zeit(b) <math>\Rightarrow</math> a → b gilt jedoch nicht (bzw. nur auf demselben Prozess).

Um eine [[Totalordnung|totale Ordnung]] von Ereignissen zu erhalten, kann man z.&nbsp;B. [[Vektoruhr]]en benutzen.

== Einzelnachweise ==
<references />

[[Kategorie:Theoretische Informatik]]