Corrigé - Algorithmes distribués

Exercice 1 - Algorithme de Chandy et Lamport

Question 1.1 - Tableau d'exécution

Note : Le tableau complet d'origine étant partiellement altéré par l'extraction du document source, nous reconstituons ici la logique des événements majeurs de l'algorithme de Chandy et Lamport à partir des éléments lisibles du corrigé, sans inventer de données non fournies.

Dans l'algorithme de Chandy et Lamport, l'enregistrement de l'état global suit des règles strictes lors de la réception d'un marqueur (mk) :

• À la première réception d'un marqueur, un processus enregistre son état local, marque le canal d'arrivée comme vide, diffuse un marqueur sur ses canaux sortants, et commence à enregistrer les messages entrants sur ses autres canaux.
• Aux réceptions suivantes d'un marqueur sur un autre canal, il arrête l'enregistrement sur ce canal et sauvegarde la séquence de messages reçus.

Voici l'analyse des événements clés de la capture d'état :

• Evénement e1 (sur P2) : P2 initie la capture d'état.
  • Action : enreg. el2, D(mk2). P2 enregistre son état local el2 et diffuse le marqueur mk2 vers P1 et P3. La variable enreg_état2 passe à VRAI.
• Evénement e5 (sur P1) : P1 reçoit le marqueur mk2 de P2 pour la première fois.
  • Action : R(mk2), D(mk1), enreg. el1. P1 enregistre son état local el1.
  • Canaux : L'état du canal C(2) est fixé à vide (reçu(2) passe à VRAI). P1 commence à écouter C(3) (reçu(3) est FAUX).
• Evénement e8 (sur P3) : P3 reçoit le marqueur mk2 de P2 pour la première fois.
  • Action : R(mk2), D(mk3), enreg. el3. P3 enregistre son état local el3.
  • Canaux : L'état du canal C(2) est fixé à vide (reçu(2) passe à VRAI). P3 commence à écouter C(1) (reçu(1) est FAUX).
• Evénement e10 (sur P1) : P1 reçoit le message M2.
  • Action : R(M2). Puisque l'enregistrement sur C(3) est en cours (reçu(3) = FAUX), M2 est ajouté à l'état sauvegardé du canal.
• Les événements ultérieurs (e11, e12, e13, e14) correspondent aux réceptions des autres marqueurs (R(mk3) ou R(mk1)) qui viennent clôturer l'enregistrement sur les canaux restants (passage de l'état reçu à VRAI) et déclencher l'envoi de l'état au processus collecteur Pc.

Question 1.2 - État des canaux

Le processus collecteur Pc recueille l'état global, qui inclut l'état des canaux de communication. Un message appartient à l'état du canal cij (allant du processus Pi vers le processus Pj) s'il a été envoyé par Pi avant l'enregistrement de son état local, et reçu par Pj après l'enregistrement de l'état local de Pj.

D'après le corrigé, l'état des canaux reçus par Pc est le suivant :

cij	i=1 (Émetteur P1)	i=2 (Émetteur P2)	i=3 (Émetteur P3)
j=1 (Récepteur P1)		{M3}	{M2}
j=3 (Récepteur P3)	{M1}
j=2 (Récepteur P2)

• c21 = {M3} : Le message M3 a été envoyé par P2 avant la capture de son état local (e1), mais reçu par P1 après la capture de son propre état (e5).
• c31 = {M2} : Le message M2 a été envoyé par P3 avant e8, et reçu par P1 à l'événement e10 (qui est postérieur à e5).
• c13 = {M1} : Le message M1 a été envoyé par P1 avant e5, et reçu par P3 après la capture de son état (e8).

Exercice 2 - Coupures cohérentes et estampillage vectoriel de Lamport

Question 2.1 - Estampillage vectoriel

Les règles de l'estampillage vectoriel de Lamport pour n processus stipulent que :

1. Chaque processus Pi incrémente son propre compteur EV[i] à chaque événement.
2. Lors de la réception d'un message, Pi met à jour son horloge en prenant le maximum composante par composante entre son horloge locale et l'horloge jointe au message, puis incrémente EV[i].

À partir des données du corrigé, voici la reconstitution des estampilles pour chaque événement, regroupées par processus :

Processus P1 :

• e4 : (1, 0, 0)
• e5 : (2, 1, 0)
• e7 : (3, 1, 0)
• e10 : (4, 1, 2)
• e15 : (5, 1, 3)

Processus P2 :

• e1 : (0, 1, 0)
• e6 : (0, 2, 1)
• e9 : (1, 3, 1)
• e11 : (1, 4, 3)
• e14 : (2, 5, 3)

