Les fautes,
et comment
s'en remettre.

Le sujet donne un exemple à 6 processus et 17 messages. On le redessine fidèlement (mêmes checkpoints, mêmes messages, dans le même ordre sur chaque ligne), puis on applique le protocole : l'index est écrit à côté de chaque checkpoint, l'index piggybacké sur chaque message, et les checkpoints forcés ajoutés par le protocole sont en or. Règle : recevoir un index plus grand que le sien force un checkpoint avant de traiter le message.

Q1Dérouler le protocole

Tout le monde démarre à l'index 0. Chaque checkpoint local incrémente l'index. On lit chaque ligne de gauche à droite :

• m2 (P1→P0) porte 1 : P1 a pris un checkpoint local juste avant. P0 est encore à 0 → checkpoint forcé d'index 1 sur P0, avant de délivrer m2.
• P1 prend ensuite un checkpoint local et passe à 2. Ses messages suivants portent tous 2. m6 arrive sur P5 (à 1) → forcé d'index 2. m9 arrive sur P3 (à 1) → forcé d'index 2.
• m7 arrive sur P2, encore à 0 : P2 saute directement à 2. Écart de plus de 1 : ce seul checkpoint forcé tient lieu de checkpoint d'index 1 et d'index 2 pour P2 (c'est la question « et si l'écart dépasse 1 ? » des slides).
• Tous les autres messages portent un index inférieur ou égal à celui du récepteur : rien à forcer (m3 porte 0 vers P1 à 1, m11 porte 2 vers P0 à 3, m16 porte 2 vers P1 à 3...). Un index plus petit signale juste un message qui franchit une ligne vers l'avant : il sera en transit pour cette ligne.
• Bilan : 4 checkpoints forcés (P0, P2, P3, P5). À la fin, P0, P1, P2, P3 et P5 sont à l'index 3, P4 à l'index 2. Pour chaque k, les checkpoints d'index k forment une coupe cohérente : un message d'index ≥ k ne peut jamais arriver chez un processus encore sous k sans le forcer.

Q2Ce qui se passe à la reprise (P2 en panne)

P2 tombe en panne. Son dernier checkpoint est d'index 3. La reprise prend la ligne d'index 3 : le checkpoint d'index 3 de chaque processus. P4 n'a jamais atteint l'index 3, il garde son état courant (tout ce qu'il a envoyé porte au plus 2, donc aucun orphelin possible). La ligne est cohérente par construction, sans graphe de dépendances, sans effet domino.

Six messages traversent la ligne vers l'avant : m10 et m14 (vers P2), m11 (vers P0), m15 (vers P3), m16 (vers P1), m17 (vers P5). Ils sont en transit : il faut les rejouer, par exemple depuis un log côté émetteur.

Chaque processus Pi tient un index local idx, incrémenté à chaque checkpoint (local ou forcé). Tout message emporte l'index courant de son émetteur. À la réception, si l'index reçu est plus grand, on force un checkpoint avant de délivrer le message.

// etat local de Pi
idx := 0                 // index courant

checkpointLocal() :
     idx := idx + 1
     store(etat local, idx)   // checkpoint sur stockage stable

sendMsg(m, Pj) :
     send (m, idx) to Pj   // on piggyback l'index courant

ReceiveMsg(m, i) // i = index piggybacke, recu de Pj :
     if (i > idx) :
          idx := i
          store(etat local, idx)  // CHECKPOINT FORCE, avant de traiter m
     else if (i == idx) :
          // meme index : rien de force
     // (i < idx impossible d'apporter une contrainte : cf remarque)
     ProcessMessage(m)      // traitement applicatif normal

Messages en transit (bonus). Pour aussi restaurer les en-transit côté récepteur, on les ajoute au checkpoint forcé au moment où on le prend (receiver-based), et on les traite à la reprise. On le mentionne car le sujet le rend optionnel : ici on choisit de ne pas les gérer pour garder le pseudo-code lisible, l'ajout est direct.

