Horloge de Lamport

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Article principal : horloge logique.

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[modifier | modifier le code]

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[modifier | modifier le code]

  1. (en) Leslie Lamport, « Time, Clocks, and the Ordering of Events in a Distributed System », Communications of the ACM, vol. 21, no 7,‎ 1978, p. 558-565 (lire en ligne [PDF])