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 dans l'étude des interactions entre processus répartis sur plusieurs sites. Elle s'inscrit dans un cours sur les systèmes distribués et aborde les notions 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 et variable due aux moyens de communication entre sites. Cette variabilité des délais peut 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 transmission, la quantité de liquide transférée peut varier. De plus, des messages peuvent se dédoubler dans le canal, compliquant encore la gestion des états.

Événements et ordre dans un système distribué

Un événement est défini comme tout changement d’état dans un système. L’ordre des événements est crucial, notamment pour assurer des mécanismes comme l’exclusion mutuelle. Deux événements ne peuvent se produire exactement au même instant, et un observateur externe suffisamment précis peut toujours déterminer lequel précède l’autre.

Dans un système distribué, chaque processus dispose uniquement d’une horloge locale, plus ou moins synchronisée, ce qui rend difficile la définition d’un ordre global précis des événements. De plus, deux processus différents peuvent percevoir des ordres et des dates d’événements divergents, ce qui pose des problèmes de décisions cohérentes.

Il est cependant essentiel que l’ordre des événements soit le même pour tous les processus, même si cet ordre diffère de celui observé par un observateur externe. Par exemple, dans un système bancaire répliqué sur trois sites, des opérations de mise à jour concurrentes peuvent entraîner des soldes différents selon l’ordre perçu des messages.

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 primordial de respecter ce principe pour éviter des incohérences graves. Par exemple, l’envoi d’un message sur un site doit précéder sa réception sur un autre site.

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 : certains événements sont dits concurrents car ils ne peuvent être ordonnés par cette relation.

Concurrence physique et logique

Deux événements sont en concurrence physique s’ils se produisent simultanément dans le temps réel. Ils sont en concurrence logique s’ils ne sont pas liés par une relation de causalité, même s’ils ne sont pas simultanés physiquement. L’ordre d’exécution des événements en concurrence logique n’affecte pas le résultat des interactions entre processus.

Ordonnancement des événements distribués et horloges

Pour permettre aux processus d’interagir sans conflit, il faut que tous partagent le même ordre sur les événements qui les concernent. Cet ordre est établi en associant une date à chaque événement à l’aide d’horloges.

Les horloges doivent respecter deux propriétés :

• Monotonie : l’horloge ne doit jamais reculer, et les corrections doivent se faire par incrément.
• Cohérence : si a → b alors H(a) < H(b).

Horloges logiques de Lamport

L’algorithme de Lamport permet de réaliser une datation des événements compatible avec la causalité et définissant un ordre total sur tous les événements.

Chaque site Si maintient une variable Hi initialisée à 0. À chaque événement local, Hi est incrémenté de 1. Lors de l’émission d’un message, Hi est incrémenté et la date H(m) du message correspond à Hi. À la réception d’un message m, Hi est mis à max(Hi, H(m)) + 1.

Initialisation : Hi ← 0 ∀i
À chaque événement local sur Si : Hi ← Hi + 1;
Émission d’un message : Hi ← Hi + 1, H(m) ← Hi;
Réception d’un message m : Hi ← max(Hi, H(m)) + 1;

L’ordre défini par ces horloges est noté “<<” et est total :

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

Cet ordre permet d’ordonner tous les événements du système, ce qui est utile pour des applications comme l’exclusion mutuelle ou le multicast ordonné. Cependant, la comparaison des dates ne permet pas toujours d’inférer la causalité exacte, et les horloges ne sont pas bornées.

Horloges vectorielles

Les horloges vectorielles améliorent la précision en représentant la dépendance causale exacte entre événements. Chaque site Si maintient un vecteur Vi de taille n (nombre total de sites), initialisé à zéro.

À chaque événement local, Vi[i] est incrémenté. Lors de l’émission d’un message, Vi[i] est incrémenté et le vecteur est envoyé avec le message. À la réception d’un message m, Vi[i] est incrémenté et chaque composante Vi[j] est mise à jour avec le maximum entre Vi[j] et V(m)[j] pour j ≠ i.