Que faire si l'index reçu dépasse de plus de 1 ? On saute directement à cet index (idx := i) : on peut avoir « raté » des index intermédiaires, ce n'est pas un problème, un seul checkpoint forcé suffit à rejoindre la bonne coupe. Et si l'index reçu est plus petit que le sien ? Le message vient d'un checkpoint plus ancien : on n'a rien à forcer, mais cette information dit que l'émetteur est « en retard », on peut l'utiliser pour la garbage collection (les vieux checkpoints d'index inférieur sont encore utiles à quelqu'un).

Le risque : additionner naïvement checkpoints locaux (périodiques) et checkpoints forcés (induits) fait exploser le total. L'idée est de fusionner quand c'est possible, en gardant un invariant simple.

• Invariant à maintenir : il existe toujours, pour chaque processus, un checkpoint (forcé ou local) portant l'index courant. C'est cet invariant, et lui seul, qui garantit la cohérence de la ligne de recovery.
• Réutiliser plutôt que dupliquer : quand la règle réclamerait un checkpoint forcé alors qu'un checkpoint local récent existe déjà pour le bon index, on l'utilise au lieu d'en créer un nouveau. Symétriquement, un checkpoint local qui tombe juste peut jouer le rôle du forcé attendu.
• Résultat : le nombre de checkpoints forcés réellement ajoutés reste borné par le nombre de messages « incrémentant l'index » qui ne coïncident pas avec un checkpoint local. Le total (forcés + locaux) reste linéaire en le nombre d'événements, sans jamais violer « toujours un checkpoint disponible pour l'index courant ».

Intuition : on ne veut pas deux checkpoints à quelques instants d'intervalle pour le même index. Un seul suffit à la cohérence, donc on garde le premier venu (local ou forcé) et on ignore la demande redondante.

CIC et checkpointing en général

Non, la PWD n'est pas nécessaire aux protocoles de checkpointing, qu'ils soient non coordonnés, coordonnés ou CIC. Raison : le checkpointing ne rejoue pas l'exécution passée. Il restaure un état sauvegardé (une coupe cohérente) et relance une nouvelle exécution à partir de là. Cette nouvelle exécution a parfaitement le droit de diverger de l'ancienne (autres choix non déterministes, autre ordre de réception) : tant qu'on repart d'un état qui aurait pu exister sans panne, la spécification est respectée. On n'a donc jamais besoin de reproduire à l'identique les événements non déterministes.

Message logging

À l'inverse, le message logging en a absolument besoin. Son principe est de rejouer l'exécution depuis le dernier checkpoint jusqu'au point de panne, à l'identique. Sans PWD, on ne saurait pas quels événements sont non déterministes ni comment les reproduire : le rejeu produirait une exécution différente, incohérente avec l'état des processus survivants (qui, eux, ont vu l'exécution d'origine). D'où des orphelins. La PWD est la pierre angulaire qui rend le rejeu possible.

Exécution du sujet redessinée à l'identique : 4 processus, 3 ou 4 checkpoints locaux chacun, 8 messages (nommés m0 à m7 comme dans le corrigé), P1 et P3 tombent en panne à droite.

MéthodePlacer les forcés, puis trouver la ligne

Pour chaque stratégie, on ajoute un checkpoint forcé (en or) à côté de chaque envoi ou de chaque réception. Si un checkpoint local est déjà collé à l'événement (aucun autre événement entre les deux), il tient lieu de forcé. Ensuite la ligne de recovery (pointillés verts) : P1 et P3 repartent de leur dernier checkpoint, P0 et P2 de leur état courant, puis on recule tant qu'un message est reçu avant la ligne mais envoyé après (orphelin). C'est exactement le marquage par atteignabilité du graphe de dépendances (section 05).

1Checkpoint forcé AVANT l'envoi : la pire

L'émission reste hors du checkpoint. P1 repart de son forcé d'avant m3, mais m3 est déjà reçu par P0 : orphelin, P0 recule. Ce recul rend m2 orphelin, P1 recule avant m2, puis m4 fait reculer P3 avant m4, et m5 fait reculer P2 jusqu'au début. Cascade m3 → m2 → m4 → m5 : 7 checkpoints perdus, c'est l'effet domino qu'on voulait éviter. Stratégie la moins utile.

