Horloge de Lamport
Pour les articles homonymes, voir 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 modifier
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
- (en) Leslie Lamport, « Time, Clocks, and the Ordering of Events in a Distributed System », Communications of the ACM, vol. 21, no 7, , p. 558-565 (lire en ligne [PDF])
