Horloge matricielle

Article principal : horloge logique.

Une horloge matricielle est un dispositif logiciel qui donne à chaque processus d'un système distribué asynchrone des informations sur la relation de causalité arrivé-avant.

Principe

Chaque processus p d'un système de n processus possède une matrice n ⨯ n d'entiers appelée estampille dans laquelle chaque composant estampille[i] est l'estimation par p de la valeur de l'horloge vectorielle du processus i. En particulier, estampille[p] est exactement l'horloge vectorielle de p. Elle est mise à jour selon les règles suivantes :

• un évenement interne provoque l'incrémentation d'estampille[p][p] ;
• tout message envoyé porte l'estampille courante ;
• lors de la réception d'un message m envoyé par un processus q portant l'estampille e, l'horloge vectorielle estampille[p] est mise à jour en utilisant e[q]. Ensuite, pour tous i,j ∈ [1..n], estampille[i,j] prend la valeur max(estampille[i,j],e[i,j]). Enfin, estampille[p][p] est incrémenté.

Comme les horloges matricielles incluent des horloges vectorielles, elles en possèdent toutes les propriétés. Elles apportent en plus la connaissance pour un processus de la perception du temps logique par les autres processus. Ainsi, par exemple, p peut constater que tous les autres processus estiment que son horloge logique a dépassé une certaine valeur. Ceci permet à p de prendre des mesures adaptées, comme libérer une zone de mémoire qu'il devait conserver tant qu'un autre processus pouvait en avoir besoin.

Le coût en mémoire par message envoyé des horloges vectorielles est en Θ(n²), où n est le nombre de processus du système, ce qui est souvent trop élevé. Diverses techniques existent pour le réduire, notamment celle de Singhal et Kshemkalyani : n'envoyer sur chaque message que les composantes de l'estampille qui ont changé depuis le dernier message envoyé au même destinataire.

Voir aussi

• Arrivé-avant
• Horloge logique
• Horloge vectorielle

Source

Article de Raynal et Singhal (anglais) : [PDF] Initiation au temps logique sur http://www.ics.uci.edu/. Consulté le 23 janvier 2008