Horloge vectorielle

Une horloge vectorielle est un dispositif logiciel introduit indépendamment en 1988 par Colin Fidge et Friedemann Mattern afin de donner à chaque processus d'un système distribué asynchrone des informations sur la relation de causalité arrivé-avant.

Principe

Chaque processus p possède un vecteur d'entiers appelé estampille dans lequel chaque composant estampille[i] est l'estimation par p de la valeur de l'horloge de Lamport du processus i. En particulier, estampille[p] est exactement l'horloge de Lamport de p. Il est mis à jour selon les règles suivantes :

• un événement interne provoque l'incrémentation d'estampille[p] ;
• avant l'envoi d'un message, estampille[p] est incrémenté et le message est envoyé avec la nouvelle valeur de l'estampille ;
• lors de la réception d'un message, chaque composante j ≠ p de l'estampille prend la valeur max(estampille[j] du message, estampille[j] courante). Ensuite, estampille[p] est incrémenté.

Pour comparer deux horloges logiques, on dit que c ≺ c' (l'estampille c précède l'estampille c') si et seulement si les deux conditions suivantes sont vérifiées :

• ∀ i, c[i] ≤ c'[i] (toute datation de site de l'estampille c est inférieure ou égale à la datation correspondante dans c'),
• ∃ i tel que c[i] < c'[i] (il existe au moins une datation strictement inférieure).

Si c ⊀ c' et c' ⊀ c, alors c ∥ c' (les deux horloges ne sont pas comparables).

Les horloges vectorielles capturent totalement la relation → : pour deux événements a et b, a → b si et seulement si l'estampille de a est inférieure à celle de b. D'autre part, a et b sont indépendants si et seulement si leurs estampilles ne sont pas comparables.

Les horloges vectorielles donnent une information plus précise que les horloges logiques pour un coût plus élevé en mémoire. Elles sont utilisées dans des algorithmes d'exclusion mutuelle, de débogage et d'optimisation de systèmes distribués.

Bien qu'il soit possible de déterminer totalement la relation → en utilisant des horloges vectorielles, il est parfois nécessaire d'utiliser des dispositifs plus élaborés : les horloges matricielles.

Exemple

Soit 3 processus, p1, p2, p3. Chacun a son estampille, chacune composée de trois numéros ou dates, les trois correspondant à chaque processus :

• estampille p1 : [0 (date pour p1), 0 (pour p2), 0 (pour p3)]
• estampille p2 : [0, 0, 0]
• estampille p3 : [0, 0, 0]

Imaginons qu'il se produise un évènement interne à p1. Les estampilles deviendront :

• estampille p1 : [1, 0, 0]
• estampille p2 : [0, 0, 0]
• estampille p3 : [0, 0, 0]

Imaginons maintenant que p1 envoie un message à p3. À l'émission, les estampilles deviendront :

• estampille p1 : [2, 0, 0]
• estampille p2 : [0, 0, 0]
• estampille p3 : [0, 0, 0]

Le message portera comme estampille [2, 0, 0], qui correspond à l'estampille de p1 lors de l'émission.

À la réception, les estampilles deviendront :

• estampille p1 : [2, 0, 0]
• estampille p2 : [0, 0, 0]
• estampille p3 : [2, 0, 1]

Sur l'estampille de p3, la date de p3 est incrémentée à la réception du message puisque la réception est un événement, tandis que la date de p1 est mise à jour à 2, en fonction du maximum entre date existante et date reçue.

Sur cet exemple, on peut dire que l'estampille de p1 précède l'estampille de p3, puisque toutes les dates de la première sont respectivement inférieures ou égales à la seconde, et qu'il en existe au moins une de strictement inférieure : celle de p3.

Liens externes

(fr) Horloges et estampilles logiques