Processus P3 :

• e2 : (0, 0, 1)
• e3 : (0, 0, 2)
• e8 : (0, 1, 3)
• e12 : (2, 1, 4)
• e13 : (3, 1, 5)

Question 2.2 - Cohérence de la coupure globale

La coupure correspondant aux états locaux enregistrés par l'algorithme est C1 = (e5, e1, e8).

Le vecteur caractérisant cette coupure se construit en prenant la i-ème composante de l'événement du processus Pi : EV(C1) = (2, 1, 3).

Vérifions les estampilles vectorielles des trois événements :

• EV(e5) = (2, 1, 0)
• EV(e1) = (0, 1, 0)
• EV(e8) = (0, 1, 3)

Une coupure est cohérente si et seulement si l'estampille de la coupure est égale au maximum des estampilles de ses événements. Calculons le maximum composante par composante : Max( (2,1,0), (0,1,0), (0,1,3) ) = (2, 1, 3).

On a bien EV(C1) = Max (EV(Ci)) pour i = 5, 1, 8. La coupure est donc cohérente.

Question 2.3 - Exemple de coupure incohérente

Le corrigé propose la coupure C2 = (e10, e6, e2).

Son vecteur associé est EV(C2) = (4, 2, 1), formé par la 1ère composante de e10, la 2ème de e6 et la 3ème de e2.

Vérifions les estampilles :

• EV(e10) = (4, 1, 2)
• EV(e6) = (0, 2, 1)
• EV(e2) = (0, 0, 1)

Calculons le maximum : Max( (4,1,2), (0,2,1), (0,0,1) ) = (4, 2, 2).

Ici, nous observons que EV(C2) < Max (EV(Ci)) pour i = 10, 6, 2, car la troisième composante diffère : (4, 2, 1) < (4, 2, 2). La composante "2" provenant de l'événement e10 montre que P1 a déjà connaissance d'un événement de P3 qui s'est produit après e2 (en l'occurrence e3). La coupure capture donc la réception d'un message dont l'émission n'est pas incluse dans la coupure. La coupure est incohérente.

Question 2.4 - Preuve de cohérence (canaux FIFO)

Il s'agit de démontrer par l'absurde que l'état global (el1, el2, ... eln) renvoyé par l'algorithme constitue toujours une coupure cohérente, sous l'hypothèse de canaux FIFO (First-In, First-Out).

Preuve :

1. Supposons que la coupure correspondant aux états (el1, el2, ... eln) n'est pas cohérente.
2. Par définition de l'incohérence, cela signifie qu'il existe un processus Pi (avec i ∈ [1, n]) dont l'état eli contient un événement eix (la réception d'un message M), alors que l'état elj du processus émetteur Pj ne contient pas l'événement d'émission ejy de ce même message M.
3. Puisque ejy n'est pas capté dans elj, l'événement ejy s'est produit après l'enregistrement de l'état elj.
4. Dans l'algorithme, un processus envoie son marqueur (mkj) exactement au moment où il enregistre son état. Donc, l'envoi du marqueur mkj par Pj est antérieur à l'émission du message M (qui correspond à ejy).
5. Par hypothèse, les canaux de communication sont FIFO. Ainsi, tout message envoyé avant un autre arrivera avant lui. Le marqueur mkj doit donc arriver au processus Pi avant le message M.
6. Selon les règles de l'algorithme, si Pi reçoit un marqueur pour la première fois, il doit immédiatement enregistrer son état local (s'il ne l'a pas déjà fait). L'enregistrement de l'état eli est donc garanti d'être antérieur à la réception du message M.
7. Par conséquent, l'événement eix (réception de M) se produit après l'enregistrement eli, et ne peut donc pas être inclus dans eli.

Nous aboutissons à une contradiction directe avec notre prémisse (qui posait que eix était dans eli). L'hypothèse de départ est donc fausse : la coupure ne peut pas être incohérente.

Méthode

Face à un problème d'algorithmique distribuée avec capture d'état, la priorité absolue est de retracer la chronologie causale. Les horloges vectorielles sont votre meilleur outil : elles ne mentent jamais sur l'ordre partiel des événements. Ne vous laissez pas déstabiliser par un diagramme complexe. Avant de tenter de remplir un tableau d'états de canaux, listez systématiquement l'horloge vectorielle de chaque événement. La règle de cohérence (le vecteur de la coupure doit égaler le maximum des vecteurs des événements qui la composent) permet de valider vos déductions mathématiquement, sans ambiguïté.