Systèmes Répartis: Horloges Logiques

Un système distribué est composé de plusieurs processus qui peuvent communiquer entre eux via des canaux de communication. Chaque nœud possède un seul processus et peut communiquer avec d'autres nœuds via des canaux.

Un système synchrone suppose que les processus sont synchronisés dans le temps et que la communication est instantanée. Un système asynchrone n'a pas de synchronisation temporelle et la communication peut être retardée.

Un événement est une action qui se produit dans un processus. L'état d'un système distribué est l'ensemble des événements qui se sont déjà produits.

Le temps logique est une mesure relative du temps dans un système distribué. Une horloge logique est un mécanisme utilisé pour ordonner les événements dans un système distribué en utilisant le temps logique.

La délivrance FIFO garantit que les messages arrivant à un processus sont traités dans l'ordre d'envoi. La délivrance causale garantit que les messages causés par d'autres événements sont reçus avant les événements qui dépendent de ces messages.

L'horloge scalaire de Lamport attribue une estampille à chaque événement, composée du numéro du processus et du numéro de l'événement. Elle assure l'ordonnancement partiel des événements, mais pas la délivrance causale.

L'horloge vectorielle de Mattern utilise un vecteur de taille égale au nombre de processus pour maintenir les estampilles des événements. Elle assure la dépendance causale et peut détecter les événements concurrents.

Une horloge matricielle est une extension de l'horloge vectorielle qui utilise une matrice pour maintenir les estampilles des événements. Elle offre une plus grande précision pour l'ordonnancement et la détection des événements concurrents.

La valeur initiale de chaque élément de la matrice est 0.

Quand un événement local se produit dans un processus Pi, la valeur Mi[i, i] est incrémentée de 1.

Quand un message est envoyé de Pi à Pj, Mi[i, i] et Mi[i, j] sont incrémentées de 1.

Le message m porte l'estampille matricielle de l'émetteur Pi, ce qui signifie que Mm = Mi.

Le récepteur Pj retarde le traitement du message m jusqu'à ce que deux conditions soient remplies.

La première condition assure que Pj a reçu tous les messages de Pi précédant m.

La deuxième condition garantit que Pj a reçu tous les messages envoyés avant l'envoi de m.

L'horloge de Mattern est un algorithme d'horloges logiques qui attribue des horodatages aux événements dans un système distribué, permettant ainsi de déterminer l'ordre partiel des événements.

Chaque processus possède un vecteur d'horloges Vi. Vi[i] représente le compteur local pour Pi et Vi[j] représente la connaissance de Pi sur le nombre d'événements de Pj.

Lorsqu'un événement local se produit sur Pi, le compteur Vi[i] est incrémenté. Chaque message envoyé par Pi contient l'estampille Vi.

Lors de la réception d'un message Vm par Pj, Pj met à jour son vecteur d'horloges Vi. Vj[j] est incrémenté et Vj[k] prend la valeur maximale entre sa valeur actuelle et Vm[k] pour tout k différent de j.

L'ordre partiel des événements peut être déduit à partir des horodatages. Vk: Vi[k] ≤ Vj[k] implique que l'événement de Pi est avant l'événement de Pj. Si Vi ≤ Vj et Vi[r] < Vj[r] alors Vi < Vj, signifiant que l'événement de Pi est avant l'événement de Pj. Si Vi < Vj et Vj < Vi sont tous deux faux, alors l'ordre est inconnu et les événements sont considérés comme parallèles. Les événements parallèles sont représentés par '||'.

Les horloges de Mattern ne permettent pas de définir un ordre global total pour tous les événements, ni de garantir une délivrance causale des messages. Par exemple, deux processus peuvent recevoir des messages sans que l'un n'ait connaissance de l'autre. L'ordre des événements est alors indéterminé.

Chaque processus Pi maintient une matrice Mi[n,n]. Mi[i,i] représente le nombre d'événements qui se sont produits localement sur Pi. Mi[i,j] représente le nombre de messages que Pi a envoyés à Pj. Mi[j,j] est le nombre d'événements de Pj que Pi connaît. Mi[j,k] est le nombre de messages envoyés par Pj à Pk que Pi connaît.