Horloge logique

Un article de Wikipédia, l'encyclopédie libre.

Une horloge logique, ou 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.

[modifier] 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 ;
• lors de la réception d'un message, l'estampille prend la valeur 1 + max (estampille du message, estampille courante).

En conséquence, si deux événements a et b sont tels que , alors l'estampille de a est supé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.

[modifier] Notes et références

• Portail de l’informatique