Gestion du temps et des états dans les systèmes distribués

Cette conférence traite de la gestion du temps et des états dans les systèmes distribués, un sujet fondamental pour comprendre comment coordonner des processus répartis sans accès à un temps global unique. Elle s'inscrit dans un cours sur les systèmes distribués et aborde les concepts de causalité, d'horloges logiques et vectorielles, ainsi que la construction d'états globaux cohérents.

Introduction à la gestion du temps dans les systèmes distribués

Les systèmes distribués sont caractérisés par une latence importante due aux délais de communication, qui sont à la fois significatifs et variables. Ces variations peuvent entraîner des exécutions différentes d’un même protocole, avec des résultats divergents. Par exemple, un chef peut envoyer un message pour ouvrir une vanne, puis un autre pour la fermer quelques minutes plus tard. Selon les délais de transfert, la quantité de liquide peut varier. De plus, la duplication de messages dans le canal de transmission peut compliquer davantage la gestion.

Dans un système distribué, les événements correspondent à tout changement d’état. L’ordre de ces événements est crucial, notamment pour assurer des mécanismes comme l’exclusion mutuelle. Deux événements ne peuvent pas avoir lieu exactement au même instant, et un observateur externe suffisamment précis peut toujours déterminer lequel précède l’autre. Cependant, les processus n’ont accès qu’à des horloges locales, souvent mal synchronisées, ce qui rend difficile la définition d’un ordre global précis. De plus, deux processus différents peuvent percevoir des ordres d’événements différents, posant des problèmes de décisions cohérentes.

Relation de causalité et ordre causal

Le principe de causalité stipule qu’un effet ne peut précéder sa cause. Dans les systèmes distribués, il est essentiel de respecter ce principe pour éviter des incohérences graves. Par exemple, l’envoi d’un message précède toujours sa réception.

La relation d’ordre causal, notée “→”, est définie par trois règles :

• Ordre local : a→b si a et b sont générés dans cet ordre sur un même site.
• Causalité élémentaire : a→b si a est l’envoi et b la réception d’un même message.
• Transitivité : si a→b et b→c alors a→c.

Cette relation est un ordre partiel, car certains événements sont concurrents, c’est-à-dire impossibles à classer causalement.

On distingue la concurrence physique (événements se produisant simultanément) de la concurrence logique (absence de relation causale). Deux événements peuvent être logiquement concurrents même s’ils ne sont pas physiquement simultanés. L’ordre d’exécution des événements concurrents logiques n’affecte pas le résultat des interactions entre processus.

Ordonnancement des événements et horloges logiques

Pour que tous les processus partagent le même ordre sur les événements qui les concernent, on leur associe des dates via des horloges. Ces horloges doivent respecter :

• Monotonie : l’horloge doit toujours avancer, même lors de corrections.
• Cohérence : si a→b alors H(a) < H(b).

Les horloges logiques permettent aux processus de distinguer les événements concurrents des événements ordonnés. L’objectif est d’établir un ordre total compatible avec la causalité.

Algorithme de l’horloge logique de Lamport

Chaque site Si maintient une variable Hi initialisée à 0. Les règles sont :

1. À chaque événement local sur Si : Hi ← Hi + 1;
2. Lors de l’émission d’un message, Hi est incrémenté et le message est estampillé par H(m) ← Hi;
3. À la réception d’un message m : Hi ← max(Hi, H(m)) + 1;

Cet algorithme garantit un ordre total sur les événements, noté “<<”, défini par :

a << b si H(a) < H(b) ou si H(a) = H(b) et le site de a est inférieur à celui de b.

Par exemple, un ordre total sur des événements répartis sur trois sites peut être :

e11 << e21 << e31 << e12 << e13 << e22 << e14 << e23 << e15 << e24 << e32 << e25 << e33 << e34

Cette méthode est utilisée pour l’exclusion mutuelle, le multicast totalement ordonné et la réplication. Ses limites sont que la comparaison des dates ne permet pas toujours de déduire la causalité exacte, et que les horloges ne sont pas bornées.

Horloges vectorielles

Les horloges vectorielles améliorent la représentation de la dépendance causale. Chaque site Si maintient un vecteur Vi de taille n (nombre de sites), initialisé à zéro. Les règles sont :

1. À chaque événement local sur Si : Vi[i] ← Vi[i] + 1;
2. Lors de l’émission d’un message : Vi[i] ← Vi[i] + 1, le message est estampillé par V(m) ← Vi;
3. À la réception d’un message m : 
   Vi[i] ← Vi[i] + 1;
   Pour tout j ≠ i : Vi[j] ← max(V(m)[j], Vi[j]);

