Happened-before

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:
* If events a ; and b ; occur on the same process, a o b if the occurrence of event a ; preceded the occurrence of event b ;.
* If event a ; is the sending of a message and event b ; is the reception of the message sent in event a ;, a o b.
* Transitivity property: for three events a ;, b ;, and c ;, if a o b and b o c, then a o c.

The happened-before relation is "irreflexive" and "antisymmetric", i.e.:
* forall a, a ot o a (irreflexivity) ;
* forall a, b such that a eq b, if a o b then b ot o a (antisymmetry).

The processes that make up a distributed system have no knowledge of the happened-before relation unless they use a logical clock, like a Lamport clock or a vector clock. This allows to design algorithms for mutual exclusion and tasks like debugging or optimising distributed systems.

ee also

* Java Memory Model


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • 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

  • 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”