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 $j \neq 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_1 \prec C_2$ si et seulement si les deux conditions suivantes sont vérifiées :

$\forall i, C_1[i] \leq C_2[i]$ ;
$\exists i, C_1[i] < C_2[i]$ .

Si $C_1 \not\prec C_2$ et $C_2 \not\prec C_1$ , alors $C_1 \parallel C_2$ (les deux horloges ne sont pas comparables).

Les horloges vectorielles capturent totalement la relation $\to$ : pour deux événements $a$ et $b$ , $a \to b$ si et seulement si l'estampille de $a$ est inférieure à celle de $b$ . D'autre part, $C_1 \parallel C_2$ 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 $\to$ en utilisant des horloges vectorielles, il est parfois nécessaire d'utiliser des dispositifs plus élaborés : les horloges matricielles.