Dernier cours en deux parties. D'abord les transactions distribuées : comment des sites différents valident ou annulent tous ensemble (2PC, 3PC). Puis la collecte d'état global : comment savoir que l'application est terminée ou interbloquée alors que personne ne voit tout.
2PC : phase 1 le coordinateur demande Prepare et collecte les votes, phase 2 il envoie la décision (Commit seulement si tous Oui). Bloquant : si le coordinateur tombe entre les deux phases, les participants prêts restent indécis. 3PC ajoute l'état tampon prepared (p) : il rend le protocole non bloquant sous les hypothèses du cours (au plus une panne, délais bornés). Terminaison : 4 compteurs de Mattern (deux vagues, S1=R1=S2=R2), jeton de Misra (compte les blancs, FIFO), Dijkstra-Feijen-van Gasteren (jeton blanc ou noir, un envoi vers un numéro plus élevé noircit). Interblocage : Chandy-Misra-Haas, sondes P(i,s,r) pour le ET (cycle), probe-echo pour le OU (acks de tous les successeurs).
01 · Transactions distribuées
Une transaction délimite une suite d'instructions qui doit s'exécuter tout ou rien. Répartie sur plusieurs machines, deux problèmes distincts apparaissent : se mettre d'accord pour valider (commit) et ne pas se marcher dessus (concurrence).
Tout ou rien. Un virement C1 → C2 sur deux sites, panne du coordinateur au milieu : C1 débité, C2 jamais crédité, de l'argent perdu.
Les règles d'intégrité sont respectées avant et après (somme des comptes constante par exemple).
Pas d'effet de bord entre transactions concurrentes sur les mêmes objets : tout se passe comme si elles étaient exécutées l'une après l'autre.
Durability : l'effet d'une transaction validée est permanent (log en mémoire stable). Deux mécanismes distincts : le protocole de commit assure l'atomicité répartie, le contrôle de concurrence assure l'isolation.
La sérialisabilité est la propriété de cohérence la plus forte : le résultat est le même que celui d'un ordonnancement série des transactions. Trois familles :
Verrous (ou estampilles) sur les accès en conflit lecture/écriture. Peut bloquer : on détecte un cycle de transactions qui s'attendent et on avorte l'une d'elles.
Aucun blocage. On retient quels objets sont lus et écrits, on construit un graphe de précédence et on cherche un cycle quand une transaction arrive à sa fin, pour décider laquelle avorter.
MVCC et snapshot isolation : chaque transaction lit une version cohérente des données.
Si T2 lit une valeur écrite par T1 et que T1 avorte ensuite, T2 a lu une valeur qui n'a jamais existé : il faut aussi avorter T2 (dirty read). Un tel ordonnancement n'est pas sérialisable. Les lectures fantômes et non répétables cassent aussi la sérialisabilité.
02 · Commit en deux phases
Le coordinateur est le site que le client a contacté en premier. Les participants sont tous les sites touchés par la transaction. À la fin de la transaction (EndTransaction), le coordinateur lance le protocole. Résultat : tous valident ou tous annulent, et les survivants exécutent la décision commune.
Commit naïf : le coordinateur boucle sur « commit » jusqu'à ce que tous acquittent. Insuffisant : un serveur peut avoir avorté (contrôle de concurrence) ou crashé et été restauré depuis un checkpoint, alors que les autres valident. Il faut d'abord demander si tout le monde peut valider.
Coordinateur sur EndTransaction du client : écrire Preparation dans le log ; envoyer Prepare à tous collecter les votes si tous les votes arrivent : écrire le résultat du vote dans le log ; envoyer Commit (tous Oui) ou Abort à tous sinon (timeout) : décider Abort collecter tous les Done puis oublier la transaction Participant : transaction locale terminée, attendre Prepare (avorter si timeout sans Prepare) écrire Ready Oui/Non dans le log en mémoire stable ; envoyer le vote (Non si abort anormal ou abort du contrôle de concurrence) attendre la décision ; écrire Commit ou Abort dans le log ; appliquer (journal R/W) ; envoyer Done
Les deux journaux sont essentiels : le log permet de redémarrer au bon point après une panne d'un participant. Un participant « prêt » (a écrit Ready Oui) a promis de pouvoir valider ou annuler selon la décision, il ne peut donc plus décider seul.
Un protocole est non bloquant si la panne d'un participant n'empêche pas les autres de décider. 2PC a un état indécis : si le coordinateur tombe juste entre les deux phases, les participants prêts ne peuvent ni commit ni abort. 2PC est bloquant tant que le coordinateur n'a pas redémarré, et les participants gardent leurs verrous pendant ce temps.
03 · Commit en trois phases
Skeen (1983). On insère entre le vote et le commit une phase Prepare / Ack et un état p (prepared to commit, état tampon). Le cours renvoie à l'automate du slide 10 (page de S. Gaddam).
| Rôle | États et transitions |
|---|---|
| Coordinateur | q1 → w1 (Commit_Request envoyé). w1 → a1 si un cohort a répondu abort (Abort envoyé) ; w1 → p1 si tous Agreed (Prepare envoyé) ; p1 → c1 quand tous ont répondu Ack (Commit envoyé). |
| Cohort i | q → w (reçoit Commit_Request, répond Agreed) ou a (répond Abort). w → p (reçoit Prepare, répond Ack) ou a (reçoit Abort). p → c (reçoit Commit). |
| Pointillés | F = transition de panne (failure), T = transition de timeout, F,T = les deux. |
L'ensemble de concurrence C(s) d'un état s contient les états que les autres sites peuvent avoir en même temps. En 2PC à deux sites : C(w2) = {c1, a1, w1}. Un site seul survivant dans l'état w voit à la fois commit et abort possibles chez les autres : il ne peut ni valider ni annuler, il bloque.
Avec le tampon : C(w1) = {q2, w2, a2} et C(w2) = {a1, p1, w1}. Aucun état n'a à la fois commit et abort dans son ensemble de concurrence.
Pour tout état non final s : si C(s) contient un commit, la transition de panne va vers commit, sinon vers abort.
Si le site j qui doit envoyer à s a une transition de panne vers commit (abort), alors s a un timeout vers commit (abort). Les survivants imitent ce que le site tombé fera à son retour.
Journal write-ahead, au plus un site tombe pendant l'exécution, protocole synchrone à une transition près (un site n'avance jamais de plus d'une transition sur un autre).
Coordinateur tombé en w1 : les cohortes timeout vers abort, le coordinateur au retour fait abort. Tombé en p1 : les cohortes en p timeout vers commit, le coordinateur au retour fait commit. Cohort tombé avant son Ack : le coordinateur timeout en p1, décide abort et prévient tout le monde, le cohort au retour (état w) fait abort.
« Non bloquant » repose sur des timeouts exacts et au plus une panne. Avec des délais non bornés ou une partition réseau, on ne peut pas distinguer un site lent d'un site tombé, et FLP revient (voir ci-dessous). 3PC coûte aussi une aller-retour de plus que 2PC.
04 · Commit et consensus
Tous les participants aboutissent à la même valeur. Ici, s'il y en a un qui veut abort, la valeur est abort. Au contraire, dans le consensus général la décision peut être la valeur de n'importe quel réplica.
Tout serveur correct finit par prendre une décision irrévocable.
Si tous votent commit et qu'il n'y a aucune panne, alors tous valident.
Un protocole de commit résout le consensus dans un système asynchrone avec pannes. Or FLP (chapitre 5) dit que c'est impossible sans rien faire contre les pannes : ces protocoles incluent donc de la suspicion de pannes et de la gestion de panne. Un site suspecté tombé agit au retour selon l'accord pris, grâce à l'information en stockage permanent.
Une transaction est une liste ordonnée d'opérations : les répliques doivent les écrire dans le même ordre dans leur log, donc un consensus répété (MultiPaxos : un chef stable qui numérote chaque valeur). Chaque shard est répliqué, et chaque valeur du 2PC (PREPARE:OUI, COMMIT) est elle-même décidée par un consensus entre les répliques du shard. Le coordinateur n'est alors plus le seul point de panne des données.
| Étape | Slide 15-16 : transaction Write(compte1,x) ; Write(compte2,y) sur deux shards A et B |
|---|---|
| 1 à 2 | Le client demande le commit. Le coordinateur de transaction envoie PREPARE au leader MultiPaxos de A et de B. |
| 3 à 5 | Chaque leader ajoute PREPARE dans son log Paxos (index 101 et 45 sur l'exemple), le réplique aux accepteurs, obtient un quorum, puis répond « I am Ready ». |
| 6 | Les deux shards sont prêts : le coordinateur décide COMMIT et ajoute COMMITTED à son log global. |
| 7 à 9 | COMMIT (notification asynchrone) à chaque shard : consensus local (index 103 et 47), puis libération des verrous et données finales. |
Le consensus seul ne connaît pas les dépendances causales entre clients. Solution classique : MultiPaxos avec un seul coordinateur qui estampille chaque requête (s'il est remplacé, le nouveau rattrape), et chaque proposeur attend que sa valeur courante soit décidée avant d'en proposer une autre (causalité FIFO). Google Spanner date le début de chaque transaction avec l'API TrueTime : cohérence externe (linéarisabilité).
05 · Collecte d'état global
On veut détecter un état global particulier : la terminaison (pour passer à la phase suivante d'une application) ou l'interblocage (pour le réparer). Ou compter : messages échangés, processus présents. Problème : les états locaux et les canaux ne sont pas collectés au même instant. C'est le problème du snapshot cohérent, mais il faut en plus fusionner les morceaux d'une manière adaptée à l'état cherché.
06 · Détection de terminaison
Tous les messages envoyés ont été reçus et traités : S = R, plus rien en transit. Il suffit de compter.
Tous les processus sont passifs et aucun message en transit. Un passif ne redevient actif que sur réception d'un message.
P1 envoie un message à P2 puis devient passif. L'observateur voit « P2 passif », puis « P1 passif ». Mais entre les deux, le message a atteint P2 qui est redevenu actif. Un observateur qui visite les processus un par un peut voir un état qui n'a jamais existé : une coupe incohérente.
Une vague (lancée depuis un processus, par exemple le leader sur un anneau, après un timeout) lit au passage les compteurs locaux s (envoyés) et r (reçus) de chaque processus. Si S = R, on proclame la terminaison. Valable seulement si la vague correspond à une coupe cohérente, sinon fausse détection :
Deux remèdes : interdire les coupes incohérentes (Chandy-Lamport, FIFO ou non FIFO étendu), ou la solution de Mattern, simple : deux vagues successives dont la seconde démarre après la fin de la première.
Si E1 = R1 = E2 = R2 (envoyés et reçus des deux vagues), alors l'application est terminée. Au plus deux vagues après la terminaison suffisent à la détecter.
Pourquoi E1 = R1 = E2 = R2 implique que plus rien n'est en transit à la fin de la vague 1.
Temps absolus : d1 < f1 < d2 < f2 (début et fin des vagues 1 et 2). On note E(t) et R(t) le nombre total de messages émis et reçus sur tous les processus jusqu'à t (un observateur « Dieu » ; aucun mécanisme réel ne permet de les connaître).
| Propriété | Énoncé |
|---|---|
| P1 | Les compteurs d'un processus sont croissants dans le temps. |
| P2 | E(t1) ≤ E(t2) et R(t1) ≤ R(t2) pour t1 ≤ t2. |
| P3 | R(t) ≤ E(t) pour tout t (on ne reçoit pas plus que ce qui a été envoyé). |
| P4 | R1 est collecté avant f1 : R1 ≤ R(f1). |
| P5 | E2 est collecté après d2 : E(d2) ≤ E2. |
Si R1 = E2 : par P5 et P4, E(d2) ≤ E2 = R1 ≤ R(f1). Par P2, E(f1) ≤ E(d2). Donc E(f1) ≤ R(f1). Avec P3, R(f1) ≤ E(f1). Donc E(f1) = R(f1) : à la fin de la première vague, tout message émis est reçu, plus rien n'est en transit. L'algorithme avait donc terminé.
07 · Détecter les états passifs
Principe général commun à Misra et Dijkstra-Feijen-van Gasteren : des vagues successives. Un message de contrôle (le jeton) visite chaque processus à tour de rôle (c'est la seule façon d'observer l'état global) et n'est traité qu'une fois le processus passif, sans message applicatif en attente. Si le processus est resté passif depuis la dernière visite, il ajoute « passif » à l'information du jeton, sinon « actif ». L'initiateur relance une vague si le jeton dit « actif », sinon il proclame la terminaison. La question : comment garantir qu'aucun message n'est en transit ? Chaque algorithme répond différemment.
Messages applicatifs et jeton circulent sur l'anneau unidirectionnel. Le jeton « vide » les canaux : sur un canal FIFO, un message envoyé avant le jeton arrive avant lui. Le jeton compte les processus blancs consécutifs.
Initialement tous les processus sont blancs ; l'initiateur est P0. Sur tout Pi, réception d'un message applicatif : état := noir Pi, i dans 1..n-1, réception du jeton (une fois passif) : si état = noir alors token := 1 sinon token := token + 1 état := blanc ; transmettre le jeton P0, réception du jeton : si (état = blanc et token = n) alors terminé sinon état := blanc ; transmettre token := 1
Le jeton ne vaut n que si les n derniers processus visités étaient blancs et que P0 l'est resté : aucun message reçu pendant un tour complet, donc rien en transit (FIFO) et tout passif. Un message reçu juste avant le jeton coûte un tour de plus.
Les messages applicatifs peuvent suivre n'importe quelle topologie, seul le jeton suit l'anneau. Risque : token = n alors qu'un message applicatif est encore en transit. Solutions : communications synchrones (rien n'est jamais en transit), et un anneau construit en connectant les processus par id croissant, avec des messages applicatifs « en avant » ou « en arrière » par rapport à l'anneau. Il faut alors un mécanisme en plus pour dire qu'un message applicatif a pu réactiver un processus que le jeton avait déjà vu passif.
Anneau 0 → n-1 → n-2 → ... → 1 → 0. Communications synchrones (ou asynchrones bornées par D) : un message n'est jamais en transit. Le jeton n'est traité que s'il n'y a plus de message applicatif dans la file de réception.
R1 un processus non initiateur qui envoie un message à un processus de numéro plus élevé (= en arrière dans l'anneau) devient noir // il réactive peut-être un processus que le jeton a déjà visité R2 un processus noir qui envoie le jeton le rend noir ; un processus blanc qui transmet le jeton lui garde sa couleur R3 un processus noir qui envoie le jeton à son successeur redevient blanc Initiateur : jeton blanc reçu et lui-même blanc alors terminé sinon nouveau jeton blanc
08 · Détection d'interblocage
Interblocage de ressources : ressources non partageables (exclusion mutuelle), chaque processus en demande au moins deux à la fois, pas de préemption (seul le propriétaire libère), et un ensemble de processus est interbloqué quand le graphe d'attente (wait-for graph, WFG) contient un circuit orienté. Détecter, c'est exhiber ce graphe réparti : un snapshot qui ne contient pas forcément tous les processus. Aucun processus ne voit le WFG entier.
[R1 ET R2 ET R3 ...] : un processus ne progresse qu'une fois toutes ses ressources obtenues. Interblocage = cycle dans le WFG.
[R1 OU R2 OU R3 ...] : un seul message suffit à le débloquer. Mixte : [R1 OU (R2 ET R3)]. Un cycle ne suffit plus : il faut qu'aucun des attendus ne puisse répondre.
Notations : w(j) = vrai si j attend ; depend[j,i] = vrai si j est un successeur (direct ou non) de i : « Pi est bloqué, directement ou indirectement, parce que Pj est bloqué ». Une sonde P(i, s, r) : i initiateur, s émetteur, r receveur (Ps est bloqué parce qu'il attend Pr). Idée : si P(i, x, i) revient à Pi, Pi est sur un circuit du WFG donc interbloqué (il est bloqué parce que lui-même est bloqué).
Programme du processus k, réception de P(i, s, k) : si w[k] et k ≠ i et ¬depend[k, i] alors envoyer P(i, k, j) à chaque successeur j ; depend[k, i] := vrai si w[k] et k = i alors k est interbloqué
Un processus qui n'attend personne ignore la sonde (il agira, donc débloquera). Sinon : première sonde reçue : marquer l'émetteur comme parent, transmettre la sonde aux successeurs ; sonde suivante : renvoyer un ack à son émetteur ; ack reçu de tous les successeurs : envoyer un ack au parent. L'interblocage est détecté si l'initiateur reçoit l'ack de tous ses successeurs (aucun d'eux ne peut le débloquer). L'algorithme ressemble à la détection de terminaison de Dijkstra-Scholten, aussi de type probe-echo.
Dans le premier graphe, P1, P2, P3, P4 sont tous sur des circuits : interblocage de ressources au sens ET, mais pas de communication : P5 est libre et finira par débloquer P3, puis P2, P1 et P0. Sans P5, P0 est OU-interbloqué. P0 est bloqué mais pas sur un circuit : on ne le tuera pas pour réparer. L'algorithme du OU est plus général que celui du ET.
09 · Pièges
| Piège | À retenir |
|---|---|
| 2PC « tolère » les pannes | Il les survit grâce aux logs, mais il bloque si le coordinateur tombe entre les phases (participants prêts indécis). |
| 3PC non bloquant sans condition | Hypothèses : au plus une panne, timeouts exacts, pas de partition. Sinon l'accord peut être violé. |
| Commit = consensus général | En commit, un seul Non impose abort ; en consensus la décision peut être la valeur de n'importe qui. |
| Une vague S = R suffit | Non : coupe incohérente possible. Il faut deux vagues qui s'accordent (E1=R1=E2=R2), la seconde après la fin de la première. |
| Misra sans FIFO | Le jeton peut doubler un message en transit : token = n à tort. |
| Traiter le jeton avec une file non vide | Le processus se déclarerait passif alors qu'il va encore travailler et envoyer. |
| DFvG : qui noircit ? | Seul un envoi vers un numéro plus élevé (déjà visité par le jeton) noircit. L'envoi vers un numéro plus bas est sans danger. |
| Chaque processus bloqué détecte | Seul un initiateur sur un circuit détecte, dans le cas ET. |
| Cycle = interblocage | Vrai pour le ET, faux pour le OU (un successeur libre suffit à tout débloquer). |
10 · Exercices corrigés
Les six exercices de la feuille de TD du dernier cours (détection de terminaison, interblocage, 2PC et 3PC). Les exercices 1 à 3 ont été faits en cours.
Source des corrigés Les exercices 1 à 3 ont été faits en cours avec des schémas annotés et la preuve de Mattern (réutilisés ci-dessous). Le prof n'a publié aucun corrigé des exercices 4, 5 et 6 : ces réponses sont rédigées à partir du cours.
Scénario où une seconde vague trop précoce valide une terminaison qui n'a pas eu lieu.
Les trois processus P0, P1, P2 ont des compteurs s (envoyés) et r (reçus). Les vagues lisent P0, puis P1, puis P2. Construisons l'exécution (animation ci-dessus, « trop tôt »).
| Événement | Effet |
|---|---|
| P1 envoie z à P0 (lent) | s1 = 1 |
| vague 1 lit P0 ; vague 2 lit P0 aussitôt après | (0, 0) pour les deux |
| P0 envoie y à P2, P2 le reçoit | s0 = 1, r2 = 1 (invisible pour P0 déjà lu) |
| les deux vagues lisent P1 puis P2 | (1, 0) et (0, 1) pour chacune |
Chaque vague trouve S = 1 et R = 1, donc E1 = R1 = E2 = R2 = 1 : terminaison proclamée à tort, z est encore en transit vers P0. L'envoi de y après la lecture de P0 (compté en moins) a masqué la réception de z non encore faite (comptée en moins aussi) : S et R sont tous deux faux et se compensent.
La cause est que la vague 2 a démarré avant la fin de la vague 1 (d2 < f1) : la preuve de Mattern a besoin de f1 < d2. Quand la vague 2 attend, elle lit P0 après l'arrivée de z : S2 = R2 = 2 ≠ 1, pas de conclusion, et c'est une troisième vague qui confirme (animation « après la fin de la vague 1 »).
Au plus 2 tours de jeton après la terminaison ? Faut-il traiter les messages en attente avant le jeton ? Et sans FIFO ?
Réponses rédigées par moi à partir du slide 22 et du schéma annoté du prof (anneau 0..4, un message de P2 vers P3 sur un canal FIFO, jeton avec les valeurs 1 et 2).
Soit T l'instant où l'application est globalement terminée : tous passifs, rien en transit. Après T, plus aucun message applicatif n'est reçu, donc aucun processus ne devient noir. Le tour en cours à T a pu démarrer avant et échouer (il n'est pas compté). Considérons le premier tour qui démarre après T : il visite chaque processus, et chaque processus noir devient blanc en transmettant le jeton (et P0 est blanc en le relançant). À la fin de ce tour, tous les processus sont blancs pour toujours. Ce tour peut échouer (token < n si un noir a remis le compteur à 1), mais le tour suivant, lui, traverse n blancs : token = n et P0 blanc, terminaison détectée. Donc au plus 2 tours démarrés après T.
Oui. Un processus ne doit traiter le jeton que s'il est passif (file vide, plus rien à faire). Sinon il passerait blanc et transmettrait le jeton alors qu'il a encore un message à traiter, qui peut le conduire à envoyer à un processus déjà visité : « blanc » ne voudrait plus dire « passif depuis la dernière visite » et la détection serait fausse.
L'algorithme est faux. Il compte sur le fait que, sur un canal, un message envoyé avant le jeton arrive avant lui (schéma du prof : m de P2 vers P3 devant le jeton, donc P3 devient noir avant de voir le jeton et le compteur repart à 1). Sans FIFO, le jeton peut doubler m : P3 est blanc et passif quand le jeton passe, token atteint n, puis m arrive et réactive P3 : fausse terminaison.
Un seul tour suffit quand ? Extension asynchrone bornée par D ? Pourquoi échoue-t-il en asynchrone FIFO ? Routage par l'anneau ?
Réponses rédigées par moi à partir du slide 24 et des deux schémas annotés (backward-forward, et cas asynchrone borné D avec l'annotation du prof sur la file M puis T).
Quand aucun processus ne noircit pendant le tour, c'est-à-dire quand aucun message n'est envoyé vers un numéro plus élevé (« en arrière » par rapport au sens du jeton) : le jeton, parti blanc, revient blanc, et l'initiateur est blanc. Par exemple si l'application est déjà terminée au départ du jeton, ou si tous ses messages vont vers les numéros plus bas (dans le sens du jeton). Contrairement à Misra où toute réception noircit, seule la réactivation d'un processus déjà visité coûte un tour de plus.
Un message peut être en transit jusqu'à D après son envoi. Le processus qui reçoit le jeton attend D avant de le traiter, puis regarde sa file : si aucun message applicatif n'est arrivé après D, tout message qui était en transit a eu le temps d'atteindre sa boîte aux lettres, on est sûr et on traite le jeton T (annotation du prof sur le schéma : « process the token only after D »). Sinon le processus traite d'abord le message.
Les règles ne noircissent que l'envoi en arrière. Un message envoyé vers un numéro plus bas (que le jeton n'a pas encore visité ce tour) laisse l'émetteur blanc. Si ce message est lent, le destinataire est passif avec une file vide quand le jeton passe, le laisse blanc, puis le message arrive et le réactive, sans que personne ne soit noir : le jeton revient blanc et l'initiateur conclut à tort. Avec des communications synchrones (ou bornées avec l'attente de D), le message est déjà arrivé quand le jeton passe.
Si un processus se contente de retransmettre au suivant les messages qui ne lui sont pas destinés (sans noircir ni devenir actif), tout passe par les canaux FIFO de l'anneau : un message envoyé avant le jeton arrive avant lui sur chaque canal, donc le jeton « vide » les canaux comme chez Misra. La différence avec Misra : Misra compte les processus blancs (il faut connaître n exactement, token = n) alors qu'ici l'initiateur ne regarde que la couleur du jeton et la sienne : le nombre de processus n'a pas besoin d'être connu.
Un algorithme similaire où ni le nombre de processus ni un ordre sur un anneau ne sont nécessaires, un seul processus arbitraire (le leader) déclenchant la détection.
Réponse rédigée par moi : c'est l'algorithme de Dijkstra-Scholten, cité au slide 30 comme algorithme de type probe-echo voisin de Chandy-Misra-Haas.
Chaque processus garde : parent (celui qui l'a engagé), déficit = nombre de ses messages applicatifs pas encore acquittés. Envoi d'un message applicatif : déficit := déficit + 1 Réception d'un message applicatif de q : si le processus n'est pas engagé alors parent := q (premier message : il est engagé, pas d'ack tout de suite) sinon envoyer immédiatement ack à q Réception d'un ack : déficit := déficit - 1 Quand le processus est passif et déficit = 0 : si parent existe, envoyer ack à parent, se désengager ; si c'est l'initiateur : terminé
Les processus engagés forment un arbre enraciné à l'initiateur, qui se replie des feuilles vers la racine. L'initiateur ne connaît ni n ni l'ordre des processus. Mode de transmission : un mode asynchrone suffit (les acquittements remplacent l'hypothèse de synchronisme), il faut seulement des canaux fiables ; la détection est correcte sans FIFO ni borne de délai.
Représentation du WFG, et Chandy-Misra-Haas est-il applicable ?
Réponse rédigée par moi à partir des slides 25 à 30 (modèles ET et OU).
Une requête « OU de groupes ET » ne se dessine pas avec de simples arêtes. On ajoute pour chaque processus Pi un niveau intermédiaire : Pi est relié à des nœuds de clause C1, C2, ... (arêtes OU : une seule clause satisfaite suffit), et chaque nœud de clause est relié aux propriétaires des ressources de cette clause (arêtes ET : tous doivent libérer). C'est un graphe à deux types d'arêtes (ou un hypergraphe).
Non, pas tel quel. L'algorithme ET (edge chasing) conclut à l'interblocage dès qu'une sonde revient à l'initiateur, c'est-à-dire sur un cycle. Or ici un cycle ne suffit pas : le processus peut sortir par une autre clause, dont toutes les ressources sont libres. On aurait de faux interblocages. L'algorithme OU (probe-echo) traite tous les successeurs comme des alternatives (un seul suffit), ce qui est faux pour les groupes ET.
Alternative (esquisse). Étendre le probe-echo : l'écho ne renvoie plus un simple ack mais un booléen interbloqué ou non. Un processus k bloqué envoie des sondes aux propriétaires de toutes les ressources de toutes ses clauses. Il est interbloqué si et seulement si pour chaque clause, au moins un des propriétaires est interbloqué (ET sur les clauses, OU sur les ressources d'une clause). Un processus libre répond « non interbloqué » ; un processus déjà engagé qui reçoit une nouvelle sonde répond « interbloqué » provisoirement (on cherche le plus grand ensemble bloqué, comme pour une définition par point fixe). L'initiateur conclut quand tous ses échos sont revenus. Cette solution n'est pas prouvée ici.
En quel sens 3PC est-il non bloquant par rapport à 2PC ?
Réponse rédigée par moi à partir du slide 9-10 et de la page de Gaddam fournie.
| 2PC (Gray) | 3PC (Skeen) | |
|---|---|---|
| Phases | Vote (Prepare / Oui ou Non), puis décision (Commit ou Abort) puis Done. | Commit_Request / Agreed, puis Prepare / Ack, puis Commit. |
| États du participant | q, w (prêt), a, c | q, w, p (prêt à valider, tampon), a, c |
| Ensemble de concurrence de w | contient c et a | ne contient jamais c et a ensemble |
| Panne du coordinateur entre les phases | les participants prêts sont indécis, ils bloquent jusqu'au retour du coordinateur | les survivants appliquent leur timeout (w vers abort, p vers commit) et décident seuls |
| Hypothèses | logs en mémoire stable, timeouts pour éviter l'attente infinie | logs, au plus une panne, timeouts exacts, pas de partition |
| Coût | 2 aller-retours | 3 aller-retours (plus de messages et de latence) |
« Non bloquant » veut dire : une panne ne suffit pas à empêcher les sites opérationnels de décider en examinant leur état local. C'est exactement ce que le tampon p permet : un site qui voit p sait que tous ont voté Oui donc commit est sûr ; un site en w sait que personne n'a pu valider donc abort est sûr. En contrepartie, 3PC suppose un réseau sans partition et des délais bornés : avec des délais non bornés, FLP interdit une garantie d'accord et de terminaison. C'est pourquoi les systèmes réels remplacent le coordinateur par un consensus (2PC au-dessus de MultiPaxos, slide 15).
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 46 questions. Tire un échantillon au hasard, correction immédiate et explication à chaque réponse.