Arrivé-avant

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.

Note et références

(en) Cet article est partiellement ou en totalité issu de l’article en anglais intitulé « Happened-before » (voir la liste des auteurs)

  1. ↑ (en) Leslie Lamport, « Time, Clocks, and the Ordering of Events in a Distributed System », dans Communications of the ACM (en), vol. 21, no 7, juillet 1978 

Wikimedia Foundation. 2010.

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

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Arrive-avant — 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

  • avant — 1. avant [ avɑ̃ ] prép. et adv. • 842; lat. imp. abante; de ab et ante « avant » I ♦ Prép. (Opposé à après, I) 1 ♦ Priorité de temps, antériorité (cf. Anté , anti , pré ). Avant le jour. « L affût du matin un peu avant le lever du soleil » (A.… …   Encyclopédie Universelle

  • arrivé — arrivé, ée [ arive ] adj. • de arriver 1 ♦ Premier, dernier arrivé : celui qui est arrivé le premier, le dernier. « il n a pu faire autrement que de servir d abord les premiers arrivés » (A. Gide). 2 ♦ Qui a réussi (socialement,… …   Encyclopédie Universelle

  • avant-hier — [ avɑ̃tjɛr ] adv. • 1220; avant ier v. 1170; de 1. avant et hier ♦ Dans le jour qui a précédé hier. Il est parti avant hier. ⇒aussi avant veille. ● avant hier adverbe Le jour qui a précédé la veille du jour où l on est …   Encyclopédie Universelle

  • avant-dernier — avant dernier, ère (a van dèr nié, niê r ) adj. Qui est avant le dernier. L avant dernier jour du mois. Les avant derniers paragraphes des deux chapitres consécutifs.    Substantivement. Il est arrivé l avant dernier. ÉTYMOLOGIE    Avant et… …   Dictionnaire de la Langue Française d'Émile Littré

  • avant-coureur — AVANT COUREUR. s. m. Celui qui va devant quelqu un, et qui en marque par avance l arrivée. Les Tartares sont ordinairement les avant coureurs de l armée des Turcs. f♛/b] En parlant Des Prophètes qui ont annoncé, qui ont prédit la venue de… …   Dictionnaire de l'Académie Française 1798

  • avant-mur — ⇒AVANT MUR, subst. masc. A. ARCHIT. Mur adossé à un autre mur (cf. CHESN. 1857, BARB. CAD. 1963). Spéc., HÉRALD. ,,Pan de muraille joint à une tour (Ac. Compl. 1842). B. FORTIF. Enceinte de murailles la plus éloignée du corps de la place (cf.… …   Encyclopédie Universelle

  • avant-hier — AVANT HIER. Adverbe de temps, qui marque l Avant veille du jour où l on est. Il partit avant hier. Il est arrivé d avant hier …   Dictionnaire de l'Académie Française 1798

  • Avant la noce — est une nouvelle d’Anton Tchekhov (en russe : Pered svadboï). Sommaire 1 Historique 2 Résumé 3 Extraits 4 Personnages …   Wikipédia en Français

  • Avant d'aller dormir chez vous — est un livre du genre autobiographique écrit par Antoine de Maximy et paru en 2008 aux éditions Florent Massot. Résumé L ouvrage est décliné en 4 parties, la première narrant l enfance de Maximy, la seconde pour ses débuts dans l audio vidéo, une …   Wikipédia en Français

Share the article and excerpts

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