- Horloge vectorielle
-
Article principal : horloge logique.
Une horloge vectorielle est un dispositif logiciel introduit indépendamment en 1988 par Colin Fidge[1] et Friedemann Mattern[2] afin de donner à chaque processus d'un système distribué asynchrone des informations sur la relation de causalité arrivé-avant.
Sommaire
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] ;
- tout message envoyé porte l'estampille courante ;
- 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] \leq 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 envoye 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 mis à 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
Notes et références
- (en) Colin J. Fidge, « Timestamps in Message-Passing Systems that Preserve the Partial Ordering », dans Proceedings of the 11th Australian Computer Science Conference, 1988, p. 56-66 [texte intégral [PDF]]
- (en) Friedemann Mattern, « Virtual Time and Global States of Distributed Systems », dans Proceedings of the Workshop on Parallel and Distributed Algorithms, 1989, p. 215-226 [texte intégral [PDF]]
Wikimedia Foundation. 2010.