Initialisation : Vi = (0, ..., 0)
À chaque événement local sur Si : Vi[i] ← Vi[i] + 1
Émission d’un message : Vi[i] ← Vi[i] + 1, V(m) ← Vi
Réception d’un message m : 
  Vi[i] ← Vi[i] + 1
  Vi[j] ← max(V(m)[j], Vi[j]) ∀ j ≠ i

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

• V ≤ V′ ssi ∀i, V[i] ≤ V′[i]
• V < V′ ssi V ≤ V′ et ∃i, V[i] ≠ V′[i]
• V || V′ ssi ni V < V′ ni V′ < V (concurrents)

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.

Applications et limites des horloges vectorielles

Les horloges vectorielles permettent de :

• Déterminer tous les événements concurrents
• Assurer un multicast causalement ordonné
• Vérifier la cohérence des points de reprise

Leur principal inconvénient est la taille du vecteur, qui doit être transportée avec chaque message, posant un problème d’échelle lorsque le nombre de processus est élevé. De plus, les horloges ne sont pas bornées.

État global d’un système distribué

Chaque processus Si possède un état local eli, résultant de son état initial et des événements locaux. Chaque canal de communication cij entre Si et Sj a pour état ecij l’ensemble des messages en transit, c’est-à-dire émis par Si mais pas encore reçus par Sj.

Les actions modifiant l’état global sont :

• Événement interne sur Si : changement 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 = Σi eli + Σi,j ecij

État global cohérent et coupures cohérentes

Un état global cohérent respecte le principe de causalité. Si l’émission d’un message est captée dans eli, alors soit sa réception est captée dans elj, soit le message est encore en transit dans cij. Inversement, si l’émission n’est pas captée, la réception ne l’est pas non plus.

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 :

Soit C une coupure, a et b deux événements. C est cohérente ssi :

(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 appartenir à la coupure.

Date et condition de cohérence d’une coupure

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 à ci.

Une coupure est cohérente si :

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

Ce vecteur doit correspondre aux composantes des horloges vectorielles des événements de la coupure. Si ce n’est pas le cas, la coupure n’est pas cohérente, ce qui permet d’identifier la source du problème.

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

L’algorithme de Chandy-Lamport permet de construire un état global cohérent dans un système distribué.

Lorsqu’un site Si envoie un marqueur :

1. Il enregistre son état local.
2. Il envoie un marqueur sur chacun de ses canaux de sortie avant d’envoyer tout autre message.

Lorsqu’un site Sj reçoit un marqueur sur un canal cxj :

1. Si Sj n’a pas encore enregistré son état, il le fait et envoie à son tour un marqueur sur ses canaux de sortie.
2. Sinon, il enregistre l’état du canal cxj comme l’ensemble des messages reçus après l’enregistrement de son état local et avant la réception du marqueur.

Cette méthode permet de capturer un état global cohérent, incluant les états locaux et les messages en transit.

Exemple d’application de l’algorithme de Chandy-Lamport

Dans un système à trois sites S1, S2 et S3, un jeton circule entre eux. En appliquant l’algorithme, le jeton peut être capté dans l’état d’un canal, par exemple ec12. Ensuite, les sites échangent leurs états locaux et les états des canaux enregistrés pour construire l’état global cohérent du système.

Points clés

• La latence et la variabilité des délais rendent difficile la gestion du temps dans les systèmes distribués.
• La relation de causalité impose un ordre partiel sur les événements, essentiel pour la cohérence.
• Les horloges logiques de Lamport fournissent un ordre total compatible avec la causalité, mais ne distinguent pas toujours la causalité exacte.
• Les horloges vectorielles représentent précisément la dépendance causale et permettent d’identifier les événements concurrents.
• La construction d’un état global cohérent nécessite de capturer les états locaux et les messages en transit selon une coupure cohérente.
• L’algorithme de Chandy-Lamport permet de capturer un état global cohérent dans un système distribué.