Envoyer un message à un seul processus, on sait faire. L'envoyer à tous, alors que l'émetteur peut tomber au milieu, et que chacun doit voir les messages dans un ordre qui a du sens : c'est la communication de groupe.
On empile des modules qui se parlent par événements. En bas, des liens point à point : le lien fair-loss perd, le lien têtu renvoie sans fin, le lien parfait livre chaque message exactement une fois. Au-dessus, la diffusion : BEB (best effort) ne promet rien si l'émetteur crashe ; RB (reliable) garantit l'accord entre processus corrects grâce à un détecteur de pannes ; URB étend l'accord aux processus qui crashent. Orthogonalement, l'ordre de livraison : FIFO (par émetteur), causal (respecte le happened-before, horloges vectorielles), total (tout le monde dans le même ordre, horloges de Lamport ou séquenceur).
01 · Le modèle
Le cours suit la présentation de Guerraoui et Rodrigues (Introduction to Reliable Distributed Programming). Chaque nœud exécute une pile de modules, et chaque module réagit à des événements.
Un module demande un service à celui du dessous. Exemple : l'application déclenche <bebBroadcast | m>.
Le module remonte un résultat, comme une réponse. Exemple : <bebDeliver | src, m> livre m à l'application.
Un « OK » ou un ack qui confirme qu'une requête a été traitée.
Implements: BestEffortBroadcast (beb) Uses: PerfectPointToPointLinks (pp2p) upon event <bebBroadcast | m> do forall pi ∈ Π do trigger <pp2pSend | pi, m> upon event <pp2pDeliver | pi, m> do trigger <bebDeliver | pi, m>
Lire : « ce module fournit BEB, il s'appuie sur des liens parfaits ; quand l'application diffuse, j'envoie à chacun ; quand un lien me livre, je remonte ». Envoyer (send) et livrer (deliver) sont deux choses distinctes : un message peut être reçu par le nœud et retenu avant d'être livré à l'application. Tout le chapitre joue sur cet écart.
Safety : « rien de mauvais n'arrive ». Une violation se voit à un instant précis, et rien ne peut la réparer ensuite. Liveness : « quelque chose de bon finit par arriver ». On ne peut jamais la réfuter en temps fini, il suffit d'attendre encore.
Exemple du prof : un feu tricolore. Safety : une seule direction au vert. Liveness : chaque direction finit par avoir le vert. Un feu toujours rouge est sûr, mais pas vivant.
Les défaillances de nœuds : crash-stop, omissions, crash-recovery, byzantin. Un nœud qui ne tombe pas pendant l'exécution est dit correct. Le détecteur de pannes sert à abstraire le temps (voir la section RB).
02 · Les liens point à point
Trois abstractions de canal, chacune construite sur la précédente. Leurs propriétés portent des noms courts (FL, SL, PL) qui reviennent dans les exercices.
FL1 fair-loss : envoyé une infinité de fois (et personne ne crashe) ⇒ livré une infinité de fois. FL2 duplication finie. FL3 pas de création. Il peut perdre n'importe quelle copie, mais pas toutes.
SL1 : si pi envoie m à pj correct et ne crashe pas, pj livre m une infinité de fois. SL2 pas de création. Construit sur fair-loss : garder tout dans sent, tout renvoyer à chaque timeout.
PL1 reliable delivery : si ni pi ni pj ne crashent, tout m envoyé est livré. PL2 pas de duplication. PL3 pas de création. Construit sur le lien têtu + un journal delivered.
// Stubborn links, sur fair-loss upon event <Init> : sent := ∅ ; startTimer(Δ) upon event <Timeout> : forall (dest, m) ∈ sent : trigger <flp2pSend | dest, m> startTimer(Δ) upon event <sp2pSend | dest, m> : trigger <flp2pSend | dest, m> sent := sent ∪ {(dest, m)} upon event <flp2pDeliver | src, m> : trigger <sp2pDeliver | src, m>
// Perfect links, sur stubborn upon event <Init> : delivered := ∅ upon event <pp2pSend | dest, m> : trigger <sp2pSend | dest, m> upon event <sp2pDeliver | src, m> : if m ∉ delivered then delivered := delivered ∪ {m} trigger <pp2pDeliver | src, m>
PL1 (tout message finit par être livré) est une propriété de liveness. PL2 (jamais deux fois) et PL3 (jamais inventé) sont des propriétés de safety : leur violation est un événement précis, irréparable.
Sauf mention contraire, le reste du cours suppose des liens parfaits, et des messages identifiés de façon unique (l'identifiant inclut l'émetteur). Envoyer deux fois « le même » contenu, ce sont deux messages différents.
03 · Diffuser au groupe
Un groupe permet d'adresser un ensemble de processus comme une seule entité, sans savoir combien ils sont ni où ils sont. Usages cités en cours : serveurs répliqués, bases de données répliquées (réplication de machine à états), visioconférence, jeux en ligne, publish/subscribe boursier, ZooKeeper et son protocole Zab. IP multicast n'étant pas activé partout sur Internet, on construit la diffusion au-dessus des liens point à point.
Si pi et pj sont corrects, tout message diffusé par pi est finalement livré par pj.
Aucun message n'est livré plus d'une fois.
Si pj livre m, alors m a été diffusé par un certain pi.
Exemple 2 : P1 diffuse, P2 et P4 livrent, P3 jamais, et P1 ne crashe pas. Interdit : P1 et P3 sont corrects, BEB1 est violée. Exemple 3 : même chose mais P1 crashe. Autorisé : BEB1 ne s'applique qu'à un émetteur correct. BEB est donc tout à fait content de laisser des processus corrects en désaccord quand l'émetteur tombe. C'est ce que corrige RB.
04 · L'ordre de livraison
Deuxième axe, indépendant de la fiabilité : dans quel ordre chaque processus livre-t-il les messages ? L'exemple du chat : si « Salle 515 » (réponse de Mr Y) s'affiche avant « Quelqu'un sait où est le cours ? » (question de Mr X), la conversation n'a plus de sens.
m1 → m2 (m1 précède causalement m2) si :
CB, livraison causale : si un nœud livre m2, il a livré avant tout message m1 → m2.
TO : pour tous messages m1, m2 et tous processus pi, pj qui livrent les deux, pi et pj les livrent dans le même ordre.
« Atomique » car tout se passe comme si la diffusion était indivisible : livré à tous ou à aucun, et chaque message est rangé avant ou après chaque autre. C'est l'abstraction qui garde des répliques d'un service déterministe cohérentes.
L'ordre total n'implique pas l'ordre causal : « tout le monde dans le même ordre » peut être un ordre qui contredit l'ordre d'envoi. Et l'ordre causal n'implique pas l'ordre total : deux messages concurrents (m1 || m2) peuvent être livrés dans des ordres différents sur deux processus, sans rien violer. Slide 77 du cours : P1 livre m1 puis m2, P2 livre m2 puis m1, aucune causalité entre eux, rien d'anormal pour un causal broadcast.
Exercice du cours : construire un causal broadcast sur BEB. Impossible de le faire proprement : avec BEB, un processus ne peut pas distinguer un ancêtre perdu pour toujours (l'émetteur a crashé au milieu) d'un ancêtre encore en transit. S'il livre m sans attendre, puis reçoit plus tard un ancêtre retardé, CB est violée ; s'il attend, il peut attendre indéfiniment. C'est la même impasse que le théorème FLP (pas de consensus déterministe en asynchrone avec une seule panne) : il faut un moyen de gérer les pannes, d'où la version fiable plus bas.
05 · Ordre total
On estampille chaque message, puis chacun livre dans l'ordre des estampilles. Reste à fabriquer des estampilles cohérentes.
Un processus central numérote les messages ; tout le monde livre dans l'ordre des numéros. Simple, mais point unique de défaillance et goulot d'étranglement. Déroulé complet dans l'exercice 6.
Chacun estampille avec une horloge de Lamport, départagée par l'identifiant. On ne livre un message que quand plus personne ne peut en envoyer un plus ancien (ou, variante ABCAST, les récepteurs proposent une estampille et on prend le max).
// algorithme de l'exercice 4 (processus p, canaux FIFO, pas de panne) LCp[1..n] := 0 ; received := ∅ ; delivered := ∅ procedure TO-multicast(m) : LCp[p] := LCp[p] + 1 ; ts(m) := LCp[p] send FIFO (m, ts(m)) to all // y compris p lui-même when receive (m, ts(m)) : LCp[p] := max(ts(m), LCp[p]) + 1 LCp[sender(m)] := ts(m) // « j'ai tout reçu de lui jusqu'à ts(m) » received := received ∪ {m} deliver tout m' ∈ received \ delivered tel que ts(m') ≤ minq LCp[q], par ordre croissant de (ts, sender)
Ordre total (tri par (ts, émetteur) identique partout) et compatible avec la causalité : un message diffusé après en avoir reçu un autre a une estampille plus grande. Prix : la liveness exige que chaque processus diffuse régulièrement (sinon min LC[q] ne bouge pas), et les canaux doivent être FIFO. L'exercice 4 détaille pourquoi.
06 · Fiabilité
TCP garantit du point à point. Pour un groupe, il faut un service plus fort : si l'émetteur crashe au milieu, tous ou aucun des processus corrects doivent avoir le message.
Un détecteur de pannes est une boîte noire qui émet des suspicions <crash | pi>. Implémentation typique : heartbeats périodiques, timeout sur le pire aller-retour, suspicion si timeout, révision (et timeout rallongé) si un message arrive d'un suspect.
Completeness porte sur les processus réellement morts (quand faut-il les voir ?), accuracy sur les vivants (a-t-on le droit de les soupçonner ?). Parfait = hypothèse synchrone, d'où « fail-stop ».
RB4 est la nouveauté. Elle ne dit rien d'un processus qui livre puis crashe (voir URB).
// RB « lazy », modèle fail-stop (slide 68) Implements: ReliableBroadcast (rb) Uses: BestEffortBroadcast (beb), PerfectFailureDetector (P) upon event <Init> : delivered := ∅ ; correct := Π ; forall pi ∈ Π : from[pi] := ∅ upon event <rbBroadcast | m> : trigger <bebBroadcast | [DATA, self, m]> upon event <bebDeliver | pi, [DATA, sm, m]> : if m ∉ delivered then delivered := delivered ∪ {m} trigger <rbDeliver | sm, m> from[pi] := from[pi] ∪ {(sm, m)} // pi = celui qui me l'a transmis if pi ∉ correct then // déjà suspect : relayer tout de suite trigger <bebBroadcast | [DATA, sm, m]> upon event <crash | pi> : correct := correct \ {pi} forall (sm, m) ∈ from[pi] : trigger <bebBroadcast | [DATA, sm, m]>
On ne relaie que quand l'émetteur (ou le dernier transmetteur) est suspecté. Sans panne : zéro message en plus de BEB. Avec pannes : on paie un relais par message reçu du processus mort. La variante « eager » relaie tout, toujours, à la première réception : pas besoin de détecteur, mais O(n²) messages par diffusion. Un détail qui tombe à l'exercice 2 : from[pi] n'est rempli qu'à la première réception de m. Une copie reçue en double n'y entre pas.
Collecter des acks de tous les membres provoque une implosion d'acks sur l'émetteur. Parades vues en cours : un arbre d'acks, ou la diffusion épidémique (probabiliste, gossip).
07 · Uniformité
Une propriété est uniforme si les processus fautifs la respectent aussi. URB, uniform agreement : pour tout message m, si un processus (correct ou non) livre m, alors tout processus correct livre m.
Une livraison peut avoir un effet visible de l'extérieur, difficile à annuler : créditer un compte sur une réplique, afficher un résultat, piloter un actionneur. Si cette réplique crashe juste après, les répliques survivantes doivent quand même appliquer le crédit. Slide 71 : p1 a livré m1 puis crashé, donc p2 et p3 doivent livrer m1 ; p1 n'a pas livré m2, donc personne n'est obligé de le livrer. Le cours se limite aux versions non uniformes, mais l'exercice 2 demande pourquoi RB n'est pas uniforme.
08 · Causal fiable
Idée : chaque message transporte un résumé de son passé (un vecteur), et on ne le livre qu'une fois ce passé livré localement. On l'empile au-dessus de RB (propriétés RB1 à RB4 plus CB).
// au nœud pi : VC[i] = nb de messages que pi a co-diffusés // VC[j] = nb de messages de pj co-livrés ici upon event <Init> : forall pj : VC[j] := 0 upon event <rcoBroadcast | m> : trigger <rbBroadcast | (DATA, VC, m)> // VC AVANT incrément VC[self] := VC[self] + 1 trigger <rcoDeliver | self, m> // livraison locale immédiate upon event <rbDeliver | pj, (DATA, VCm, m)> : if pj ≠ self then pending := pending ∪ {(pj, VCm, m)} ; deliver-pending() procedure deliver-pending() : while ∃ (sm, VCm, m) ∈ pending tel que VC ≥ VCm : pending := pending \ {(sm, VCm, m)} trigger <rcoDeliver | sm, m> VC[rank(sm)] := VC[rank(sm)] + 1
Pourquoi retenir ? VCm = [1,0,0] dit « m est la conséquence d'un message de P1 ». Si le récepteur est à [0,0,0], il n'a pas encore livré ce message : il attend.
Pourquoi VC[1] = 1 après livraison de m1 ? Parce que la case compte les messages de P1 co-livrés, pas un temps.
Pourquoi pas de max case par case ? La condition VC ≥ VCm garantit déjà que toutes les autres cases sont au moins à leur valeur dans VCm. Seule la case de l'émetteur change, d'une unité.
09 · Vue d'ensemble
Les deux problèmes se ressemblent (slide 79). Le consensus décide une valeur parmi des propositions (mettre à jour une variable répliquée A) ; la communication de groupe décide de livrer un message sur chaque nœud. Dans les deux cas, tous les nœuds corrects doivent être d'accord, il faut suspecter les pannes (détecteur parfait), et on décide valeur par valeur ou message par message.
| Diffusion | Fiabilité | Ordre | Coût typique |
|---|---|---|---|
| BEB | validité si l'émetteur est correct | aucun | n messages |
| RB (lazy) | + accord entre corrects | aucun | n, + relais si crash |
| URB | + accord uniforme | aucun | relais + acks de tous |
| RCO (vecteurs) | RB | causal (donc FIFO) | vecteur de n entiers par message |
| TO (Lamport) | aucune panne tolérée | total et causal | chacun doit diffuser régulièrement |
JGroups, Appia, ISIS, Horus, Quicksilver, Ensemble, Joram (JMS). ZooKeeper utilise Zab, une diffusion atomique à leader qui garantit en plus l'ordre FIFO du primaire.
10 · Exercices corrigés
Dans l'ordre du dossier Moodle « Some exercises and their correction » (exos 1 à 6). Les diagrammes sont redessinés d'après les slides et les sujets, les valeurs d'horloge sont recalculées par simulation et comparées aux copies notées A+ fournies par le prof.
Le prof impose de s'entraîner sur les exos 2 (scénarios Reliable Broadcast) et 3 (ordre causal, puis crash de P1 pendant m3). Ce sont les deux corrigés les plus détaillés ci-dessous, avec l'état de chaque processus à chaque événement et la liste de ce qu'il faut savoir justifier. Le corrigé officiel de l'exo 2 et celui de la partie causale de l'exo 3 sont publiés et concordent avec les nôtres ; celui de la question additionnelle de l'exo 3 (crash de P1) ne sortira qu'après le test.
Implémenter pp2p autrement qu'en cours : au lieu du lien têtu, faire renvoyer un acquittement par le récepteur, sur un lien fair-loss. Discuter toutes les propriétés attendues.
Corrigé basé sur une copie notée A+ et les annotations du prof. Idée : l'émetteur renvoie périodiquement tant qu'il n'a pas reçu d'ack, puis oublie le message. Plus de renvoi infini.
Implements: PerfectPointToPointLinks (pp2p) Uses: FairLossPointToPointLinks (flp2p) upon event <Init> : not_delivered := ∅ ; delivered := ∅ ; startTimer(Δ) upon event <Timeout> : forall (dest, m) ∈ not_delivered : trigger <flp2pSend | dest, [DATA, m]> startTimer(Δ) upon event <pp2pSend | dest, m> : not_delivered := not_delivered ∪ {(dest, m)} trigger <flp2pSend | dest, [DATA, m]> upon event <flp2pDeliver | src, [DATA, m]> : trigger <flp2pSend | src, [ACK, m]> // TOUJOURS, même pour un doublon if m ∉ delivered then delivered := delivered ∪ {m} ; trigger <pp2pDeliver | src, m> upon event <flp2pDeliver | src, [ACK, m]> : not_delivered := not_delivered \ {(src, m)}
Si ni l'émetteur ni le récepteur ne crashent, m reste dans not_delivered et part à chaque timeout tant qu'aucun ack n'est revenu. Si l'ack n'arrive jamais, m est envoyé une infinité de fois, donc livré par FL1. S'il arrive, c'est que le récepteur a reçu m au moins une fois, donc l'a livré.
Garanti par delivered : seule la première copie remonte. Point subtil de la figure : l'ack peut lui aussi être perdu. L'émetteur renvoie alors m, le récepteur reçoit un doublon. Il doit quand même ré-acquitter, sinon l'émetteur renverrait à l'infini, mais sans relivrer.
Héritée de FL3 : le lien fair-loss ne crée pas de message, et on ne livre que des DATA reçus.
1) Un timer par message serait plus propre qu'un timer global qui renvoie tout. 2) Le lien fair-loss n'a qu'un seul événement de livraison : on ne peut pas supposer un « flp2pAckDeliver » séparé, il faut étiqueter les messages (DATA / ACK) et dispatcher sur le contenu, comme ci-dessus. Par rapport à la version du cours, on gagne la fin des renvois ; on garde un journal delivered qui grossit sans fin (on peut le borner avec des numéros de séquence par émetteur, hors sujet ici).
Slide 69 : P0 diffuse m et crashe, P1 détecte le crash de P0, relaie m puis crashe à son tour. Continuer l'exécution de l'algorithme RB lazy jusqu'au bout.
Le prof a mis en ligne le 29/09 une copie notée A+ (« CorrecRBCAST »). Elle déroule le même scénario que ci-dessous : P2 relaie m quand son détecteur lui annonce le crash de P0, P4 livre grâce à ce relais, puis P3 relaie à son tour quand il apprend le crash de P1. Elle ajoute la comparaison avec BEB et le cas où P2 et P3 tombent aussi, repris en fin de corrigé.
On déroule le RB « lazy » de la slide 68 (voir la section RB). Chaque processus tient trois variables, et c'est leur évolution que le correcteur veut voir :
delivered (d) : les messages déjà livrés, pour jeter les doublons ;correct (c) : les processus que le détecteur n'a pas encore signalés ;from[pj] : les messages livrés dont la première copie est venue de pj. Si pj crashe, on les rediffuse, car pj n'a peut-être pas fini de les transmettre. Un doublon n'entre jamais dans from (tout se passe dans le if m ∉ delivered).Diagramme initial (transcrit de la slide 69) :
Lecture : P0 diffuse m. Ses copies atteignent P0 lui-même, P1 et P2, puis P0 crashe (croix) avant d'envoyer à P3 et P4. Le losange sur P1 (« X of P0 » sur la slide) est l'événement <crash | P0> délivré par le détecteur : P1 relaie m (vers P0, P2, P3) puis crashe avant d'atteindre P4.
Anime le scénario : une étape = un événement, et la colonne de droite montre d (delivered), c (correct) et from de chaque processus. C'est la méthode de la copie A+ : sous chaque événement, écrire d, c et from.
Le même déroulé en tableau, à reproduire sur copie :
| # | Où | Événement | Ce que fait l'algorithme | État après |
|---|---|---|---|---|
| 0 | tous | Init | - | d = ∅, c = {P0..P4}, from[*] = ∅ |
| 1 | P0 | rbBroadcast(m) | bebBroadcast à tous. P0 reçoit sa propre copie et livre m. Les copies pour P1 et P2 partent, P0 crashe avant P3 et P4. | P0 : d = {m}, puis crash |
| 2 | P1 | bebDeliver(P0, m) | m ∉ d : livre m, from[P0] ∪= {m}. P0 ∈ c : pas de relais. | d = {m}, from[P0] = {m} |
| 3 | P1 | <crash | P0> | c := c \ {P0}, rediffuse from[P0] = {m} vers P0, P2, P3, puis crashe avant l'envoi à P4. | c = {P1..P4}, puis crash |
| 4 | P2 | bebDeliver(P0, m) | 1re copie : livre m. P0 pas encore signalé à P2 : from[P0] = {m}. | d = {m}, from[P0] = {m} |
| 5 | P2 | bebDeliver(P1, m) | m ∈ d : rien, ni livraison ni ajout dans from[P1]. | inchangé |
| 6 | P3 | bebDeliver(P1, m) | 1re copie : livre m (émetteur d'origine sm = P0, pas P1). from[P1] = {m}. | d = {m}, from[P1] = {m} |
| 7 | P2 | <crash | P0> | c := c \ {P0}, rediffuse from[P0] = {m} vers tous (P0 et P1 sont morts). | c = {P1..P4} |
| 8 | P3 | bebDeliver(P2, m) | doublon, ignoré. | inchangé |
| 9 | P4 | bebDeliver(P2, m) | 1re copie : livre m, from[P2] = {m}. | d = {m}, from[P2] = {m} |
| 10 | P3 | <crash | P1> | rediffuse from[P1] = {m} : P2 et P4 l'ont déjà, ignoré. | c sans P1 |
| 11 | tous | autres <crash> | P2 apprend P1 : from[P1] = ∅. P3 apprend P0 : from[P0] = ∅. P4 apprend P0 et P1 : rien. Aucun renvoi. | c = {P2, P3, P4} partout |
P4 garde m dans from[P2], mais P2 est correct : par PFD2 (pas de fausse suspicion) son crash ne sera jamais annoncé, donc P4 ne relaiera jamais rien. L'exécution s'arrête là.
Les trois processus corrects (P2, P3, P4) livrent m exactement une fois : RB4 (agreement) et RB2 tiennent. P0 et P1 l'ont livré avant de tomber, ce que RB n'exige pas. Coût : P1, P2 et P3 rediffusent chacun m, donc des copies redondantes. C'est le prix de ne pas savoir, localement, qui a déjà transmis quoi.
Le résultat final de la copie A+ est juste (P2, P3, P4 livrent m), mais plusieurs points ne suivent pas la slide 68. À ne pas recopier au test :
if m ∉ delivered). Un doublon n'y entre pas. C'est cette annotation qui mène à l'erreur précédente.if pi ∉ correct), pas plus tard au losange [crash]. Au test : soit c contient encore l'émetteur à la réception et le relais part au [crash] (notre déroulé), soit c l'exclut déjà et le relais part à la réception. Pas les deux. Le résultat final est le même.if pi ∉ correct). Même résultat, relais plus tôt.La troisième variante, animée :
Deuxième partie de la copie A+. Avec BEB, un processus qui reçoit m le livre et s'arrête là : il ne le relaie jamais, même quand l'émetteur tombe. Sur le schéma du corrigé, P1 ne relaie pas m ; il diffuse un autre message m2 puis crashe :
P1 et P2 ont m, P3 ne l'aura jamais, P4 n'aura ni m ni m2. BEB respecte son contrat (BEB1 ne promet rien quand l'émetteur crashe), mais les corrects P2, P3, P4 sont en désaccord sur m : exactement ce qu'interdit RB4. Toute la différence entre les deux algorithmes tient dans le relais déclenché par <crash>.
1) on livre à la première copie seulement ; 2) le relais est déclenché par le détecteur (ou tout de suite si le transmetteur est déjà suspect), jamais par la simple réception ; 3) from est indexé par le transmetteur, pas par l'émetteur d'origine ; 4) la conclusion s'exprime en propriétés : RB4 pour les corrects, rien d'exigé pour P0 et P1.
Assumptions. Lazy RB of slide 68 on top of BEB and a perfect failure detector P. Each process pi keeps delivered, correct (initially Π) and from[pj] = messages whose first copy came from pj.
Conclusion. The correct processes P2, P3, P4 each deliver m exactly once: RB4 (agreement), RB2 and RB3 hold. RB1 does not apply (the sender P0 is faulty).
Robustness. If P2 crashed before relaying to P4, P4 would still get m: P3 holds m in from[P1] and, since P1 crashed and P3 is correct, strong completeness guarantees that P3 detects it and relays m. If P2 and P3 crash before relaying, P4 never gets m: this is allowed by RB (no correct process delivered m and the sender is faulty) but forbidden by URB.
BEB. With Best Effort Broadcast nobody ever relays. P1 and P2 deliver m, P3 and P4 never do (P1 may broadcast another message m2, received by P2 and P3 and lost for P4). BEB1 is not violated (faulty sender), but the correct processes disagree on m, which RB4 forbids.
Sur le diagramme de la slide 78, appliquer l'algorithme de Reliable Causal Order à vecteurs. Commenter deux estampilles. Puis faire crasher P1 pendant la diffusion de m3, avec et sans RB. Enfin, l'algorithme RB est-il uniforme ?
Partie causale : notre simulation donne exactement les vecteurs et les ordres de livraison de la copie A+ du homework 2025-26 et du corrigé officiel publié le 29/09 (homework #4, exercice 2). La question additionnelle (crash de P1) n'a pas encore de corrigé officiel. Rappel de l'algorithme : l'émetteur accroche son vecteur avant de l'incrémenter et se livre le message tout de suite.
Sur la slide 74, les vecteurs de P1 sont mal placés. Le vecteur d'un processus ne change qu'à deux moments : quand il diffuse (sa propre case +1, après avoir accroché l'ancien vecteur au message) et quand il livre le message d'un autre (case de l'émetteur +1). Jamais à la simple réception : un message reçu puis mis en attente ne touche pas au vecteur. Sur P1, le passage de (0,0,0) à (1,0,0) se fait donc au moment de d(m1), celui à (2,0,0) au moment de d(m2). L'algorithme des slides 75/76 (rappelé dans la section causale) le rend explicite.
Ordre des événements lu sur la slide. P1 : b(m1), reçoit m2, b(m3), reçoit m5, reçoit m4. P2 : reçoit m1, b(m2), b(m5), reçoit m4, reçoit m3. P3 : reçoit m3, reçoit m2, reçoit m1, b(m4), reçoit m5.
Animation : une étape par événement, le vecteur local et la file d'attente de chaque processus à droite.
Relations : m1 → m2 (P2 livre m1 puis diffuse m2, ordre réseau), m2 → m3 (P1 livre m2 puis diffuse m3), m1 → m3 (FIFO sur P1), m2 → m5 (FIFO sur P2), m3 → m4 (P3 livre m3 puis diffuse m4), et par transitivité m1 → m4, m2 → m4, m1 → m5. En revanche m3 || m5 et m4 || m5 : aucune chaîne ne les relie.
| Message | m1 | m2 | m3 | m5 | m4 |
|---|---|---|---|---|---|
| VCm | [0,0,0] | [1,0,0] | [1,1,0] | [1,1,0] | [2,1,0] |
| Processus | Ce qui se passe | Ordre de livraison |
|---|---|---|
| P1 | m2 : [1,0,0] ≥ [1,0,0], livré → [1,1,0]. b(m3) → [2,1,0]. m5 ([1,1,0]) livré → [2,2,0]. m4 ([2,1,0]) livré → [2,2,1]. | m1 m2 m3 m5 m4 |
| P2 | m1 livré → [1,0,0]. b(m2) → [1,1,0], b(m5) → [1,2,0]. m4 arrive : il faut VC[1] ≥ 2, P2 a 1, m4 en attente. m3 arrive ([1,1,0]) : livré → [2,2,0], puis m4 débloqué → [2,2,1]. | m1 m2 m5 m3 m4 |
| P3 | m3 ([1,1,0]) en attente, m2 ([1,0,0]) en attente. m1 ([0,0,0]) livré → [1,0,0], puis m2 → [1,1,0], puis m3 → [2,1,0]. b(m4) → [2,1,1]. m5 livré → [2,2,1]. | m1 m2 m3 m4 m5 |
Les trois ordres diffèrent (m3 et m5 échangés, m4 et m5 échangés), et c'est normal : ces paires sont concurrentes. Tous respectent m1 → m2 → m3 → m4 et m2 → m5.
(2,2,0) est le vecteur local de P2 juste après avoir livré m3, pas l'estampille de m3 (qui vaut [1,1,0]). VC[1] = 2 : P2 a livré deux messages de P1 (m1, m3). VC[2] = 2 : P2 a diffusé deux messages (m2, m5). Le 2 en case 2 ne vient pas de m3 : m3 ne dépend que de m2, pas de m5. C'est exactement le signe que m3 || m5.
P3 a diffusé m4 après avoir livré m1, m2, m3 : deux messages de P1, un de P2, zéro de lui-même. m4 dit donc « livre-moi après m1 et m3 de P1 et m2 de P2 », et rien sur m5. D'où l'attente sur P2 : quand m4 arrive, P2 n'a livré qu'un message de P1 (VC[1] = 1 < 2), il manque m3.
Tous les vecteurs du corrigé publié sont exacts. Deux formulations sont fausses à la lettre : « d(m2) incrémente VC2[2] car m2 est reçu de P2 » (m2 est diffusé par P2 lui-même : l'incrément se fait au coBroadcast, la livraison locale ne touche pas au vecteur, sinon on compterait deux fois) et « à la réception de m3, VC2[1] est incrémenté » (c'est à la livraison ; m4, arrivé avant, était en attente et n'est livré qu'après m3).
À la livraison de m venant de pj, on fait VC[j] := VC[j] + 1 et rien d'autre. Pas besoin du max case par case des horloges vectorielles classiques : la condition de livraison VC ≥ VCm impose déjà que toutes les autres cases locales soient au moins égales à celles de VCm. Le max ne changerait rien.
Le corrigé officiel de cette question ne sortira qu'après le test du 5 octobre. Ce qui suit applique à la lettre l'algorithme causal (slides 75/76) posé sur le RB lazy (slide 68).
Le scénario. Une diffusion BEB est une boucle d'envois point à point. P1 fait b(m3) : il accroche VCm3 = [1,1,0], passe à [2,1,0], se livre m3, envoie la copie à P3, puis crashe avant d'envoyer celle de P2. Le reste du diagramme ne change pas (m1 et m2 étaient déjà partis ; P1 ne recevra plus m5 ni m4, sans importance).
Ce qui doit arriver. Les corrects sont P2 et P3. P3 livre m3, donc par RB4 P2 doit aussi livrer m3, puis m4 qui en dépend. Au final les deux corrects doivent livrer m1, m2, m3, m4 et m5. Rien n'est exigé de P1.
Sans RB (la même couche causale posée sur BEB) :
P3 livre m3 (après m1 et m2, comme dans l'exécution normale). P2 ne recevra jamais m3 : personne ne le lui renvoie. Puis m4 arrive sur P2 avec VCm4 = [2,1,0] alors que P2 est à [1,2,0] : il manque un message de P1, m4 part en attente pour toujours. Deux problèmes :
C'est pour ça que le cours empile l'ordre causal sur RB et pas sur BEB : l'ordre causal attend les ancêtres, il faut donc une couche qui garantit que les ancêtres livrés par un correct arrivent partout.
Avec RB : scénario proposé, avec le moment de chaque livraison.
| # | Où | Événement | Couche RB | Couche causale (VC après) |
|---|---|---|---|---|
| 1 | P3 | reçoit m3 de P1 | 1re copie : rbDeliver. P1 ∈ correct : from[P1] = {m3} | en attente (il faut [1,1,0], P3 a [0,0,0]) |
| 2 | P3 | reçoit m2 | rbDeliver, from[P2] = {m2} | en attente |
| 3 | P3 | reçoit m1 | rbDeliver, from[P1] = {m3, m1} | livre m1, m2, m3 : [2,1,0] |
| 4 | P3 | b(m4) | bebBroadcast | VCm4 = [2,1,0], puis [2,1,1] |
| 5 | P3 | <crash | P1> | rediffuse from[P1] = {m1, m3}, avec l'émetteur d'origine P1 et les vecteurs d'origine | inchangé |
| 6 | P2 | reçoit m4 | rbDeliver, from[P3] = {m4} | en attente (VC[1] = 1 < 2) : [1,2,0] |
| 7 | P3 | reçoit m5 | rbDeliver | [2,1,1] ≥ [1,1,0] : livre m5, [2,2,1] |
| 8 | P2 | reçoit m1 relayé | déjà dans delivered : ignoré | inchangé |
| 9 | P2 | reçoit m3 relayé | 1re copie : rbDeliver, from[P3] = {m4, m3} | [1,2,0] ≥ [1,1,0] : livre m3, [2,2,0], puis m4 débloqué : [2,2,1] |
| 10 | P2 | <crash | P1> | rediffuse from[P1] = {m1} | P3 l'ignore (doublon) |
Ordres de livraison : P2 m1 m2 m5 m3 m4, P3 m1 m2 m3 m4 m5. Ce sont exactement ceux de l'exécution sans panne : la panne ne change que le moment où P2 livre m3, fixé par le détecteur de P3. Accord rétabli, ordre causal respecté (m3 avant m4 partout).
1) P3 relaie tout from[P1], donc m1 et m3 (m1 est un doublon pour P2, ignoré par la couche RB). 2) Le relais garde l'émetteur d'origine P1 et le vecteur d'origine [1,1,0] : sinon P2 incrémenterait la mauvaise case. 3) La couche RB livre à la couche causale dès la première copie, même si le message part ensuite en attente : c'est la réception RB qui remplit from, pas la livraison causale. 4) Le relais peut aussi être immédiat : si P3 apprend le crash de P1 avant que m3 arrive, il le rediffuse à la réception.
Deux variantes du scénario. Si c'est la copie pour P2 qui part et pas celle pour P3 : symétrique, P2 livre m3 et le relaie à P3 sur <crash | P1>. Mais P3 ne peut plus livrer m3 avant b(m4), donc m4 porte [1,1,0] et ne dépend plus de m3. Si aucune copie ne part : seul P1, fautif, a livré m3. RB n'exige rien, m3 disparaît, et m4 porte [1,1,0] : pas de blocage, personne ne dépend d'un message que personne n'a.
Rules. On coBroadcast, pi attaches its current VC to m, then increments VC[i] and delivers m locally (the local delivery does not change VC). On receiving m from pj ≠ pi: m is held until VC ≥ VCm; when delivered, VC[j] += 1. Timestamps: m1 (0,0,0), m2 (1,0,0), m3 (1,1,0), m5 (1,1,0), m4 (2,1,0). Delivery orders: P1 m1 m2 m3 m5 m4, P2 m1 m2 m5 m3 m4, P3 m1 m2 m3 m4 m5 (m3 || m5 and m4 || m5, so different orders are legal).
Why d(m3) on P2 is (2,2,0). This is P2's local clock right after delivering m3, not the timestamp of m3 (which is (1,1,0)). Before that, P2 delivered m1 from P1 (VC[1] = 1) and broadcast m2 and m5 itself (VC[2] = 2, incremented at each coBroadcast). m4 arrived first but was held, since VCm4[1] = 2 > 1. m3 is deliverable ((1,2,0) ≥ (1,1,0)); its delivery increments VC[1]: (2,2,0). m4 then becomes deliverable: (2,2,1). VC[2] = 2 counts m5 although m3 does not depend on m5: m3 || m5.
Why m4 carries (2,1,0). It is P3's clock when it broadcasts m4, before incrementing VC[3]. P3 had delivered m1, m2, m3 (m3 and m2 were held until m1 arrived): two messages from P1, one from P2, none of its own. So m4 must be delivered after m1, m3 and m2, and says nothing about m5.
Additional question: P1 crashes while broadcasting m3. Assume the copy to P3 is sent and the copy to P2 is not. Without RB (causal layer on BEB): P3 delivers m1, m2, m3, broadcasts m4 with (2,1,0); P2 never receives m3, so m4 is held forever, and so is every later message of P3 (its VC[1] = 2). The correct processes disagree and P2 blocks: this is why the causal layer is built on RB. With lazy RB: P3 stores m1 and m3 in from[P1] (first copies from P1). On <crash | P1> it relays both, with their original sender and timestamps. P2 ignores m1 (duplicate), delivers m3 ((1,2,0) ≥ (1,1,0), clock (2,2,0)), then m4 (2,2,1). P2 later relays its from[P1] = {m1}, a duplicate for P3. Final orders are the same as without the crash: P2 m1 m2 m5 m3 m4, P3 m1 m2 m3 m4 m5; only the time of d(m3) on P2 depends on the failure detector.
L'énoncé exact de cette question n'est pas dans le dossier ; elle est reconstituée d'après la copie notée A+ (« YES » du prof sur l'analyse).
Non. Contre-exemple : P1 diffuse m, seul P2 le reçoit. P2 n'a pas encore détecté la panne de P1, donc il livre sans relayer, puis crashe. P3, correct, n'aura jamais m. RB4 tient (P2 n'est pas correct), mais l'uniform agreement est violé : un processus a livré m, un correct ne le livre pas. Voir l'animation de la section URB.
Variante « relayer avant de livrer, mais seulement si l'émetteur est suspect » : même contre-exemple, si P1 n'est pas encore suspecté au moment où P2 livre. Pas uniforme non plus.
Pour obtenir URB : relayer à chaque première réception, sans condition, et ne livrer m que lorsqu'on sait que tous les processus encore corrects l'ont (on a reçu m de chacun d'eux, algorithme « All-Ack » avec détecteur parfait ; ou d'une majorité si moins de la moitié peut crasher, sans détecteur). Ainsi, au moment où un processus livre, m est déjà chez tous les corrects.
Exercice d'examen (5 points). n processus, aucune panne, canaux point à point FIFO. Découvrir quel ordre de livraison garantit l'algorithme de la figure, s'il en garantit un (d'où le nom « xx-multicast »).
// Figure 1 : code du processus p (canaux FIFO) Initialization : receivedp := ∅ ; deliveredp := ∅ ; LCp[p1..pn] := (0, ..., 0) // LCp[q] : horloge logique de q, vue par p procedure xx-multicast(m) : LCp[p] := LCp[p] + 1 ts(m) := LCp[p] send FIFO (m, ts(m)) to all when receive (m, ts(m)) : LCp[p] := max(ts(m), LCp[p]) + 1 LCp[sender(m)] := ts(m) receivedp := receivedp ∪ {m} deliverable := ∅ for each m' ∈ receivedp \ deliveredp : if ts(m') ≤ minq∈Π LCp[q] then deliverable := deliverable ∪ {m'} deliver tous les messages de deliverable, par ordre croissant de (ts(m), sender(m)) deliveredp := deliveredp ∪ deliverable
Corrigé fondé sur la copie notée A+ et les annotations au crayon du prof. Valeurs recalculées par simulation, identiques à la copie. Convention : « send to all » inclut p lui-même, et on considère que p reçoit sa propre copie immédiatement (sa case LCp[p] est alors écrasée par ts(m), ce qui ne change rien puisqu'elle vaut déjà ts(m)).
P1 diffuse m1 (ts = 1), P2 diffuse m2 (ts = 1). Chez P1 : sa copie donne LC = [1,0,0], puis m2 donne LC[1] = max(1,1)+1 = 2 et LC[2] = 1, soit [2,1,0]. Symétriquement P2 est à [1,2,0]. Le minimum vaut 0 (la case de P3) : ts = 1 > 0, rien n'est livrable, pas même chez l'émetteur.
Pourquoi ? LCp[q] se lit « j'ai reçu tout ce que q a diffusé jusqu'à l'estampille LCp[q] ». Tant que P3 n'a rien envoyé, P1 ne sait pas si un message de P3 de faible estampille est encore en route. La règle est prudente : elle attend une preuve (un message de P3 d'estampille ≥ ts(m)) que plus rien de plus ancien ne viendra de P3. Sans cette preuve, livrer maintenant pourrait obliger à livrer plus tard un message qui aurait dû passer devant.
P3 reçoit m2 puis m1 : [0,1,2] puis [1,1,3]. Minimum = 1 : ts(m1) = ts(m2) = 1 ≤ 1, les deux sont livrables. Égalité d'estampille départagée par l'émetteur : P3 livre m1 puis m2. P1 et P2, toujours sans nouvelle de P3, retiennent.
Puis P3 diffuse m3 (ts = 4) :
P1 : [5,1,4], P2 : [1,5,4]. Minimum 1 : ils livrent m1 puis m2, comme P3. m3 (ts 4) reste retenu partout, P3 compris ([1,1,4]) : P1 et P2 n'ont rien envoyé depuis leurs messages d'estampille 1.
Si c'est P2 qui diffuse (m3, ts = 3) au lieu de P3 :
P1 passe à [4,3,0], P2 à [1,3,0] : toujours LC[3] = 0, rien de livré sur P1 ni sur P2. P3 passe à [1,3,4], min = 1 : m3 retenu. Seule la parole de P3 peut débloquer P1 et P2.
Ordre total : chaque processus livre par (ts, émetteur) croissant, et il ne livre ts = t que quand plus aucun message d'estampille ≤ t ne peut arriver (FIFO + LC[q] ≥ t pour tout q). Tous livrent donc la même suite. xx-multicast = TO-multicast (diffusion atomique), à la Lamport.
Il est de plus compatible avec la causalité (ordre total causal) :
Liveness : un message n'est livré qu'une fois que chaque processus a envoyé quelque chose de plus récent. Il faut donc que tout processus diffuse régulièrement (en pratique, des messages vides ou des heartbeats quand il n'a rien à dire). Un seul processus muet bloque toutes les livraisons. Et bien sûr aucun crash : un processus mort est un processus muet pour toujours.
L'affectation LC[sender] := ts(m) suppose que les messages d'un même émetteur arrivent dans l'ordre : c'est ce qui autorise à lire LCp[q] comme « plus rien de plus ancien ne viendra de q ». Sans FIFO, un vieux message peut arriver après un plus récent du même émetteur.
Exemple simulé : P1 diffuse m1 (ts 1) puis m5 (ts 2), et m5 double m1 sur le canal vers P3. P3 reçoit m5 puis m4 de P2 (ts 4) : [2,4,5], min = 2, il livre m5. m1 arrive ensuite : LCP3[1] recule de 2 à 1, et P3 livre m1. Ordre sur P3 : m5, m1. Sur P1 et P2 : m1, m5.
Sans FIFO, l'algorithme ne garantit plus aucun ordre : ni total (P3 et P1 divergent), ni causal, ni même FIFO (m1 → m5 sur P1 et pourtant m5 livré d'abord).
La copie A+ répondait que FIFO « semble inutile » car les estampilles suffiraient à remettre les messages dans l'ordre. Le prof a annoté A- sur cette question avec un contre-exemple du même type que ci-dessus : une fois un message livré, un message plus ancien arrivé en retard ne peut plus passer devant. Les estampilles trient ce qu'on a reçu, pas ce qu'on n'a pas encore reçu.
Chaque capteur mesure la température en un point. Calculer le maximum courant et le diffuser à tous, uniquement par diffusion. D'après Ghosh ; l'intérêt porte sur l'ordre de réception des valeurs diffusées.
Hypothèses du prof : modèle atomique de Mattern (une action gardée qui diffuse s'exécute d'un bloc), taille du réseau inconnue, valeurs qui fluctuent, plusieurs capteurs peuvent mesurer la même valeur. Corrigé construit à partir d'une copie étudiante (non notée), vérifié et complété par simulation.
Var mytemp, oldTemp ; Max := undefined {Max = undefined} : Max := mytemp ; broadcast(Init, Max) ; oldTemp := mytemp {oldTemp <> mytemp} : // ma température vient de changer if mytemp > Max then Max := mytemp ; broadcast(Update, Max) if mytemp < oldTemp and oldTemp = Max then // j'étais peut-être le max Max := mytemp ; broadcast(Update, Max) oldTemp := mytemp {message <j> tagué Init} : if j > Max then Max := j {message <j> tagué Update} : if j > Max then Max := j // 1) le max monte else if mytemp > j then Max := mytemp ; broadcast(Update, Max) // 2) je corrige else Max := j // 3) j est le nouveau max
Les élections vues au chapitre 1 (même les versions par approximation) supposent une topologie connue du programmeur : voisins, anneau, identifiants, parfois n. Un réseau de capteurs est volatil (nœuds qui apparaissent, disparaissent, se reconnectent) et sa taille est inconnue ; une élection interrompue par une panne devrait repartir, sans fin si c'est fréquent. Et surtout, une élection converge vers une valeur stable (le plus grand identifiant), alors que la température change tout le temps, y compris à la baisse.
P1 diffuse (Update, 11), P2 diffuse (Update, 14) en même temps. P2 reçoit 11 : 11 ≤ Max et mytemp = 14 > 11, il corrige par un nouveau (Update, 14). P3 (mytemp = 5) reçoit 14 puis la correction 14 : Max = 14. Mais la diffusion de base n'ordonne rien, et m1 (11) arrive chez P3 en dernier : 11 ≤ 14, mytemp = 5 n'est pas > 11, branche 3 : Max := 11. P3 garde une valeur fausse, et personne ne rediffusera 14 pour la corriger.
Même départ : max à 7, puis 11 sur P1 et 14 sur P2 en parallèle (P3 à mytemp 5). Chaque capteur livre aussi ses propres messages dans l'ordre total.
| Ordre total | P1 (mytemp 11) | P2 (mytemp 14) | P3 (mytemp 5) |
|---|---|---|---|
| m1 = 11 | 11 (branche 3) | 14, et diffuse m3 = 14 (branche 2) | 11 (branche 1) |
| m2 = 14 | 14 | 14 | 14 |
| m3 = 14 | 14 | 14 | 14 |
| Ordre total | P1 (mytemp 11) | P2 (mytemp 14) | P3 (mytemp 5) |
|---|---|---|---|
| m2 = 14 | 14 | 14 | 14 |
| m1 = 11 | 11 (branche 3) | 14, et diffuse m3 = 14 | 11 (branche 3) |
| m3 = 14 | 14 | 14 | 14 |
Dans les deux ordres, tout le monde finit à 14. La clé : P2 diffuse m3 après avoir livré m1, donc l'ordre total place m3 après m1 chez tout le monde. La correction arrive forcément après la valeur fausse, jamais avant. Dans le second ordre, P1 et P3 passent brièvement par 11 : l'estimation est transitoirement fausse, puis réparée.
La copie supposait qu'un capteur ne reçoit pas ses propres diffusions, et oubliait que P2 corrige aussi dans l'ordre « 11 puis 14 ». Le résultat final (14 partout) est le même, mais il coûte bien un message m3 dans les deux ordres.
P2 passe de 7 à 14 (diffuse Update 14, m1), puis juste après de 14 à 11 (ancien max = lui, diffuse Update 11, m2). L'ordre total livre m2 (11) puis m1 (14) :
| Ordre total | P1 (mytemp 7) | P2 (mytemp 11) | P3 (mytemp 5) |
|---|---|---|---|
| m2 = 11 | 11 | 11 | 11 |
| m1 = 14 | 14 | 14 | 14 |
Tous finissent à 14 alors que le vrai maximum est 11. Aucune branche ne corrige : personne n'a une température supérieure à 14. L'ordre total seul ne suffit pas.
Hypothèse cachée : l'ordre total doit respecter l'ordre d'émission de chaque capteur (ordre total FIFO, ou plus fort, ordre total causal comme celui de l'exercice 4). P2 a diffusé 14 avant 11, tout le monde doit livrer 14 avant 11.
Sous ordre total FIFO, n'utiliser que Update reste correct : la simulation converge vers le vrai maximum dans tous les ordres testés. Mais le coût explose. Quand un capteur livre (Update, j) avec j plus petit que sa température, il est dans la branche 2 (car Max ≥ mytemp) et rediffuse sa valeur. Donc une diffusion de valeur v déclenche une diffusion de chaque capteur plus chaud, et chacune d'elles déclenche à nouveau celles des capteurs plus chauds qu'elle.
Avec des températures distinctes t1 < ... < tn, notons B(i) le nombre de diffusions provoquées par une diffusion de ti (elle comprise) : B(n) = 1 et B(i) = 1 + B(i+1) + ... + B(n), soit B(i) = 2n-i. Au démarrage, chaque capteur diffuse sa valeur une fois :
| Démarrage | Diffusions | Messages (n-1 destinataires) |
|---|---|---|
| Init puis Update | n | n(n-1) |
| Update seulement | 2n - 1 | (2n - 1)(n-1) |
Vérifié par simulation pour n = 2 à 8, quel que soit l'ordre total. Avec 3 capteurs on passe de 3 à 7 diffusions (la figure de la copie : P1 = 1 réveille P2 et P3, puis P2 réveille P3), avec 20 capteurs de 20 à plus d'un million. Oui, la distinction vaut la peine : Init sert à collecter les valeurs initiales sans déclencher de correction. Un bémol reste : la phase Update a le même comportement en cascade quand un maximum redescend fortement, c'est le défaut de fond de l'algorithme.
La copie propose n · Σ i·n messages. Le décompte exact, pour des valeurs distinctes, est exponentiel : 2n - 1 diffusions. Avec des valeurs égales, la branche 2 ne se déclenche pas (mytemp = j), le coût baisse.
Ancien sujet d'examen. Chaque processus RB-diffuse ses messages, un séquenceur central leur attribue des numéros d'ordre. Dérouler un exemple, puis étudier la causalité sans FIFO, la panne d'un processus, la panne du séquenceur et l'uniformité.
Corrigé fondé sur le homework #4 publié sur le Moodle (« correcSequencerAndInClassExo1 », copie d'étudiant), avec deux compléments signalés en callout.
// sur chaque processus pi upon Init : r := 0 // prochain numéro à livrer pour TO-diffuser m : RB-multicast(<m, i>) // i = identifiant unique de m upon RB-deliver(<m, i>) : ranger <m, i> dans la file d'attente (hold-back) upon RB-deliver(<"order", i, s>) : attendre que <m, i> soit dans la file et que s = r // attente non bloquante TO-deliver(m) ; r := s + 1 // sur le séquenceur upon Init : s := 0 upon RB-deliver(<m, i>) : RB-multicast(<"order", i, s>) ; s := s + 1
Si i n'est que le numéro de l'émetteur, sans FIFO : P0 envoie m1 et m2, P1 les reçoit dans l'ordre m1, m2, P2 dans l'ordre m2, m1, puis tous reçoivent <"order", 0, s>. Lequel des deux messages de P0 est désigné ? P1 et P2 peuvent trancher différemment : l'ordre total est cassé. D'où un identifiant unique (GUID, ou le couple émetteur + numéro local).
P0 diffuse m1 et P1 diffuse m2 en même temps. P2 reçoit m2 en premier, mais sans order il ne peut rien en faire : m2 attend dans la file. Le séquenceur S a reçu m1 d'abord, il diffuse order(m1, 0) puis order(m2, 1). Chacun livre m1 dès qu'il a m1 et l'order 0, puis m2. Tous livrent m1 puis m2, y compris P2 qui avait reçu m2 d'abord. Coût par message : deux diffusions (m, puis son order) et deux sauts de latence.
Non. P0 diffuse m1 puis m2 : m1 → m2 (même émetteur, règle C1). Sans FIFO, la copie de m1 vers le séquenceur peut se faire doubler par m2. Le séquenceur numérote dans son ordre de réception : m2 prend 0, m1 prend 1, et tout le monde livre m2 avant m1. L'ordre est bien total (tous d'accord) mais viole la causalité.
Avec des canaux FIFO et sans panne, l'ordre obtenu est causal. Règle C1 (même émetteur) : FIFO jusqu'au séquenceur, donc m1 numéroté avant m2. Règle C2 (pj livre m1 puis diffuse m2) : pj n'a pu livrer m1 qu'après avoir reçu son order, donc S avait déjà numéroté m1 avant même que m2 existe, et m2 aura un numéro plus grand. Par transitivité, les numéros croissent le long de toute chaîne causale.
Oui. Le message est diffusé en RB. Si l'émetteur crashe au milieu, soit aucun correct ne livre m (et personne ne l'attendra), soit un correct le livre et alors, par RB4, tous les corrects le reçoivent, séquenceur compris. S le numérote et diffuse l'order, lui aussi en RB : tous les corrects reçoivent m et son numéro, et le livrent à la même place. Un processus mort ne bloque personne : r n'attend que des numéros réellement attribués par S.
Solution de la copie : voir le séquenceur comme un leader. Sur <crash | S> (détecteur parfait), on élit un remplaçant, par exemple le processus correct de plus petit identifiant ; grâce à P, chacun le calcule localement sans message d'élection. Le nouveau séquenceur interroge tout le monde, reprend la numérotation après le plus grand numéro déjà attribué, puis numérote les messages restés dans les files sans order.
La difficulté clé : savoir exactement quels numéros l'ancien séquenceur a déjà attribués, et à quels messages, alors qu'il est mort au milieu d'un RB-multicast(order). Un order peut n'avoir atteint que certains processus, et avoir déjà été livré par certains. Si le nouveau séquenceur redonne ce numéro à un autre message, deux processus livrent deux messages différents en position k : l'ordre total est cassé. Les survivants doivent donc se mettre d'accord sur l'ensemble des orders de l'ancien séquenceur avant de reprendre. C'est un problème de consensus (changement de vue), faisable ici grâce au détecteur parfait.
La copie reprend à partir de max(r). Ce n'est pas tout à fait suffisant : r est le prochain numéro qu'un processus peut livrer, mais il peut avoir reçu order(m, k) sans pouvoir livrer (m pas encore arrivé, ou un numéro plus petit manquant). Si le nouveau séquenceur redonne k à un autre message, conflit. Il faut collecter les orders reçus (couples (i, s)), pas seulement r, et repartir de max(s) + 1.
Définition (Défago, slide 70) : uniform total order = si deux processus quelconques, corrects ou non, livrent m et m', ils les livrent dans le même ordre.
Un processus, même sur le point de crasher, ne livre m qu'avec son numéro s, et ce numéro est fixé une fois pour toutes par un seul séquenceur, avant toute livraison. Chacun livre dans l'ordre 0, 1, 2, ... sans trou (condition s = r). Tout processus livre donc un préfixe de la même suite : deux processus ne peuvent pas livrer m et m' dans des ordres différents, qu'ils soient corrects ou non. La copie ajoute : si un fautif livre m, il a reçu m et son order, donc S a vu m ; par RB, les corrects finissent par recevoir m et l'order, et le livrent à la même place.
Ce dernier argument (« tous les corrects finissent par le livrer ») relève de l'accord uniforme et suppose que l'order ne s'est pas perdu avec des processus morts. Avec le RB lazy, non uniforme : S envoie order(m, 5) à P1 seul, P1 livre m en position 5 puis crashe, S crashe aussi. Aucun correct n'a cet order, le nouveau séquenceur peut donner 5 à un autre message m' : le fautif P1 a livré m en 5, les corrects livrent m' en 5. Tant que S ne tombe pas, l'argument de la copie tient. Avec reprise du séquenceur, il faut diffuser les orders en URB (voir la section URB).
11 · Révision active
Le QCM tire des questions au hasard et mélange les options à chaque partie. Les cartes mémo, pour l'auto-test rapide avant l'examen.
Pool de 49 questions. Tire un échantillon au hasard, correction immédiate et explication à chaque réponse.
sent et tout renvoyer à chaque timeout.delivered.