Happened-before

Happened-before

Arrivé-avant

La relation arrivé-avant (anglais happened-before), notée \to, 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é asynchrone. Elle est introduite par Leslie Lamport en 1978 [1].

La relation arrivé-avant est définie ainsi:

  • Si les évènements a \; et b \; surviennent dans le même processus, a \to b si l'occurrence de a \; précède l'occurrence de b \;.
  • Si l'évènement a \; est l'émission d'un message et l'évènement b \; est la réception de ce même message, alors a \to b.
  • Transitivité: soient trois évènements a \;, b \;, et c \;, si a \to b et b \to c, alors a \to c.

Deux évènements a \; et b \; tels que a \neq b, a \not\to b et b \not\to a sont dits indépendants.

Cette notion de temps logique est fondamentale dans les systèmes distribués asynchrones car, contrairement aux systèmes synchrones, ils ne disposent pas d'une horloge centrale. La relation arrivé-avant permet de donner aux événements du système une structure de treillis.

Les processus d'un système peuvent obtenir des informations sur cette relation en utilisant des horloges de différents types :

De nombreux algorithmes reposent sur ces horloges. Leurs principales applications sont l'exclusion mutuelle, le débogage et l'optimisation de systèmes distribués et la tolérance aux défaillances.

Notes

Ce document provient de « Arriv%C3%A9-avant ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Happened-before de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

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