|
Horloge vectorielleUne 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. PrincipeChaque 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 :
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 :
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. ExempleSoit 3 processus, p1, p2, p3. Chacun a son estampille, chacune composée de trois numéros ou dates, les trois correspondant à chaque processus :
Imaginons qu'il se produise un évènement interne à p1. Les estampilles deviendront :
Imaginons maintenant que p1 envoie un message à p3. À l'émission, les estampilles deviendront :
Le message portera comme estampille [2, 0, 0], qui correspond à l'estampille de p1 lors de l'émission. À la réception, les estampilles deviendront :
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 Notes et références
|
