Horloge matricielle
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 d'un système de 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 événement 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
Source
Article de Raynal et Singhal (anglais) : [PDF] « Initiation au temps logique », sur http://www.ics.uci.edu/ (consulté le )