Happened-Before

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 Kausalordnung von Ereignissen in asynchronen verteilten Systemen zu bestimmen. Sie wurde von Leslie Lamport formuliert. 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-Uhren wie folgt definiert ist:

  • Auf demselben Prozess, a → b wenn die Zeit von a < der Zeit von b (die Zeit ist durch die lokale Uhr gegeben)
  • Wenn ein Prozess eine Nachricht zu einem anderen Prozess sendet, dann a → b wenn a der Sender ist und b der Empfänger.
  • Für drei Ereignisse a, b, c, wenn a → b und b → c, dann a → c (Transitivität).

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

Die Happend-Before-Relation nach Lamport liefert nur eine 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, denn a → b bedeutet, dass Zeit(a) < Zeit(b), aber Zeit(a) < Zeit(b) bedeutet nicht, dass a → b.

Um eine totale Ordnung von Ereignissen zu erhalten kann man z. B. Vektoruhren benutzen.


Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

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

  • Happened-before — The happened before relation (denoted: o) is a means of ordering events based on the causal relationship of two events in asynchronous distributed systems. It was formulated by Leslie Lamport.The happened before relation is formally defined as: * …   Wikipedia

  • Happened-before — Arrivé avant La relation arrivé avant (anglais happened before), notée , est un ordre partiel (relation binaire irréflexive, antisymétrique et transitive) sur les évènements basé sur la causalité de deux évènements dans un système distribué… …   Wikipédia en Français

  • 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

  • This Never Happened Before — Infobox Single Name = This Never Happened Before Caption = Album cover art Artist = Paul McCartney from Album = Chaos and Creation in the Backyard Released = 2006 Format = Promo CD Recorded = 2003 2005 Genre = Rock Length = 3:26 (album version) 3 …   Wikipedia

  • This Never Happened Before — «This Never Happened Before» Sencillo de Paul McCartney del álbum Chaos and Creation in the Backyard Formato Promo CD Grabación 2003 2005 Género(s) Rock D …   Wikipedia Español

  • before — [[t]bɪfɔ͟ː(r)[/t]] ♦ (In addition to the uses shown below, before is used in the phrasal verbs go before and lay before .) 1) PREP If something happens before a particular date, time, or event, it happens earlier than that date, time, or event.… …   English dictionary

  • Before Sunset — Infobox Film | name = Before Sunset caption = Before Sunset film poster imdb id = 0381681 director = Richard Linklater writer = Richard Linklater, Ethan Hawke, Julie Delpy | starring = Ethan Hawke, Julie Delpy music = Julie Delpy cinematography …   Wikipedia

  • Before the Devil Knows You're Dead — Infobox Film name = Before the Devil Knows Youre Dead image size = caption = Theatrical release poster director = Sidney Lumet producer = nowrap|Michael Cerenzie Brian Linse William S. Gilmore Paul Parmar writer = Kelly Masterson narrator =… …   Wikipedia

  • before — conj., prep., & adv. conj. 1 earlier than the time when (crawled before he walked). 2 rather than that (would starve before he stole). prep. 1 a in front of (before her in the queue). b ahead of (crossed the line before him). c under the impulse… …   Useful english dictionary

  • before your time — 1) often humorous used for saying that something happened or existed before you were born These styles were a bit before my time. 2) used for talking about things that existed in a place before you lived or worked there She was a manager here,… …   English dictionary

Share the article and excerpts

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