2Checkpoint forcé APRÈS l'envoi : la meilleure

L'émission est toujours dans le checkpoint. Un processus qui recule ne peut donc jamais « désenvoyer » un message déjà reçu : aucun orphelin. P1 et P3 repartent de leur dernier checkpoint, personne d'autre ne recule, 0 checkpoint perdu. La ligne est établie immédiatement après la panne. Stratégie la plus utile.

3Checkpoint forcé AVANT la réception : plutôt utile

La réception reste hors du checkpoint. P1 et P3 repartent de leur dernier checkpoint local, mais m3 et m7, envoyés après, sont déjà reçus : P0 et P2 reculent, et tombent tout de suite sur le forcé posé juste avant ces réceptions. Recul borné à un cran, 2 checkpoints perdus, pas de cascade. Utile, juste un peu moins efficace que « après l'envoi ».

4Checkpoint forcé APRÈS la réception : peu utile

La réception est toujours capturée : chaque forcé contient une réception dont l'émission peut être annulée par la reprise. P0 recule à cause de m3, P1 à cause de m2, P3 à cause de m4, P2 à cause de m7 : 6 checkpoints perdus, tous les processus reculent. Mieux que « avant l'envoi » (la cascade s'arrête avant l'état initial), mais peu utile.

L'animation de la section Snapshot déroule ce scénario. Le raisonnement :

• Comme P envoie en premier et qu'il n'y a qu'un jeton, quand P a reçu 101 fois, Q a lui aussi reçu 101 fois juste avant. P envoie m vers Q puis initie : il enregistre Sp = 101 et place un marqueur sur le canal P→Q, derrière m.
• Le canal est FIFO : Q reçoit d'abord m (son compteur passe à 102), puis le marqueur. Au premier marqueur, Q enregistre Sq = 102 et marque le canal P→Q comme vide (m a été délivré avant l'enregistrement), puis renvoie un marqueur à P.
• Il reste le canal Q→P, dont l'état dépend de ce que Q a fait de m avant de traiter le marqueur.

États globaux possibles

• (a) Q n'a pas encore renvoyé m quand il enregistre : snapshot = {P = 101, Q = 102, canaux vides}. Le jeton est « chez Q ».
• (b) Q a déjà renvoyé m vers P avant de traiter le marqueur : ce m est parti avant le marqueur de Q sur le canal Q→P, donc P l'enregistre comme état de ce canal. Snapshot = {P = 101, Q = 102, canal Q→P = {m}}. Le jeton est « en transit vers P ».

Les deux sont des coupes cohérentes : dans les deux cas il y a exactement un exemplaire du jeton (chez Q, ou dans le canal), et la somme des états est cohérente. L'algorithme peut rapporter l'un ou l'autre selon l'entrelacement, jamais un état incohérent.

