Horloge de Lamport
- Horloge de Lamport
-
Une horloge de Lamport est un dispositif logiciel introduit en 1978 par Leslie Lamport[1] afin de donner à chaque processus d'un système distribué asynchrone des informations sur la relation de causalité arrivé-avant. C'est le premier type d'horloge logique introduit en informatique.
Principe
Chaque processus possède un entier appelé estampille. Il est mis à jour selon les règles suivantes :
- un évènement interne provoque l'incrémentation de l'estampille ;
- tout message envoyé porte l'estampille courante de l'émetteur ;
- lors de la réception d'un message, l'estampille prend la valeur 1 + max(estampille du message, estampille courante du récepteur).
En conséquence, si deux événements a et b sont tels que a → b (a précède b), alors l'estampille de a est inférieure à celle de b. En revanche, la réciproque est fausse. Les horloges vectorielles capturent totalement la relation → au prix d'une occupation de mémoire plus importante.
Les horloges logiques sont utilisées dans de nombreux algorithmes, notamment d'exclusion mutuelle dans le cas de systèmes distribués.
Notes et références
- ↑ (en) Leslie Lamport, « Time, Clocks, and the Ordering of Events in a Distributed System », dans Communications of the ACM, vol. 21, no 7, 1978, p. 558-565 [texte intégral [PDF]]
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Horloge de Lamport de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Horloge logique — Une horloge logique est un dispositif logiciel qui sert à établir et mesurer une notion de temps établie selon la relation de causalité arrivé avant dans un système réparti asynchrone. Différents types d horloges logiques existent et fournissent… … Wikipédia en Français
Horloge vectorielle — Article principal : horloge logique. Une horloge vectorielle est un dispositif logiciel introduit indépendamment en 1988 par Colin Fidge[1] et Friedemann Mattern[2] afin de donner à chaque processus d un système distribué asynchrone des… … Wikipédia en Français
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é asynchrone. Elle… … Wikipédia en Français
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
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
Algorithme de Ricart et Agrawala — L Algorithme Ricart Agrawala est un algorithme d exclusion mutuelle sur un système distribué. Cet algorithme est une extension et une optimisation de l algorithme de Lamport, en supprimant la nécessité de communiquer un messages de libération. Il … Wikipédia en Français
Parallélisme (informatique) — Pour les articles homonymes, voir parallèle. Blue Gene L cabinet., un des ordinateurs massivement parallèle les plus rapides des années 2000 En informatiqu … Wikipédia en Français
Modèle Byzantine Altruistic Rational — Le modèle Byzantine Altruistic Rational (qui signifie en Anglais « byzantin, altruiste, rationnel », plus communément appelé modèle BAR) est un modèle mathématique de sécurité informatique, utilisé dans les systèmes distribués afin de… … Wikipédia en Français
