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. 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.