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

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