Exécution du cours (figure du survey d'Elnozahy et al.), redessinée : 4 processus, checkpoints c_i,x, P0 et P1 tombent en panne. Les messages sont nommés a à k, sauf m1 et m2 que le prof a annotés.

Q1Le graphe de dépendances de rollback

Un nœud par checkpoint, plus un nœud par état volatil (ce qui a été fait depuis le dernier checkpoint). Pour chaque message envoyé dans l'intervalle qui se termine par c_i,x et reçu dans l'intervalle qui se termine par c_j,y, on trace l'arête c_i,x → c_j,y. Sens : si on annule l'intervalle qui contient l'envoi, il faut annuler celui qui contient la réception. Par exemple m1, envoyé par P1 après c_1,3 et reçu par P0 avant c_0,3, donne volatil(P1) → c_0,3.

Q2La ligne de recovery (P0 et P1 en panne)

On marque les états volatils de P0 et P1 (perdus), puis tout ce qui est atteignable. m1 marque c_0,3, puis m2 (envoyé par P0 dans l'intervalle de c_0,3) marque c_1,3. Rien d'autre n'est atteint. La ligne = le dernier nœud non marqué de chaque processus : {c_0,2, c_1,2, état courant de P2, état courant de P3}. P2 et P3 n'ont pas besoin de reculer.

Q3Et si P3 tombe seul ?

P3 repart de c_3,3. Mais g (P3→P2) est parti après, donc P2 recule avant sa réception : c_2,2. Alors d (P2→P1) devient orphelin : P1 recule à c_1,1. Puis c (P1→P0) fait reculer P0 à c_0,1, b (P0→P2) fait reculer P2 à c_2,1, et f (P2→P3) ramène P3 à c_3,1. Ligne : {c_0,1, c_1,1, c_2,1, c_3,1}, presque au début. Une seule panne, pourtant plus de dégâts : P3 est au cœur de l'enchevêtrement de messages. C'est la loterie du non coordonné.

SuiteÉviter aussi les messages en transit (slide 23)

Autre exécution, P1 tombe. Avec la règle habituelle (pas d'orphelin), P1 recule à son 2^e checkpoint à cause de h puis e, P0 à son 2^e, P2 et P3 gardent leur état : c'est la ligne verte. Mais le message d (P2→P1, en or) est alors en transit : envoyé avant la ligne, reçu après.

Extension des règles : on ajoute l'arête inverse. Si un message est reçu dans un intervalle annulé, on annule aussi l'intervalle qui contient son envoi. Ici d oblige P2 à reculer avant de l'envoyer, donc à son checkpoint initial. Du coup c, f et g (P2→P3) deviennent orphelins et P3 recule aussi à son checkpoint initial. Nouvelle ligne : {2^e checkpoint de P0, 2^e de P1, initial de P2, initial de P3}. Plus aucun message ne la traverse, mais on perd beaucoup plus. D'où l'autre option : garder la première ligne et journaliser les messages en transit (c'est ce que fait Chandy-Lamport).

Un Z-path (zigzag path) enchaîne des intervalles de checkpoints reliés par des messages, en autorisant, sur un même processus, un message reçu avant qu'un autre soit envoyé dans le même intervalle. Un Z-cycle est un Z-path qui revient sur le même checkpoint (par exemple la chaîne m5 m3 m4 du cours).

Lecture du Z-cycle : m5 est envoyé par P2 après c_2,2 et reçu par P0 avant c_0,2. Dans le même intervalle de P0, m3 part vers P1 (avant la réception de m5 : c'est le « zig-zag », pas une chaîne causale). m3 arrive chez P1, qui envoie ensuite m4, reçu par P2 avant c_2,2. On est revenu sur c_2,2.

Pourquoi le checkpoint est inutile

Preuve sur l'exemple : supposons une coupe cohérente qui contient c_2,2. m5 est envoyé après c_2,2, donc sa réception doit être hors de la coupe : P0 doit y figurer avant m5, donc au plus c_0,1. m3 est alors envoyé après la coupe de P0 : P1 doit y figurer avant de recevoir m3, donc au plus c_1,1. m4 est envoyé après : P2 doit y figurer avant de recevoir m4, donc avant c_2,2. Contradiction. Aucune coupe cohérente ne contient c_2,2.

Un checkpoint pris dans un Z-cycle ne sert jamais à la reprise. Intuition : appartenir à un Z-cycle signifie qu'il existe une chaîne causale qui, en partant de ce checkpoint, y revient. Aucune coupe cohérente ne peut donc « passer par » ce checkpoint sans se contredire (il faudrait qu'il soit à la fois dans le passé et le futur d'une même chaîne). Dans le graphe de dépendances de rollback, il est toujours marqué dès qu'un de ses voisins l'est, il n'est donc jamais le « dernier non marqué » d'un processus. Conséquence pratique : les protocoles CIC sont conçus pour ne pas créer de checkpoint dans un Z-cycle (checkpoints forcés bien placés), ce qui garantit qu'aucun checkpoint n'est gaspillé. Ce n'est pas une preuve formelle d'équivalence, mais l'argument informel qui la sous-tend.