Algorithme de Chandy-Lamport

En informatique, l'algorithme de Chandy–Lamport est un algorithme de prise d'état qui est utilisé dans le calcul distribué pour enregistrer un état global cohérent d'un système asynchrone^[pas clair]. Il porte le nom de ses inventeurs, Leslie Lamport et K. Mani Chandy.

Histoire

D'après le site internet de Leslie Lamport, « L'algorithme de prise d'état distribué m'est venu lorsque j'ai rendu visite à Chandy, qui était alors à l'Université du Texas à Austin. Il m'a exposé le problème durant le dîner, mais nous avions tous deux bu trop de vin pour y penser clairement. Le lendemain matin, dans la douche, j'ai trouvé une solution. Lorsque je suis arrivé au bureau de Chandy, il m'attendait pour me proposer la même idée. »

Définition

L'algorithme présuppose les conditions suivantes :

• Les agents n'échouent pas et tous les messages arrivent intacts et une unique fois
• Les canaux de communication sont unidirectionnels et suivent une structure de file (premier entré, premier sorti).
• Il existe un chemin de communication entre tous les nœuds du système
• Tout processus peut commencer l'algorithme de prise d'état
• L'algorithme de prise d'état n'interfère pas avec l'exécution normale des processus
• Chaque processus enregistre son état local et l'état de ses canaux d'entrée

L'algorithme fonctionne par envoi de messages marqueurs. Chaque processus souhaitant initier une prise d'état enregistre son état local et envoie un marqueur sur chacun de ses canaux de sortie. Tous les processus, à la réception d'un marqueur, enregistrent leur état local, enregistrent l'état du canal d'où provient le marqueur comme vide et envoient des marqueurs sur tous leurs canaux de sortie. Si un processus reçoit un marqueur après avoir déjà enregistré son état local, il enregistre l'état du canal d'entrée d'où provient le marqueur comme contenant tous les messages reçus entre l'arrivée de ce marqueur et du premier marqueur ayant entraîné la prise d'état local.

Certaines des hypothèses de l'algorithme peuvent être satisfaites en utilisant un protocole de communication plus sûr, comme TCP/IP. L'algorithme peut être adapté de sorte qu'il puisse y avoir plusieurs prises d'états ayant lieu simultanément.

Algorithme

L'algorithme de Chamdy-Lamport s'exécute ainsi :

1. Le processus observateur (celui qui initie la prise d'état) :
   1. Il enregistre son état courant.
   2. Il envoie une requête de prise d'état contenant marqueur d'état.
2. Un processus recevant un marqueur d'état pour la première fois de n'importe quel message :
   1. Il envoie son état courant au processus observateur.
   2. Il ajoute à chaque message futur un marqueur d'état pour aider à la propagation.
3. Lorsqu'un processus ayant déjà effectué sa prise d'état reçoit un message qui n'a pas de marqueur d'état, il le transfère au processus observateur. Ce message a été évidemment envoyé avant que la prise d'état globale n'ait fini (car il ne porte pas de marqueur d'état, il a dû être envoyé avant que le marqueur d'état n'ait été envoyé) et doit par conséquent être inclus dans la prise d'état globale.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Chandy–Lamport algorithm » (voir la liste des auteurs).