La relation d’ordre sur les vecteurs est définie par :

• V ≤ V' si ∀i, V[i] ≤ V'[i]
• V < V' si V ≤ V' et ∃i tel que V[i] ≠ V'[i]
• V || V' (concurrents) si ni V < V' ni V' < V

Les horloges vectorielles représentent exactement la dépendance causale :

• a → b ⇔ Va < Vb
• a || b ⇔ Va || Vb

Contrairement aux horloges logiques, elles ne définissent pas un ordre total.

Chaque composante Vi[i] compte le nombre d’événements précédant un événement donné sur le site Si.

Applications et limites des horloges vectorielles

• Applications : détermination des événements concurrents, multicast causalement ordonné, vérification de la cohérence des points de reprise.
• Limites : nécessité de transporter les vecteurs avec tous les messages, problème de passage à l’échelle lorsque le nombre de processus est grand, horloges non bornées.

Gestion de l’état global dans un système distribué

Chaque processus Si possède un état local eli, résultant de son état initial et de la séquence des événements sur ce site. Chaque canal de communication cij entre Si et Sj a pour état ecij l’ensemble des messages en transit (émis par Si et non encore reçus par Sj).

Les actions modifiant l’état global sont :

• Événement interne à Si : modification de eli
• Envoi d’un message m de Si vers Sj : cij ← cij ∪ {m}
• Réception d’un message m envoyé de Sj vers Si : cij ← cij − {m}

L’état global du système est la somme des états locaux et des états des canaux :

État global = Σ eli + Σ ecij

Exemple introductif

Un jeton circule entre trois sites S1, S2 et S3. À tout instant, le jeton est soit sur un site, soit en transit dans un canal. Si S3 interroge le système sur le nombre de jetons, il peut recevoir une réponse erronée indiquant deux jetons en circulation, ce qui est incohérent avec la réalité. Cela illustre la difficulté de construire une vision cohérente de l’état global à partir de vues locales prises à des instants différents.

Concept de coupure cohérente

Une coupure est un ensemble d’événements contenant au moins un événement par site. Elle est dite cohérente si elle est fermée par la relation de dépendance causale. Formellement, une coupure C est cohérente si :

(a ∈ C et a → b) ⇒ b ∈ C

Autrement dit, si un événement appartient à la coupure, alors tous les événements qui en dépendent causalement doivent aussi y appartenir.

La date d’une coupure C = (c1, ..., cn) est définie par le vecteur :

V(C) = sup(V(c1), ..., V(cn))

où V(ci) est l’horloge vectorielle associée à l’événement ci.

Une coupure est cohérente si :

V(C) = (Vc1[1], ..., Vci[i], ..., Vcn[n])

Un exemple montre que certaines coupures ne sont pas cohérentes car la composante d’un vecteur ne respecte pas la fermeture causale.

Algorithme de Chandy-Lamport pour la capture d’état global

Pour construire un état global cohérent, l’algorithme de Chandy-Lamport utilise un marqueur envoyé par un processus Si :

1. Si enregistre son état local.
2. Pour chaque canal sortant cix, Si envoie un marqueur avant tout autre message.

À la réception d’un marqueur par Sj via le canal cxj :

1. Si Sj n’a pas encore enregistré son état, il le fait et envoie à son tour des marqueurs sur ses canaux sortants.
2. Sinon, Sj met à jour l’état du canal cxj en enregistrant les messages reçus après l’enregistrement de son état et avant la réception du marqueur.

Dans l’exemple, le jeton est capturé dans l’état du canal ec12. Ensuite, les processus échangent leurs états locaux et les états des canaux enregistrés pour construire l’état global cohérent.

Points clés

• Les systèmes distribués sont caractérisés par des délais de communication variables qui compliquent la gestion du temps et des états.
• La relation de causalité impose que l’effet ne précède jamais la cause, ce qui est fondamental pour la cohérence des systèmes distribués.
• L’ordre causal est un ordre partiel sur les événements, distinguant événements ordonnés et événements concurrents.
• Les horloges logiques (Lamport) permettent d’établir un ordre total compatible avec la causalité, mais ne reflètent pas toujours la dépendance causale exacte.
• Les horloges vectorielles représentent précisément la dépendance causale et permettent d’identifier les événements concurrents, mais ne définissent pas un ordre total.
• L’état global d’un système distribué est la combinaison des états locaux et des messages en transit, et sa construction cohérente est complexe.
• Une coupure cohérente respecte la fermeture causale et peut être caractérisée par un vecteur d’horloges vectorielles.
• L’algorithme de Chandy-Lamport permet de capturer un état global cohérent en synchronisant les enregistrements d’état locaux et des canaux.