Horloge vectorielle
Un article de Wikipédia, l'encyclopédie libre.
Une horloge vectorielle est un dispositif logiciel introduit indépendemment 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.
[modifier] 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 logique du processus i. En particulier, estampille[p] est exactement l'horloge logique de p. Il est mis à jour selon les règles suivantes :
- un évenement 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 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 si et seulement si les deux conditions suivantes sont vérifiées :
- ;
- .
Si et , alors (les deux horloges ne sont pas comparables).
Les horloges vectorielles capturent totalement la relation : pour deux événements a et b, si et seulement si l'estampille de a est inférieure à celle de b. D'autre part, si et seulement si a et b sont indépendants.
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.
[modifier] Notes et références
- ↑ [pdf] Colin Fidge, Horloges vectorielles sur http://sky.fit.qut.edu.au/~fidgec/. Consulté le 23 janvier 2008
- ↑ [pdf] Friedemann Mattern, Horloges vectorielles sur http://people.inf.ethz.ch/mattern/. Consulté le 23 janvier 2008