Ce qui tombe d'après les annales, les fiches de chaque chapitre au même format (français, termes et phrases-réponses en anglais), les algorithmes en pseudo-code court, les pièges, et un recap PDF à imprimer.
01 · Le contrôle
Lundi 2 novembre 2026, après-midi, 3 h, examen papier.
Autorisé (message du prof du 1er novembre) : les slides imprimées distribuées, tous ses tests, et ses notes, qui peuvent être imprimées.
Selon le prof : long mais facile. Surtout faire tourner des algorithmes fournis et les comprendre, plus des questions sur les slides (certaines vues en cours). Les exercices Moodle et leurs corrections sont utiles.
02 · Recap imprimable
Un seul document « tout ce qu'il faut pour le contrôle » : sommaire, ce qui tombe, quel algorithme quand, puis pour chacun des six chapitres les fiches, les algorithmes clés, les réponses types des annales, les pièges et des schémas. A4, deux colonnes, numéros de page.
Accents de couleur pour repérer les blocs (pièges, anglais, algorithmes).
Aucune couleur porteuse de sens : traits, motifs et libellés (PIEGES, EN, TOMBE), contraste fort pour l'impression laser.
Les mêmes pages, avant impression.
03 · Ce qui tombe
Annales de 2011 à 2019 et corrigé de l'exercice 5 de 2022. Pas de correction officielle publiée pour la plupart ; les PDF sont dans le dossier Moodle (non republiés ici).
| Thème | Années | Chap. |
|---|---|---|
| Checkpointing : CIC (Briatico), calcul du N de recovery, forced checkpoints | 2011, 2012-13, 2013-14 | 3 |
| Checkpoint avant / après chaque envoi, graphe de dépendances, ligne de recovery, domino | 2012, 2022 | 3 |
| Ordres causal et total : 2 propriétés causales (safety / liveness), séquenceur sans FIFO, reprise du séquenceur | 2011, 2012-13, 2013-14 | 4 |
| CBCAST à horloges vectorielles : livrabilité, états hold | 2017-18, 2019 | 4 |
| Consensus uniforme contre non uniforme, flooding en N-1 étapes, hiérarchique | 2011, 2012, 2019 | 5 |
| Détecteurs ◇P, élection de leader, « pas plus d'un jour » = synchrone | 2011, 2012 | 5 |
| Exclusion mutuelle : Ricart-Agrawala, token ring, Suzuki-Kasami, preuves ME1 à ME3 | 2011, 2012-13, 2013-14, 2017-18 | A |
| Élection : probe-echo (compter processus ou arêtes), Chang et Roberts, Bully, inondation, Franklin | 2011, 2012, 2012-13, 2013-14, 2017-18, 2019 | 1 |
| Temps : Cristian (preuve de la précision), horloges vectorielles (diagonale), estampilles | 2012, 2017-18, 2013-14 | 2 |
| Terminaison : quand détecter, Misra (nombre de tours), jeton sur anneau | 2012-13, 2017-18, 2019 | 6 |
Thème présent dans quatre annales (Ricart-Agrawala, token ring, Suzuki-Kasami, preuves ME1 à ME3). Il n'a pas encore de chapitre en ligne : la fiche de l'annexe (chapitre A) est tirée des slides 2021-DistAlgo_Exmut.pdf.
04 · Quel algorithme quand
| Situation | Algorithme | Chap. |
|---|---|---|
| Élire le plus grand sur un anneau à sens unique, sans panne | Chang et Roberts (fin détectée gratuitement, pire cas n(n+1)/2) | 1 |
| Élire sur un anneau à double sens avec garantie au pire cas | Franklin (2N log N messages au pire, log N rondes) | 1 |
| Collecter ou diffuser avec confirmation sur un graphe quelconque, un initiateur | Probe-Echo (2E messages, arbre couvrant) | 1 |
| Élire avec pannes de processus, graphe complet, ids connus, timeout | Bully (O(n²), pire O(n³)) | 1 |
| Ordonner des événements, savoir si deux événements sont concurrents | Horloges vectorielles (Lamport seul ne prouve pas la concurrence) | 2 |
| Photo cohérente de l'état global (processus + canaux) | Chandy-Lamport (canaux FIFO, marqueurs) | 2 |
| Synchroniser une horloge sur un serveur de temps / entre pairs | Cristian (externe, ±(RTT/2 - min)) / Berkeley (interne, moyenne) | 2 |
| Reprendre après panne en revenant à une coupe cohérente | Checkpointing coordonné (bloquant ou non) ou CIC (index piggybacké) | 3 |
| Ne faire reculer que le processus fautif | Message logging pessimiste (log avant exécution) | 3 |
| Livrer à tous les corrects si un correct livre (avec détecteur P) | Reliable Broadcast lazy ; uniforme : URB All-Ack | 4 |
| Respecter la causalité des diffusions | CBCAST (vecteurs de diffusion, livrer si VC_m ≤ VC) | 4 |
| Même ordre de livraison partout | Total order : séquenceur (2N messages) ou Lamport + FIFO (mysterious broadcast) | 4 |
| Consensus avec un détecteur P, décision de chaque chef à son tour | Consensus hiérarchique (non uniforme) ; uniforme : PROPOSAL + ACK | 5 |
| Consensus avec ◇S et majorité de corrects | Chandra-Toueg (coordinateur tournant, f < n/2) ; Paxos si leader seulement à terme | 5 |
| Exclusion mutuelle répartie avec horloges, canaux FIFO | Lamport (3(N-1) messages) ; sans FIFO et sans release : Ricart-Agrawala (2(N-1) messages) | A |
| Exclusion mutuelle avec un jeton | Anneau à jeton (1 message par sortie, (N-1)-fairness) ; graphe complet : Suzuki-Kasami (req[], last[], jeton = (Q, last)) | A |
| Valider ou annuler une transaction répartie | 2PC (bloquant) ; 3PC (non bloquant sous ses hypothèses) | 6 |
| Savoir que l'application est terminée (comptage) | Mattern, 4 compteurs : deux vagues, E1=R1=E2=R2 | 6 |
| Savoir que l'application est terminée (jeton sur anneau) | Misra (FIFO, token = n) ; Dijkstra-Feijen-van Gasteren (blanc ou noir) ; sans n ni anneau : Dijkstra-Scholten | 6 |
| Interblocage : ressources (ET) / communication (OU) | Chandy-Misra-Haas : sondes P(i,s,r) / probe-echo avec acks | 6 |
Chapitre 1
Tombe à presque chaque examen : probe-echo (compter processus ou arêtes, 2011 et 2012), Chang et Roberts avec tous candidats (2012-13), Bully et connaissance de N (2013-14), inondation en D rondes (2017), Franklin (2019). Le chapitre complet en ligne
Avant tout algorithme il faut dire ce que le système permet : des processus qui ne partagent rien et n'ont pas d'horloge commune, qui ne se parlent que par messages. Une action gardée est une règle « si la garde est vraie, exécute le corps d'un coup » : Ip quand la garde porte sur l'état local, Rp quand elle porte sur l'arrivée d'un message. Le non-déterminisme (plusieurs gardes vraies) force à raisonner pour tous les ordres possibles, pas pour un seul.
Conséquence pratique à l'examen : quand on déroule un algorithme, on est libre de choisir l'ordre des actions, mais il faut que le résultat soit juste quel que soit cet ordre. Le piège classique est un message qui arrive avant l'action interne de démarrage : sans garde started dans les deux règles, l'action interne reste bloquée.
Chaque candidat écrit son numéro sur un papier et le passe à son voisin. Un processus qui reçoit un papier plus grand que tout ce qu'il a vu le fait suivre, sinon il le jette. Un papier qui revient à son auteur a battu tout le monde : l'auteur est le plus grand, il l'a appris sans rien demander (fin détectée gratuitement) et proclame.
Le coût est la somme des distances parcourues par les papiers. Un papier meurt dès qu'il rencontre un processus qui a vu plus grand. Si les ids décroissent dans le sens du tour, chaque papier survit longtemps (pire cas) ; s'ils croissent, tous meurent au premier saut sauf le max (meilleur cas).
L'initiateur envoie un probe à tous ses voisins. Un processus qui reçoit son premier probe retient l'expéditeur comme parent et envoie des probes aux autres voisins. Quand il a reçu autant de messages (probe ou echo) qu'il a de voisins, il envoie un echo à son parent. L'initiateur termine quand il a tout reçu.
Le résultat est un arbre couvrant qui dépend des vitesses des liens. Chaque arête porte exactement deux messages : probe et echo si elle est dans l'arbre, deux probes croisés sinon. D'où le total 2E.
Anneau à sens unique sans panne : Chang et Roberts. Anneau à deux sens avec garantie au pire cas : Franklin (la moitié des actifs disparaît à chaque ronde). Graphe quelconque sans panne : Tel (un Probe-Echo par candidat, la vague du max l'emporte). Pannes de processus avec délai borné : Bully (le plus grand vivant gagne, mais deux leaders sont possibles si un processus redémarre). Serveur fiable : serveur central (le premier candidat arrivé gagne).
Processus P0..Pn, mémoire locale, ni mémoire partagée ni horloge globale. Envoi seulement aux voisins. Canaux fiables, FIFO. Pas de panne sauf mention.
Temps : async (défaut, délai fini non borné : lent et mort indistinguables, pas de timeout fiable), sync (borne Δ connue, rondes, timeout 2Δ fiable), async borné connu (timeout possible, Bully).
FIFO : sur un canal P→Q, réception dans l'ordre d'envoi. Rien de garanti entre deux canaux différents. Fabriquer FIFO : numéros de séquence et attente.
Ip: { garde } règle interne (ne reçoit jamais de message). Rp: { msg } règle message (receive au début). Plusieurs gardes vraies : choix au hasard, action exécutée en entier (atomique).
Piège : un message traité avant Ip rend M ≠ 0 et Ip reste bloquée à jamais. Correctif : started dans les deux gardes ; une garde fausse laisse le message dans la boîte.
Coût = messages (compter les flèches) + temps (plus longue chaîne de messages qui se déclenchent, 1 unité = 1 message). Messages envoyés en parallèle = 1 seule unité de temps.
Toujours donner le nombre ET la situation qui le provoque (pire, meilleur cas). O(1) < O(n) < O(n log n) < O(n²) < O(n³).
EN Cost is counted in messages and in time, where one time unit is one message in a causal chain.
Casser la symétrie : choisir un coordinateur ; un seul élu et tous les non fautifs connaissent le même. Valeurs uniques, ordre total (souvent max id). Étapes : détection, préparation, élection, proclamation.
Approximation distribuée : chacun garde le meilleur vu et l'améliore. Complet naïf : pire O(N³) (reçu en ordre croissant), meilleur O(N²), temps N-1. Complet avec N connu : N(N-1) messages, temps 1.
EN Election breaks symmetry: exactly one leader, and every correct process knows the same one.
Anneau à sens unique, pas de panne. Je passe un numéro seulement s'il est > M (le plus grand vu), sinon je le jette. Je reçois mon propre numéro : j'ai gagné (fin détectée gratuitement). Proclamation : fait le tour (+ n messages).
Coût = somme des distances parcourues par chaque papier. Pire : ordre décroissant dans le sens du tour, le papier i fait i sauts, n(n+1)/2 = O(n²). Meilleur : ordre croissant, (n-1) + n = 2n-1. Moyenne O(n log n). Temps O(n). Plus n messages de proclamation. 2 candidats sur N : N + d (1 ≤ d ≤ N-1), meilleur N+1, pire 2N-1, moyenne 3N/2.
V1 : un dormeur qui reçoit j le relaie et ne candidate jamais, élu = max des réveillés seuls. V2 : un dormeur qui reçoit j < moi jette j et envoie MON numéro, élu = max global.
EN A process forwards an id only if it is larger than the largest it has seen; receiving its own id means it won.
1 initiateur, réseau quelconque connexe, liens bidirectionnels. 1er probe reçu de q : parent := q, probe aux autres voisins. Chaque message reçu : compteur++ ; compteur = nombre de voisins : echo au parent (initiateur : fin).
Construit un arbre couvrant. Messages 2E (arête de l'arbre : probe + echo ; hors arbre : 2 probes croisés). Temps ≤ 2N. Usages : diffusion avec confirmation, collecte dans l'echo (sac S, union). Un seul echo par processus. Compter les arêtes : echo 0 si déjà visité (2012).
L'arbre dépend des vitesses des liens (parent = probe arrivé en premier) : triangle depuis A, 3 arbres possibles.
EN The first probe received defines the parent; a process answers with an echo once every neighbour has answered.
Tel (réseau quelconque) : chaque candidat lance un Probe-Echo ; j > M : changer de camp (M := j, parent := q, nb := 1, relayer) ; j = M : nb++ ; j < M : ignorer. Seule la vague du max revient complète. ≤ 2E par vague, pire O(N·E).
Franklin : anneau double sens, pas de panne, rondes. Un actif envoie son numéro à gauche et à droite, compare aux 2 actifs voisins : un voisin plus grand, éliminé (relais seulement) ; reçoit son propre numéro : élu. Au moins la moitié éliminée par ronde : ≤ log N rondes. 2N messages par ronde, 2N log N au pire, garanti au pire (≠ C&R).
Bully : pannes possibles, liens fiables, délai borné, graphe complet, ids connus. Leader ⇔ tous les plus grands morts. Pi envoie Election aux j > i ; Pj vivant répond Reply et devient candidat ; personne ne répond avant timeout : Leader aux j < i. O(n²) messages, O(n³) au pire (n-1 pannes pendant l'élection), temps O(n). Piège slide 27 : un processus redémarré ou lent se proclame aussi, deux leaders.
Serveur central : étoile, serveur jamais en panne, oracle de panne du leader. 1er be_candidate = élu (pas forcément le max), search_leader servi seulement si leader ≠ vide. 2N messages, temps O(1).
Chang et Roberts (anneau à sens unique)
Ip: { ¬started } started := vrai ; M := p ; send ⟨p⟩ au suivant Rp: { message ⟨j⟩ arrivé } si j = p alors leader := p ; proclamer sinon si j > M alors M := j ; send ⟨j⟩ au suivant sinon jeter j
Probe-Echo
Rp: { ⟨probe⟩ de q } si premier probe : parent := q ; probe aux voisins ≠ q Rp: { ⟨probe⟩ ou ⟨echo⟩ reçu } compteur++ si compteur = |voisins| : echo à parent // initiateur : fin
Bully (Pi)
Ip: { détection du leader mort } send ⟨Election⟩ à tous les j > i ; attendre timeout Rp: { ⟨Election⟩ de k < i } send ⟨Reply⟩ à k ; lancer sa propre élection Rp: { ⟨Reply⟩ } attendre ⟨Leader⟩ // timeout sans Leader : recommencer timeout sans Reply : leader := i ; send ⟨Leader⟩ à tous les j < i
annales 2012-13, cours
Énoncé. Anneau de 5 processus, sens du tour = sens des flèches, tous candidats. Compter les messages d'élection pour des ids croissants puis décroissants dans le sens du tour.
Pire cas n(n+1)/2 messages (ids décroissants dans le sens du tour), meilleur cas 2n-1 (croissants), plus n pour la proclamation.
EN Worst case n(n+1)/2 election messages, best case 2n-1, plus n messages to announce the leader.
cours (test)
Énoncé. Triangle A, B, C, initiateur A. Quels arbres peut-on obtenir, combien de messages ?
Trois arbres possibles selon les vitesses des liens ; 2E = 6 messages.
EN The tree depends on which probe arrives first; every edge carries two messages, so 2E in total.
cours
Énoncé. Réseau a, b, c, f avec les liens f-a, f-c, a-b, a-c. Appliquer Tel avec tous candidats.
f est élu ; arbre f→a, f→c, a→b, lien a-c hors arbre.
EN Only the wave of the highest id completes, so its initiator is elected.
cours
Énoncé. Graphe P0..P4 avec liens P0-P1 (1), P1-P2 (2), P0-P4 (5), P1-P3 (3), P3-P4 (6), P2-P4 (1). Évolution de la table de P0.
| moment | vers P1 | vers P2 | vers P3 | vers P4 |
|---|---|---|---|---|
| départ | 1 | ? | ? | 5 |
| ronde 1 | 1 | 3 (via P1) | 4 (via P1) | 5 |
| ronde 2 | 1 | 3 | 4 | 4 (via P1) : 1+3 < 5 |
| ronde 3 | 1 | 3 | 4 | 4 : stable |
P0 final : P1 1, P2 3 via P1, P3 4 via P1, P4 4 via P1.
EN Each node improves its estimate whenever a neighbour offers a shorter path, until no table changes.
cours (tests)
Énoncé. Test 1 Q1-Q2 ; exo 4 capteurs (température max) ; exo 5 numéros uniques pour processus anonymes.
started dans les deux gardes ; diffusion du max avec rediffusion si plus grand ; tirage de bits par rondes.
Meilleur : ids croissants dans le sens du tour, 2n-1 messages d'élection (+ n de proclamation). Pire : ids décroissants dans le sens du tour, le papier i fait i sauts, n(n+1)/2.
EN Best case: ids increasing along the ring, 2n-1 election messages. Worst case: decreasing, n(n+1)/2.
À chaque ronde au moins la moitié des actifs est éliminée (de deux actifs voisins, le plus petit tombe) : au plus log N rondes de 2N messages, donc 2N log N garanti.
EN At least half of the active processes are eliminated each round, so there are at most log N rounds of 2N messages.
2E : chaque arête de l'arbre porte un probe et un echo, chaque arête hors arbre porte deux probes croisés.
EN Every edge carries exactly two messages, so the total is 2E.
Un processus de plus grand id redémarré (ou lent, timeout mal calibré) se proclame leader même si un autre vient d'être élu : deux leaders, vue incohérente.
EN A recovering process with the highest id proclaims itself leader, so two leaders may coexist.
Chapitre 2
Cristian : preuve de la précision (2012), délai d chez le serveur (2017) ; horloges vectorielles : le max des vecteurs d'événements concurrents est la diagonale (2013-14) ; estampilles et ordre de livraison ; Chandy-Lamport sans FIFO. Le chapitre complet en ligne
Sans horloge globale, on ne peut pas dire « a a eu lieu avant b » au sens du temps réel. On définit à la place a → b : une information a pu voyager de a à b (même processus dans l'ordre, envoi puis réception, transitivité). Deux événements non reliés sont concurrents. Ce n'est pas un ordre total : plusieurs « passés » sont compatibles avec ce qu'on observe.
L'horloge de Lamport est un entier qui respecte la causalité dans un sens : a → b implique L(a) < L(b). L'inverse est faux : deux événements concurrents ont des valeurs comparables quand même. Elle sert à fabriquer un ordre total (L, id) cohérent avec la causalité.
L'horloge vectorielle a une case par processus. Elle caractérise exactement la causalité : V(a) < V(b) si et seulement si a → b, et deux vecteurs incomparables signifient concurrence. Prix : N entiers par message.
Une coupe choisit un point par processus. Elle est cohérente si aucun message n'est reçu dans le passé de la coupe et envoyé dans son futur (orphelin). Les messages envoyés avant et reçus après sont simplement en transit. Chandy-Lamport prend une telle photo en ligne : le marqueur, envoyé sur chaque canal sortant juste après la photo locale, sépare les messages « avant » des messages « après ». Il faut des canaux FIFO pour que cette séparation tienne.
Cristian : un client interroge un serveur de temps et corrige avec la moitié du RTT ; l'incertitude vient de l'asymétrie inconnue des deux trajets. Berkeley : pas de serveur de référence, un maître fait la moyenne des horloges (en écartant les valeurs aberrantes) et renvoie à chacun sa correction.
e1 → e2 (happened-before) : une information a pu aller de e1 à e2. Trois règles : même processus et avant ; envoi puis réception ; transitivité.
Ni e1 → e2 ni e2 → e1 : e1 || e2 (concurrents). Tester : chercher un chemin. || n'est pas transitif.
EN e1 happened before e2 if a piece of information could have travelled from e1 to e2.
+1 avant chaque événement ; l'envoi porte L ; réception de l : L := max(L, l) + 1.
a → b ⇒ L(a) < L(b), pas la réciproque. Ordre total (L, id). L(e) = plus longue chaîne causale qui mène à e.
EN Lamport clocks respect causality, but L(a) < L(b) does not imply a happened before b.
V[i]++ avant chaque événement ; l'envoi porte V ; réception : max case par case puis V[i]++. Défaut : N cases.
V1 < V2 ⇔ e1 → e2. Un < et un > : e1 || e2. Deux événements concurrents : le max des vecteurs d'un trio d'événements 2 à 2 concurrents donne la diagonale (Vt1[1], ..., Vtn[n]).
EN V(a) < V(b) holds if and only if a happened before b; two incomparable vectors mean concurrency.
Coupe cohérente ⇔ pas d'orphelin (envoi dans le futur, réception dans le passé) ⇔ VCut[k] = Vk[k]. S = R ne suffit pas (un envoi non vu et une réception non vue se compensent).
Effacer une réception = message en transit (sans danger). Effacer un envoi déjà reçu = orphelin.
≠ horloges de Lamport : pas d'horloge, but = photo de l'état global (état de chaque processus + messages en transit). FIFO, pas de perte, pas de panne, tout processus peut lancer.
Initiateur : photo + marqueur sur chaque canal sortant + écoute tous les entrants. 1er marqueur reçu sur c : photo + c = vide + marqueur sur chaque sortant + écoute les autres. Message normal sur canal écouté : noté (en transit). Marqueur suivant sur c : état(c) = messages notés depuis la photo. Fin : marqueur reçu sur tous les entrants.
Banque : P=70, Q=90, R=100, 10 en route P→Q et 30 Q→P, R lance : photos R=100, Q=90, P=70, canaux P→Q {10}, Q→P {30}, total 300. Naïf (slide 17) : B photo puis envoie M à C, C reçoit puis photo : 310 au lieu de 300.
EN The marker separates, on each channel, messages sent before the sender's snapshot from those sent after; FIFO guarantees it.
P et Q à 100 (total 200), canal P→Q non FIFO. Cas 1 : P envoie m (10), photo P=90, marqueur ; le marqueur double m : Q photo 100, canal vide, m arrive après, noté nulle part : 190 (perte). Cas 2 : P photo 100, marqueur, puis m' (10) ; m' double le marqueur : Q=110 puis photo : réception sans envoi, orphelin, 210.
Exo 6 (anneau P⇄Q, un jeton m, état = nombre de réceptions) : Sp=101, Sq=102, P→Q vide ; Q→P vide si Q garde m, {m} si Q l'a renvoyé avant le marqueur. Un seul jeton, cohérent.
EN Without FIFO an application message can overtake the marker, so it is recorded nowhere or received without its send.
Cristian (synchro externe, serveur S) : P demande à t0, S répond t, P reçoit à t1. RTT = t1 - t0. P règle à t + RTT/2 ; répéter, garder le RTT minimal. S a lu t dans [t0 + min, t1 - min] : précision ±(RTT/2 - min) (min inconnu : ±RTT/2). Exemple : RTT 20 ms, min 4 ms : ±6 ms.
Berkeley (synchro interne) : le maître interroge tous, corrige par RTT/2, fait la moyenne en ignorant les écarts > δ, renvoie à chacun son ajustement. Exemple : maître 3:00, A 3:25, B 2:50 : moyenne 3:05, ajustements +5, -20, +15.
EN Accuracy is ±(RTT/2 - min), since the server's reading lies between t0 + min and t1 - min.
Exo 3 (2 processus, ressource exclusive, plus petite estampille gagne, égalité : id) : pour redemander il faut avoir libéré donc échangé des messages, l'écart entre requêtes ≤ 1. Compter modulo 3 : x plus ancien que y ⇔ y = x + 1 (mod 3). Modulo 2 insuffisant. Règle : 2 × écart + 1 valeurs.
Exo 4 (N > 2, FIFO, envois infinis, traiter par estampille croissante) : last[k] = dernière estampille reçue de k. Traiter M (de j) ssi pour tout k ≠ j, last[k] > ts(M) ; sinon le garder. Un envoi de données à un processus : message nul de même estampille à tous les autres. Vivacité grâce à « envois infinis ».
EN A process delivers M only once it has received from every other process a message, possibly null, with a larger timestamp.
Horloge de Lamport
événement interne : L := L + 1 envoi : L := L + 1 ; send ⟨m, L⟩ réception ⟨m, l⟩ : L := max(L, l) + 1
Horloge vectorielle (Pi)
tout événement : V[i] := V[i] + 1 envoi : send ⟨m, V⟩ réception ⟨m, W⟩ : pour tout k : V[k] := max(V[k], W[k]) ; V[i] := V[i] + 1
Chandy-Lamport (Pi)
Ip: { initiateur } photo ; marqueur sur chaque sortant ; écouter tous les entrants Rp: { ⟨marqueur⟩ sur c, premier } photo ; état(c) := vide ; marqueur sur chaque sortant ; écouter les autres Rp: { ⟨marqueur⟩ sur c, suivant } état(c) := messages notés depuis la photo ; fin si tous les entrants clos Rp: { message normal sur c écouté } noter (en transit)
TD2, valeurs vérifiées
Énoncé. Trois processus, huit messages (a1→a2, a2→b1, a3→b2, b1→b3, c1→c2, c2→c3, c2→d1, c3→d2). Donner les horloges, puis dire quelles coupes sont cohérentes.
Une coupe est cohérente ssi VCut[k] = Vk[k] pour tout k, c'est-à-dire sans orphelin ; les messages en transit sont permis.
EN The cut is consistent because no message is received before the cut and sent after it.
TD2, valeurs vérifiées
Énoncé. Diagramme P, Q, R, messages p1→q3, p2→q6, q2→p5, q4→p3, q5→r2, q2→r1, q7→r5, r3→q9, q10→r6.
Un message ajouté est possible s'il ne crée pas de cycle causal.
EN Adding the message is impossible because it would create a causal cycle.
cours et TD2
Énoncé. P = 70, Q = 90, R = 100, 10 en route de P vers Q et 30 de Q vers P, R lance. Puis contre-exemple sans FIFO (exo 5) et anneau avec un jeton (exo 6).
Le marqueur sépare sur chaque canal les messages envoyés avant la photo de ceux envoyés après ; FIFO le garantit.
EN Without FIFO a message can overtake the marker, so the recorded state is inconsistent.
annales
Énoncé. Prouver la précision ±(RTT/2 - min). Puis : liens symétriques, serveur qui attend d avant de répondre.
Précision ±(RTT/2 - min) ; avec liens symétriques la déviation est nulle ; un délai d chez le serveur décale P de d/2.
EN The error is bounded by RTT/2 - min because the server read its clock within [t0 + min, t1 - min].
TD2
Énoncé. Berkeley : maître 3:00, A 3:25, B 2:50. Exo 3 : horloges bornées. Exo 4 : livraison par estampille.
Moyenne puis ajustement par processus ; compteur modulo 3 ; livraison quand toutes les dernières estampilles reçues dépassent celle du message.
S a lu t après t0 + min (temps minimal d'aller) et avant t1 - min (temps minimal de retour). P règle à t + RTT/2 ; l'erreur est donc bornée par (RTT - 2·min)/2 = RTT/2 - min dans les deux sens.
EN The server read the clock between t0 + min and t1 - min, so setting the clock to t + RTT/2 gives an error of at most RTT/2 - min.
Deux processus à 100 (total 200). Le marqueur double m : Q photographie 100, le canal est enregistré vide, m arrive après et n'est compté nulle part, total 190. Ou m' double le marqueur : réception sans envoi, 210.
EN Without FIFO an application message can overtake the marker, so the recorded cut is inconsistent.
Non : a → b implique L(a) < L(b) mais pas la réciproque (contre-exemple L(a3)=3 < L(b4)=5 avec a3 || b4). Les horloges vectorielles donnent l'équivalence.
EN No: L(a) < L(b) does not imply a happened before b. Vector clocks characterise causality exactly.
Quand aucun message n'a son envoi dans le futur et sa réception dans le passé de la coupe (pas d'orphelin). Avec les vecteurs : VCut[k] = Vk[k] pour tout k. Les messages en transit sont autorisés.
EN A cut is consistent if no message is received before the cut and sent after it.
Chapitre 3
À chaque examen : CIC (2011, 2012-13, 2013-14), checkpoint avant / après chaque envoi avec graphe de dépendances et ligne de recovery (2012, 2022), domino. Le chapitre complet en ligne
Checkpointing : on sauvegarde de temps en temps l'état ; après une panne, (presque) tous les processus reviennent à une coupe cohérente puis repartent. Message logging : on journalise les événements non déterministes (les réceptions) ; seul le fautif revient en arrière et rejoue la même exécution grâce au journal.
Si chacun checkpointe quand il veut, la dernière photo de chaque processus n'est pas forcément cohérente. En reculant un processus on efface un envoi que l'autre a déjà reçu : c'est un orphelin, l'autre doit reculer, ce qui peut créer un nouvel orphelin, et ainsi de suite jusqu'au début : l'effet domino. Effacer une réception est sans danger (le message devient en transit).
Le checkpointing coordonné évite le domino en forçant une coupe cohérente (deux phases bloquantes, ou piggyback de la demande sans bloquer). Le CIC (communication-induced) le fait sans message de contrôle : chaque message porte l'index du checkpoint de l'émetteur ; si l'index reçu dépasse l'index courant, on prend un checkpoint forcé avant de traiter le message. Tous les checkpoints de même index forment alors une coupe cohérente.
On suppose l'exécution « piecewise deterministic » : entre deux événements non déterministes, tout se rejoue pareil. Pessimiste : on journalise chaque réception avant de l'exécuter, donc jamais d'orphelin mais un coût synchrone. Optimiste : on journalise par lots, on suit les dépendances, et une panne peut provoquer des retours en cascade.
Du moins grave au plus grave : crash (s'arrête, correct avant : fail-stop) < omission (envoi / réception) < timing (hors délai) < response (valeur / transition d'état) < arbitraire = byzantin.
k-fault tolerant : survit à k composants en panne (crash : k+1 copies ; byzantin : 2k+1). Stable storage : 1 panne : RAM d'un autre ; transitoires : disque local ; définitives : hors machine (FS répliqué).
Recoverable state : assez d'information pour rejouer jusqu'à une coupe cohérente. Checkpointing : (presque) tous reviennent à une coupe cohérente. Message logging : seul le fautif revient et rejoue à l'identique avec le journal. En transit : à sauvegarder si canal fiable ; orphelin : réémis donc reçu 2 fois.
Chacun checkpointe quand il veut ; après panne : collecter les dépendances, calculer la recovery line ; garder tous les checkpoints.
Effet domino : reculer efface un envoi déjà reçu, orphelin, l'autre recule, etc. (effacer une réception = en transit, sans danger).
Graphe de Bhargava-Lian : arête c(i,x) → c(j,y) si m envoyé dans l'intervalle I(i,x) et reçu dans I(j,y), plus arêtes locales. 1) marquer les nœuds volatils des fautifs, 2) atteignabilité, 3) recovery line = dernier nœud non marqué de chaque processus. Slide 22 : ABC impossible car m5 envoyé après A, reçu avant B : domino jusqu'au début.
EN Rolling back a process may undo a send already received by another, creating an orphan message and forcing a cascading rollback: the domino effect.
Bloquant (2 phases) : l'initiateur checkpoint et envoie request ; chacun : stop, flush, checkpoint provisoire, ack ; tous les acks : commit, checkpoint permanent (garder l'ancien jusqu'au commit). Cohérent, pas de domino, mais latence. Sans blocage : orphelin.
Non bloquant : FIFO, la request arrive avant tout autre message ; ou piggyback de la request sur le premier message. FIFO nécessaire si seul le 1er message porte la request ; inutile si tous portent le numéro (c'est le CIC).
Index piggybacké ; checkpoint local (index++) ; checkpoint forcé : message reçu d'index i > index courant : checkpoint forcé d'index i avant de traiter (saut possible 0 → 2). Ligne de recovery k = les checkpoints d'index k (sinon le premier d'index ≥ k) : jamais d'orphelin. i < index : message en transit à sauvegarder (receiver-based).
Exam 2011 : checkpoint local : current := current + 1 ; send (local_state, j, current) à la mémoire stable. N de recovery = min sur i du dernier index stocké par i. Index reçu = current - 2 : pas de forcé, mais messages en transit pour N+1..current : pas optimal. Extension : si N < current, pour k = N+1..current : send (M, j, k) à la mémoire stable ; recovery N : renvoyer (local_state, i, N) puis les messages (M, i, N).
CIC contre non coordonné : pas de domino, ligne = même index, 0 message de contrôle.
EN On receiving a message with a larger index, the process takes a forced checkpoint with that index before delivering it.
Checkpoint avant chaque envoi : l'envoi n'est pas dans le checkpoint, orphelins, domino possible. Checkpoint après chaque envoi : jamais d'orphelin, pas de domino ; ligne = dernier checkpoint des fautifs + état courant des autres ; GC : garder le dernier seul. Coût : un checkpoint par envoi, plus lourd que le CIC.
2022 : checkpoint à la réception puis renvoi = checkpoint avant envoi : domino ; correctif : renvoyer puis checkpointer. Exam 2012 recalculé : avant, ligne P0 655, P1 475, P2 160 (initial), P3 387 (cascade m3, m7, m2, m4, m5) ; après, P1 1046, P3 1026, P0 et P2 à l'état courant.
EN Checkpointing after each send guarantees that rolling back never undoes a send, so no orphan message can appear.
PWD (piecewise deterministic) : événements non déterministes (réceptions) identifiables, déterminant stockable, rejeu identique. Processus orphelin : dépend d'un événement ND non journalisé. Condition : pour tout e, ¬Stable(e) ⇒ Depend(e) ⊆ Log(e). Slide 38 : Depend(e) = {P0, P3, P2}, Depend(e') = {P1, P2, P0}. PWD indispensable au logging, inutile au checkpointing.
Pessimiste : log AVANT d'exécuter, jamais d'orphelin, seul le fautif repart, simple ; log synchrone coûteux (NVRAM ; si pertes tolérées : log avant l'envoi suivant). Optimiste : flush de temps en temps, suivi causal, rollbacks en cascade possibles. Checkpointing : petit ou moyen, surcoût faible ; logging : grande échelle, surcoût moyen à élevé.
EN Pessimistic logging writes every non-deterministic event to stable storage before executing it, so no orphan process can exist.
CIC de Briatico (Pi)
checkpoint local : index := index + 1 ; save(state, index) envoi de m : send ⟨m, index⟩ réception ⟨m, i⟩ : si i > index alors index := i ; checkpoint forcé d'index i // avant de traiter m si i < index alors sauvegarder m // en transit traiter m recovery : N := min_i (dernier index stocké par i) ; tous reviennent au checkpoint d'index N
Checkpointing coordonné bloquant
initiateur : checkpoint provisoire ; send ⟨request⟩ à tous ; attendre tous les ⟨ack⟩ ; send ⟨commit⟩ Pi, ⟨request⟩ : stop ; flush ; checkpoint provisoire ; send ⟨ack⟩ Pi, ⟨commit⟩ : checkpoint permanent ; supprimer l'ancien ; reprendre
Recovery line (Bhargava-Lian)
1. marquer les nœuds volatils des processus fautifs 2. tout nœud atteignable depuis un nœud marqué est marqué 3. recovery line := dernier nœud non marqué de chaque processus
cours, vérifié sur le site
Énoncé. Trois processus avec checkpoints A, B, C, P2 tombe après C. Peut-on revenir à la coupe {A, B, C} ?
La recovery line est l'état initial : domino, car m5 est envoyé après A et reçu avant B.
EN Rolling back undoes the send of m5, so the receiver must also roll back, up to the initial state.
annale 2011
Énoncé. Pseudo-code CIC donné : checkpoint local (current := current + 1, send (local_state, j, current) en mémoire stable). Calculer le N de recovery ; que se passe-t-il si l'index reçu vaut current - 2 ?
N = min des derniers index stockés ; il faut aussi stocker les messages en transit (receiver-based).
EN The recovery index is the minimum of the last stored indices; in-transit messages must be logged too.
annales 2012 et 2022, valeurs recalculées
Énoncé. Quatre processus, messages m1 à m10, checkpoint avant chaque envoi, puis après chaque envoi : graphe de dépendances, recovery line, domino ? 2022 : P1 et P2 se renvoient m, checkpoint à la réception avant de renvoyer.
Checkpoint après chaque envoi : pas d'orphelin, pas de domino, mais un checkpoint par envoi.
EN Checkpointing after each send guarantees that rolling back never undoes a send.
cours
Énoncé. Condition de non orphelin et exemple du slide 38.
Pessimiste : log avant exécution, un seul processus recule ; optimiste : suivi causal.
EN Pessimistic logging records each event before it executes, so no process can become an orphan.
N = min des derniers index stockés. Si l'index reçu vaut current - 2, aucun checkpoint forcé mais des messages sont en transit pour N+1..current : pas optimal. Extension : stocker (M, j, k) pour k = N+1..current et les renvoyer au recovery.
EN The recovery index is the minimum over processes of their last stored index; in-transit messages must also be logged.
Avant : l'envoi n'est pas inclus, orphelins et domino possibles. Après : jamais d'orphelin ni de domino, mais un checkpoint par envoi. Le CIC fait mieux avec peu de checkpoints forcés.
EN Checkpointing after each send never creates orphans, but it costs one checkpoint per send.
Le renvoi est après le checkpoint donc l'envoi n'y figure pas : orphelin, dépendances en chaîne, domino jusqu'au début. Correctif : renvoyer m puis checkpointer.
EN Send first, then take the checkpoint, so the checkpoint includes the send.
Chaque réception est journalisée avant exécution : aucun événement non déterministe non journalisé ne peut influencer un autre processus. Seul le fautif revient et rejoue.
EN Every non-deterministic event is logged before execution, so no process can depend on a lost event.
Chapitre 4
Deux propriétés d'ordre causal safety / liveness (2011, 2012-13), total order par séquenceur sans FIFO et panne du séquenceur (2012-13, 2013-14), CBCAST à vecteurs (2017-18, 2019), liens perfect à partir de fair-loss (2019). Le chapitre complet en ligne
On part de liens perdants (fair-loss), on les rend têtus (stubborn), puis parfaits (perfect, sans perte ni duplication). Au-dessus : BEB (le meilleur effort : un correct envoie à tous les corrects), RB (tout ou rien parmi les corrects, grâce à un détecteur P qui déclenche le relais), URB (tout ou rien même pour les processus fautifs qui ont livré). Chaque étage se construit sur le précédent.
FIFO : mes messages sont livrés dans l'ordre où je les ai envoyés. Causal : si m1 a causé m2, tous livrent m1 avant m2 (se réalise avec des vecteurs : CBCAST). Total : tous livrent dans le même ordre, mais pas forcément causal (se réalise avec un séquenceur ou des horloges de Lamport).
m1 = une question, m2 = la réponse. Règle (a) : si on livre m1 et m2, m1 d'abord (safety, rien de mauvais n'arrive). Règle (b) : livrer m2 impose que m1 soit déjà livré (plus forte, c'est la spécification du broadcast causal). Livrer la réponse sans la question respecte (a) mais viole (b).
Safety = rien de mauvais n'arrive (violation visible à un instant t). Liveness = quelque chose de bon finit par arriver.
Causal (exam) : m1 = question, m2 = réponse (m1 → m2). (a) si on livre m1 ET m2, m1 d'abord : safety. (b) si on livre m2, m1 est déjà livré : plus forte, c'est la spec CO (CB slide 49). Livrer la réponse seule : (a) respectée, (b) violée.
m1 → m2 vient de : C1 FIFO, C2 réseau (livre m1 puis diffuse m2), C3 transitivité.
EN Safety: nothing bad ever happens. Liveness: something good eventually happens.
BEB : bebBroadcast = pp2pSend à tous. BEB1 (pi ET pj corrects : livré) liveness, BEB2 pas de duplication (safety), BEB3 pas de création (safety).
RB = BEB + tout ou rien. Détecteur P : PFD1 strong completeness (liveness), PFD2 strong accuracy (safety). RB4 agreement : livré par un correct ⇒ livré par tous les corrects. Lazy (slide 68) : from[pi] ; crash(pi) : rediffuser from[pi] ; pi déjà suspecté : relais immédiat. EXO 2 : P2 relaie sur crash P0, P3 sur crash P1, P4 livre ; P2, P3, P4 livrent une seule fois.
URB : si un processus (même fautif) livre m ⇒ tous les corrects livrent. All-Ack : relais immédiat, livrer quand correct ⊆ ack_m (N² messages). Majority-Ack sans détecteur si f < N/2.
EN Reliable broadcast: if a correct process delivers m, then every correct process delivers m.
VC[i] = messages diffusés par pi, VC[j] = messages de pj livrés. Envoyer VC puis VC[self]++. Livrer si VC_m ≤ VC puis VC[émetteur]++ (pas de max). VC ne change qu'à la livraison.
EXO 3 : m1 000, m2 100, m3 110, m5 110, m4 210 ; P2 livre m1 m2 m5 m3 m4 ; crash de P1 pendant m3 : sans RB, m4 bloqué sur P2 ; avec RB, P3 relaie m1 et m3.
EN A message is delivered once its vector is less than or equal to the local one; the vector is updated at delivery only.
Même ordre partout, pas forcément l'ordre d'envoi. Séquenceur : r := 0 ; order(i, S) : attendre m ET S = r ; S numérote à l'arrivée. Q1 sans FIFO : m2 double m1, tous livrent m2 puis m1 (pas causal). Q2 FIFO ⇒ causal. Q4 : 2N messages, 2 étapes. Q5 : m envoyé seulement à S : N+1 messages, FIFO pi → S seulement.
Panne de S : élection (détecteur + élection de leader), collecte des orders reçus, reprise à max + 1, orders diffusés en URB.
Mysterious broadcast (EXO 4) : Lamport + FIFO, livrer ts ≤ min_q LC[q] : ordre total causal ; liveness : chacun diffuse régulièrement ; sans FIFO : plus aucun ordre.
EN The sequencer assigns a sequence number on arrival; receivers deliver in sequence-number order.
Reliable Broadcast lazy (slide 68)
Init: delivered := ∅ ; correct := Π ; from[pi] := ∅ pour tout pi rbBroadcast(m): bebBroadcast(⟨Data, self, m⟩) bebDeliver(pj, ⟨Data, s, m⟩): si m ∉ delivered : delivered ∪= {m} ; rbDeliver(s, m) ; from[s] ∪= {m} si s ∉ correct : bebBroadcast(⟨Data, s, m⟩) crash(pi): correct \= {pi} ; pour tout m ∈ from[pi] : bebBroadcast(⟨Data, pi, m⟩)
CBCAST (pi)
cbcast(m): envoyer ⟨m, VC⟩ à tous ; VC[i] := VC[i] + 1 réception ⟨m, VCm⟩ de pj: attendre VCm ≤ VC (composante par composante) livrer m ; VC[j] := VC[j] + 1 // pas de max
Total order par séquenceur
to-broadcast(m): envoyer m à tous et à S S, réception de m: envoyer ⟨order, id(m), seq⟩ à tous ; seq := seq + 1 pi: r := 0 ; livrer m dès que m reçu et ⟨order, id(m), r⟩ reçu ; r := r + 1
annales
Énoncé. m1 est une question, m2 la réponse. Les propriétés (a) et (b) sont-elles équivalentes ? Safety ou liveness ?
(b) implique (a) ; elles diffèrent quand m1 n'est jamais livré. Les deux sont des safety.
EN Property (b) is stronger: it forbids delivering m2 unless m1 has already been delivered.
corrigé officiel concordant
Énoncé. Cinq processus, P0 puis P1 tombent pendant leur diffusion. Qui relaie, qui livre, combien de fois ?
P2 relaie sur crash(P0), P3 sur crash(P1), P4 livre ; P2, P3, P4 livrent une fois.
EN When the sender is suspected, a correct process that delivered the message relays it to everybody.
corrigé officiel partie causale
Énoncé. Messages m1 (000), m2 (100), m3 (110), m5 (110), m4 (210) ; P2 livre m1 m2 m5 m3 m4. Que se passe-t-il si P1 tombe pendant m3 ?
CBCAST seul peut bloquer sur un message perdu ; un reliable broadcast dessous garantit l'arrivée.
EN Without reliable broadcast a lost message blocks every message that causally depends on it.
annales
Énoncé. Séquenceur S numérote les messages ; sans FIFO, avec FIFO ; coût ; panne de S.
FIFO source-séquenceur donne le causal ; coût 2N messages ; reprise à max + 1 après élection.
EN The sequencer assigns increasing numbers on arrival; all processes deliver in that numeric order.
cours
Énoncé. Livrer quand ts ≤ min_q LC[q] : quel ordre ? Que faut-il supposer ?
Ordre total causal par estampille, sous FIFO et diffusions régulières.
EN Messages are delivered in timestamp order once no smaller timestamp can still arrive.
(a) : si on livre m1 et m2, m1 d'abord (safety). (b) : si on livre m2, alors m1 déjà livré (plus forte, c'est CO). (b) implique (a) ; (a) n'interdit pas de livrer la réponse seule.
EN The second property is stronger: it forbids delivering the answer without the question.
m2 envoyé après m1 par la même source mais m2 double m1 vers S : S numérote m2 puis m1, tous livrent m2 m1. L'ordre total est respecté mais pas l'ordre causal. Avec FIFO source → S, l'ordre total respecte la causalité.
EN If m2 overtakes m1 on the way to the sequencer, everyone delivers m2 then m1: total order without causal order.
Détecter (détecteur de pannes), élire un nouveau séquenceur (leader election), collecter les order déjà reçus, reprendre la numérotation à max + 1, diffuser les order en URB pour ne pas en perdre.
EN Elect a new sequencer, collect the orders already received, resume at the maximum plus one, and broadcast orders uniformly.
Quand VC_m ≤ VC : toutes les diffusions dont m dépend ont déjà été livrées localement, et c'est le suivant attendu de l'émetteur. Puis VC[émetteur]++ (pas de max).
EN Deliver once every message that causally precedes m has already been delivered locally.
Chapitre 5
Consensus uniforme contre régulier (2011, 2012, 2019), flooding en N-1 étapes, détecteurs ◇P et élection de leader (2011, 2012), commit de transaction (2019). Le chapitre complet en ligne
Chaque processus propose une valeur, tous doivent décider la même, parmi celles proposées, exactement une fois, et tout processus correct doit finir par décider. FLP : en asynchrone pur, même avec un seul crash possible, aucun algorithme déterministe ne garantit à la fois l'accord et la terminaison, car on ne peut pas distinguer un processus lent d'un processus mort.
Un détecteur dit à chaque processus qui il soupçonne. Completeness : les morts sont finalement soupçonnés. Accuracy : les vivants ne le sont pas (forte : jamais ; finale : à partir d'un moment). P : synchrone, parfait. ◇P : partiellement synchrone, il se trompe un temps puis se stabilise, en augmentant son délai à chaque erreur. ◇S est le plus faible qui permet le consensus.
Hiérarchique : les processus sont classés par rang ; à son tour, le chef décide sa valeur et la diffuse, les autres l'adoptent ou suspectent le chef. Il est correct mais non uniforme : le chef décide avant que personne n'ait reçu, donc il peut décider puis crasher sans que les autres le suivent. Le consensus uniforme exige l'accord de tous, y compris les fautifs ; il faut des acquittements avant de décider.
Paxos suppose seulement qu'un leader existe à terme (Ω) ; avec un quorum de majorité il reste sûr même si plusieurs processus se croient leaders. CAP : si le réseau se partitionne, on choisit la cohérence ou la disponibilité, pas les deux. La cohérence à terme (eventual consistency) n'est pas la cohérence de CAP.
4 propriétés : terminaison (liveness : tout correct décide), accord, validité (la valeur décidée a été proposée), intégrité (une seule décision). Uniforme : l'accord vaut pour tous les processus, y compris ceux qui crashent après avoir décidé.
FLP : consensus impossible en asynchrone pur, même avec 1 crash (mort ≠ lent). Sorties : détecteur de pannes, borner f (quorum f+1 parmi 2f+1), probabiliste.
EN FLP: no deterministic algorithm solves consensus in an asynchronous system if even one process may crash.
Completeness (les morts sont suspectés) forte / faible ; accuracy (les vivants ne sont pas suspectés) forte / faible ; ◇ = à terme. On ne garde que la completeness forte (boosting).
P : synchrone, délai max δ connu ; strong completeness (liveness) + strong accuracy (safety). ◇P : partiellement synchrone ; sur restore, T augmente (T += Δ) ; strong completeness + eventual strong accuracy. Impossible en asynchrone pur ; « pas plus d'un jour » = synchrone formellement, inutile en pratique.
Classes P, S, ◇P, ◇S ; ◇S est le plus faible qui résout le consensus. Leader election : LE2 (leader ⇒ anciens morts) est une safety, besoin de P ; Ω : à terme le même leader, faisable avec ◇P.
EN An eventually perfect failure detector may suspect correct processes for a while, but eventually every crashed process is suspected and no correct one is.
Tour i : chef p_i décide sa proposition courante et la diffuse (beb) ; les autres l'adoptent ou suspectent le chef. Au plus n tours. Algorithme 5.2 (slides 43-44) : if (r < rank(self)) and (r > proposer) then proposal := v ; proposer := r ; delivered[r] := true (toujours). Première moitié : ne rien adopter après son propre tour. Seconde : un ancien message ne doit pas écraser un plus récent (message en retard).
Correct mais non uniforme : le chef décide avant de diffuser, il peut décider puis crasher sans que personne d'autre ne le suive. Le scénario du message en retard donne un vrai désaccord seulement avec n = 4 (le message doit arriver entre deux tours).
EN The hierarchical algorithm is correct but not uniform: the leader may decide and crash before anyone else adopts its value.
Messages PROPOSAL et ACK. Ack si rank(p) ≥ round. Adoption de proposed[round] seulement à la détection du crash du chef. Décision par rbBroadcast(DECIDED) quand detectedranks ∪ ackranks = {1..N}. Cas « décision b » : le chef 1 crashe en pleine diffusion, p3 a reçu a, p2 non, le tour 2 décide b.
Annales : « le flooding uniforme en N-1 étapes est-il correct ? » (2011), différence flooding / hiérarchique avec deux diagrammes et les complexités (2012). Dessiner les deux exécutions et compter messages et étapes.
EN Uniform consensus: no process, even one that crashes later, may decide differently from the others.
Chandra-Toueg ◇S : tours à coordinateur tournant, 4 phases : estimation + timestamp, proposition du plus grand timestamp parmi une majorité, ack ou nack, décision par RB si majorité d'ack sans nack. f < n/2 requis même avec ◇P (argument de partition). S : 3 phases, n-1 tours, tolère n-1 pannes.
Paxos : suppose seulement un leader à terme (Ω), plus complexe car pas de vue fiable ; à chaque tour, le rang le plus haut gagne (alors que le plus bas gagne en hiérarchique : même principe, échelle de temps différente). Ring Paxos : coordinateur dédié.
CAP : en cas de partition, choisir C ou A. CP = Paxos ; CA = pas de partition. Cohérence à terme ≠ C de CAP. Horloges vectorielles pour détecter la concurrence et fusionner (siblings). Dynamo (papier SOSP 2007) expose les vecteurs ; DynamoDB (service AWS) fait last-writer-wins.
EN During a network partition, a system must choose between consistency and availability.
Consensus hiérarchique 5.2 (règle clé)
// tour r = 1..N, le chef du tour r est le processus de rang r tour r : si r = rank(self) et proposal ≠ ⊥ : decide(proposal) ; bebBroadcast(⟨DECIDED, proposal⟩) bebDeliver(pr, ⟨DECIDED, v⟩): si (r < rank(self)) et (r > proposer) : proposal := v ; proposer := r delivered[r] := vrai // toujours
◇P à timeout croissant (algo 2.6)
Timeout: si (alive ∩ suspected) ≠ ∅ : period := period + Δ pour tout pi : si pi ∉ alive et pi ∉ suspected : suspected ∪= {pi} ; suspect(pi) sinon si pi ∈ alive et pi ∈ suspected : suspected \= {pi} ; restore(pi) send(pi, HEARTBEAT) alive := ∅ ; startTimer(period) Deliver HEARTBEAT de q: alive ∪= {q}
Chandra-Toueg ◇S (tour r, coordinateur c)
1. chacun envoie (estimation, timestamp) à c
2. c attend une majorité, prend l'estimation de plus grand timestamp, la diffuse
3. chacun répond ack (si reçu) ou nack (si c suspecté)
4. c reçoit une majorité d'ack sans nack : RB(decide) // f < n/2rédigé, voir le site
Énoncé. Un seul compteur period sert aux heartbeats et à la détection. Est-ce un bon algorithme ? Sans panne mais Δ mal calibré ? Délai entre deux heartbeats, délai maximal de détection ?
Le timeout croît à chaque restore, donc finit par dépasser le délai réel : eventual strong accuracy.
EN The timeout grows after every false suspicion, so eventually it exceeds the real delay.
annales, scénarios du site
Énoncé. Différence entre consensus uniforme et régulier, scénario où le hiérarchique viole l'uniformité, deux diagrammes.
Uniforme : aucun processus, même fautif, ne décide autre chose ; le hiérarchique ne l'assure pas.
EN In uniform consensus even a process that crashes later cannot have decided differently.
cours
Énoncé. Partition réseau : que choisir ? Cohérence à terme ?
Partition : cohérence ou disponibilité ; R + W > N pour des lectures fraîches.
EN During a partition the system must choose between consistency and availability.
Régulier : seuls les processus corrects s'accordent. Uniforme : aucun processus, même un qui crashe ensuite, ne décide différemment. Le hiérarchique décide avant de diffuser donc n'est pas uniforme ; l'algorithme II attend les acks de tous les non détectés avant de décider.
EN Regular consensus constrains correct processes only; uniform consensus constrains every process that decides, even faulty ones.
Impossible en asynchrone pur (FLP). « Au plus un jour » est formellement une borne donc le système est synchrone, mais une borne trop grande rend le détecteur inutile en pratique.
EN An eventually perfect detector needs partial synchrony; a one-day bound makes the system synchronous in theory but useless in practice.
Avec ◇ le détecteur peut se tromper : si f ≥ n/2, une partition peut produire deux groupes qui décident chacun une valeur différente. Il faut une majorité qui s'intersecte.
EN With an unreliable detector, a partition into two halves could decide two different values, so a majority is required.
Atomic commit = consensus où un Non impose abort. 2PC est bloquant, 3PC ne l'est pas sous ses hypothèses ; les systèmes réels répliquent chaque valeur par un consensus (Paxos).
EN Atomic commit is a consensus problem in which a single No vote forces abort.
Chapitre 6
Terminaison (Misra : combien de tours, 2017 ; jeton sur anneau pondéré, 2019 ; quand détecter, 2012-13), commit de transaction (2019). Le dernier cours est aussi couvert par le TD fait en cours (exos 1 à 3). Le chapitre complet en ligne
Première partie : une transaction touche plusieurs sites et doit être atomique. Il faut un protocole où tous valident ou tous annulent (2PC, 3PC) et, séparément, un contrôle de concurrence pour l'isolation. Seconde partie : détecter un état global (fin de l'application, interblocage) sans voir tout le système, par vagues, par jeton ou par sondes.
Une vague lit les compteurs de chaque processus à un instant différent. Si P0 est lu avant d'envoyer un message et P2 après l'avoir reçu, la vague voit une réception sans envoi ; un autre message en transit compense, et on trouve S = R alors qu'un message circule encore. Mattern évite le problème avec deux vagues qui doivent donner les mêmes totaux, la seconde commençant après la fin de la première.
Un jeton fait le tour de l'anneau et collecte l'information « je suis resté passif depuis ta dernière visite ». Dans Misra, toute réception noircit, le jeton compte les processus blancs consécutifs et il faut connaître n. Dans DFvG, seul un envoi vers un numéro plus élevé (que le jeton a déjà visité) noircit ; le jeton et les processus se colorent, et l'initiateur n'a besoin que de la couleur.
Atomicity (tout ou rien), Consistency (règles d'intégrité), Isolation (pas d'effet de bord entre transactions concurrentes : sérialisabilité), Durability. Commit protocol = atomicité répartie ; contrôle de concurrence (pessimiste : verrous, cycle puis avorter ; optimiste : graphe de précédence examiné à la fin ; MVCC) = isolation. Lecture sale : si T1 avorte, T2 doit avorter.
Propriétés d'un protocole de commit : Agreement (un seul Non impose abort), Termination (tout correct décide), Validity (tous Oui sans panne : commit). Base répliquée : chaque valeur du 2PC (PREPARE:OUI, COMMIT) est décidée par MultiPaxos entre les répliques d'un shard.
EN A commit protocol is a consensus problem in which a single No vote forces abort.
2PC : phase 1 : le coordinateur écrit Preparation, envoie Prepare, les participants écrivent Ready dans le log (mémoire stable) et votent Oui ou Non. Phase 2 : Commit si tous Oui, sinon Abort, puis Done. Bloquant : si le coordinateur tombe entre les phases, les participants prêts sont indécis, ils attendent son retour.
3PC (Skeen) : phase Prepare / Ack et état tampon p. C(s) = ensemble de concurrence : blocage si C(s) contient commit et abort. Timeouts : cohort en w : abort ; en p : commit. Coordinateur au retour : en w1 abort, en p1 commit. Hypothèses : au plus un site en panne, timeouts exacts, pas de partition. 3 aller-retours contre 2.
EN 2PC blocks if the coordinator fails between the two phases; 3PC adds a prepared state so that survivors can decide on their own.
Vague : lit les compteurs s (envoyés) et r (reçus) de chaque processus. Une vague S = R ne suffit pas (coupe incohérente). Deux vagues, la seconde après la fin de la première : si E1 = R1 = E2 = R2 alors terminé. Au plus 2 vagues après la terminaison.
Preuve : d1 < f1 < d2 < f2 ; R(t) ≤ E(t) ; R1 ≤ R(f1) ; E(d2) ≤ E2 ; R1 = E2 donne E(f1) ≤ E(d2) ≤ E2 = R1 ≤ R(f1) ≤ E(f1), donc E(f1) = R(f1).
EN If two consecutive waves report E1 = R1 = E2 = R2, no message was in transit at the end of the first wave.
Misra : anneau unidirectionnel, canaux FIFO, messages et jeton sur l'anneau. Tous blancs ; réception d'un message : noir. Pi : si noir token := 1 sinon token + 1 ; devient blanc ; transmet. P0 : blanc et token = n : terminé, sinon relance token = 1. Au plus 2 tours après la terminaison. Traiter le jeton seulement passif. Sans FIFO : faux.
DFvG : anneau 0 → n-1 → ... → 1 → 0, communications synchrones (ou bornées par D : attendre D avant le jeton). R1 : un envoi vers un numéro plus élevé noircit l'émetteur. R2 : un noir qui envoie le jeton le rend noir. R3 : il redevient blanc. Initiateur : jeton blanc et lui blanc : terminé. Un tour suffit si personne n'a noirci. Sans n ni anneau : Dijkstra-Scholten (acks, parent, déficit).
EN Misra's token counts consecutive white processes; it reaches n only if no message was received during a full round.
WFG (wait-for graph). ET (ressources) : cycle orienté. OU (communication) : un seul message débloque.
Chandy-Misra-Haas ET : sonde P(i, s, r). Reçue en k : si w[k], k ≠ i, ¬depend[k, i] : envoyer P(i, k, j) aux successeurs, depend[k, i] := vrai ; si k = i : interbloqué. L'initiateur doit être sur un circuit.
Chandy-Misra-Haas OU (probe-echo) : un non-attendant ignore ; 1ère sonde : parent + transmission ; suivantes : ack ; tous les acks : ack au parent ; initiateur avec tous les acks : interbloqué. Un cycle ne suffit pas pour le OU (un successeur libre débloque tout).
EN In the OR model a cycle is not enough: a deadlock requires that no reachable process can send a message.
2PC
Coordinateur: log(Preparation) ; send ⟨Prepare⟩ à tous ; collecter les votes tous Oui : log(Commit) ; send ⟨Commit⟩ ; sinon (un Non ou timeout) : log(Abort) ; send ⟨Abort⟩ Participant: attendre ⟨Prepare⟩ (timeout : abort) ; log(Ready Oui/Non) ; send vote ; attendre la décision ; log ; appliquer ; send ⟨Done⟩
Misra (anneau, FIFO)
Rp: { message applicatif reçu } état := noir Pi, jeton reçu (passif): si noir : token := 1 sinon token := token + 1 ; état := blanc ; transmettre P0, jeton reçu: si blanc et token = n : terminé sinon état := blanc ; transmettre token := 1
Dijkstra-Feijen-van Gasteren
R1: envoi à un numéro plus élevé (non initiateur) : état := noir R2: noir qui envoie le jeton : jeton := noir ; blanc : garde la couleur du jeton R3: noir qui envoie le jeton : état := blanc P0: jeton blanc et P0 blanc : terminé ; sinon nouveau jeton blanc
Chandy-Misra-Haas ET (processus k)
Rp: { ⟨P(i, s, k)⟩ reçue } si w[k] et k ≠ i et ¬depend[k, i] : send ⟨P(i, k, j)⟩ à chaque successeur j ; depend[k, i] := vrai si w[k] et k = i : k interbloqué
fait en cours, scénario reconstruit
Énoncé. Scénario où une seconde vague trop précoce valide une terminaison inexistante.
La seconde vague doit démarrer après la fin de la première, sinon les deux voient la même coupe incohérente.
EN The second wave must start after the first one has ended.
rédigé, schéma du prof
Énoncé. Prouver qu'au plus 2 tours suffisent après la terminaison. Faut-il traiter les messages en attente avant le jeton ? Et sans FIFO ?
Au plus deux tours ; jeton traité seulement passif ; FIFO indispensable.
EN At most two rounds after termination; the token is processed only when passive.
rédigé, schémas du prof
Énoncé. Un tour suffit quand ? Borne D ? Pourquoi échoue-t-il en asynchrone ? Routage par l'anneau ?
Un tour sans envoi en arrière ; attendre D ; pas besoin de n.
EN Waiting D guarantees that every message in transit has reached the mailbox.
rédigé
Énoncé. Détection de terminaison sans connaître n ni un ordre sur un anneau, un seul initiateur.
Dijkstra-Scholten : arbre d'engagement, acks, déficit.
EN Termination is detected when the root is passive and all its messages are acknowledged.
rédigé, esquisse non prouvée
Énoncé. Représenter le WFG et dire si Chandy-Misra-Haas s'applique.
Non applicable tel quel ; un écho à valeur booléenne (ET sur les clauses, OU sur les ressources) convient.
EN A cycle is not enough in the AND-OR model.
rédigé
Énoncé. En quel sens 3PC est-il non bloquant ?
Non bloquant = une panne n'empêche pas les autres de décider.
EN 3PC adds a prepared state so that operational sites can decide on their own.
Deux. Après la terminaison plus personne ne noircit : le premier tour démarré après blanchit tous les processus (il peut échouer), le suivant voit n blancs consécutifs.
EN At most two rounds: the first round started after termination whitens every process, the second sees n white processes.
En 2PC, l'état w a commit et abort dans son ensemble de concurrence : un survivant seul ne peut décider. 3PC ajoute l'état tampon p : en p timeout vers commit, en w vers abort, sous l'hypothèse d'au plus une panne.
EN In 2PC the waiting state may be concurrent with both commit and abort; 3PC adds a prepared state that removes this ambiguity.
Une vague isolée peut être une coupe incohérente (envoi non vu, réception non vue). Avec E1 = R1 = E2 = R2 et la seconde vague démarrée après la première, la preuve donne E(f1) = R(f1) : plus rien en transit.
EN A single wave may observe an inconsistent cut; two waves with equal totals prove that nothing was in transit.
ET : sonde qui revient à l'initiateur sur un circuit. OU : probe-echo, l'initiateur est interbloqué s'il reçoit l'ack de tous ses successeurs ; un processus libre ignore la sonde.
EN In the AND model a returning probe proves a cycle; in the OR model the initiator needs an echo from all its successors.
Un message envoyé vers un numéro plus bas laisse l'émetteur blanc ; s'il est lent il réactive un processus déjà vu passif sans noircir personne : fausse terminaison. Parade : attendre D (borne de délai) avant de traiter le jeton.
EN A slow message sent to a lower-numbered process can reactivate it behind the token without any process turning black.
Annexe
Dans quatre annales : Ricart-Agrawala avec preuves ME1 à ME3 (2011), token ring et Suzuki-Kasami modifiés pour un processus prioritaire (2012-13), double anneau à jeton (2013-14), Suzuki-Kasami avec requêtes concurrentes et jeton perdu (2017-18). Pas de page de cours en ligne : fiche tirée des slides ExclMut.pdf et 2021-DistAlgo_Exmut.pdf.
Plusieurs processus veulent entrer dans une section critique : ME1 au plus un à la fois (safety), ME2 pas d'interblocage, ME3 pas de famine (liveness). Deux familles de solutions réparties : à permission (Lamport, Ricart-Agrawala : on demande à tous) et à jeton (anneau, Suzuki-Kasami : seul le détenteur entre).
Lamport : requêtes estampillées, file locale, ack, release ; entrer quand ma requête est première et que tous ont répondu ; 3(N-1) messages, canaux FIFO. Ricart-Agrawala : pas de release, on retient la réponse tant qu'on est en CS ou qu'on a une estampille plus petite ; 2(N-1) messages, FIFO inutile.
n processus Pi, graphe complet, messages. Chacun veut périodiquement : entrer en section critique (CS), l'exécuter, en sortir. Pourquoi : l'atomicité n'existe que jusqu'à un certain niveau (compte bancaire : load, add, store entrelacés : 2 entrelacements sur 12 donnent le bon résultat).
ME1 exclusion mutuelle : au plus un processus en CS (safety). ME2 absence d'interblocage : au moins un processus éligible entre (liveness). ME3 équité (fairness) : tout processus qui veut entrer finit par y arriver, pas de famine. Mesure : attente bornée, n-fairness ; FIFO fairness quand n = 0.
EN ME1 is safety, ME2 and ME3 are liveness.
interested[tid] := vrai ; last_interested := tid ; tant que (last_interested = tid ET interested[autre]) attendre. Sortie : interested[tid] := faux. Principe : je dis que je veux entrer, je dis que je suis le dernier, j'attends tant que l'autre veut aussi et que je suis encore le dernier.
ME2 (liveness) : par l'absurde, deux bloqués verraient chacun last_interested = soi, contradiction. ME1 (safety) : 4 événements par fil (WI, WL, RI, RL) ; on suppose que les deux entrent et on trouve un cycle de happened-before. Échanger les deux écritures casse la safety (pas de cycle) ; modèles mémoire faibles : réordonnancements, barrières (fences).
EN Peterson: announce interest, give priority to the other, wait while the other is interested and you were the last to announce.
Centralisé : un coordinateur, file des requêtes, req / reply / release. Défauts : point unique de panne, contention, pas d'équité FIFO (une requête arrivée tard par un chemin lent).
Naïf : diffuser REQUEST, attendre les ACK de tous, entrer, diffuser RELEASE. Ne marche pas : deux REQUEST concurrentes se confondent. Remède : estampiller les requêtes.
Chaque processus a une file Q des requêtes connues. LA1 demander : envoyer une requête estampillée à tous, l'ajouter à sa file. LA2 à la réception : l'ajouter à Q et envoyer un ACK estampillé (mais une fois sorti de la CS). LA3 entrer quand ma requête est première dans Q (ordre chronologique) ET tous les ACK reçus. LA4 sortir : retirer ma requête de Q, envoyer release estampillé. LA5 à la réception d'un release : retirer la requête.
Observation : quand tous les ACK sont reçus, toute requête en route a une estampille plus grande, donc vue cohérente de la file. ME1 : si j et k entraient, Qj.ts < Qk.ts et Qk.ts < Qj.ts, impossible. ME2 : la chaîne d'attente est acyclique. ME3 : les nouvelles requêtes arrivent en fin de file. FIFO fairness : par FIFO, k a reçu la requête de j avant l'ack de j. Messages : 3(N-1) (requêtes + acks + releases).
EN A process enters when its request is first in its local queue and it has received an acknowledgement from everyone.
1. Diffuser une requête estampillée. 2. À la réception d'une requête : ack si je ne veux pas entrer, ou si je veux entrer mais mon estampille est plus grande (la sienne est plus petite) ; sinon (déjà en CS ou estampille plus petite) ne rien répondre et mémoriser la requête en attente. 3. Entrer quand je reçois l'ack de tous. 4. À la sortie : envoyer l'ack aux requêtes en attente avant d'en refaire une. Pas de release.
Messages : 2(N-1) (N-1 requêtes + N-1 acks). ME3 (FIFO fairness) tient même si les canaux ne sont pas FIFO. Exercice du cours : L-exclusion (jusqu'à L processus en CS), modifier R-A.
EN A process grants its permission unless it is in the critical section or it has a smaller timestamp; deferred replies are sent on exit.
Anneau à jeton : anneau logique pi → p(i+1) mod n ; seul le détenteur du jeton entre en CS ; sinon il le fait suivre. Safety et liveness garanties, pas l'ordre ; 1 message par sortie ; (N-1)-fairness ; délai entre sortie et entrée suivante entre 1 et N-1 messages.
Naïf (graphe complet) : le « roi » détient le jeton et la file des demandes ; à la sortie il envoie le jeton avec la file. Le roi change, donc chaque demande est diffusée. Exercice : deux scénarios qui échouent (une demande jamais satisfaite : famine ; un processus reçoit le jeton sans l'avoir demandé).
req[j] : numéro de séquence de la dernière requête de j (tout le monde). last[j] : numéro de la dernière visite de j en CS (dans le jeton). Jeton = (Q, last). Demande : req[j]++ puis diffuser (j, req[j]) ; attendre le jeton. Réception de (k, num) : req[k] := max(req[k], num) (écarte les requêtes périmées).
Sortie : last[j] := req[j] ; pour tout k ≠ j, k ∉ Q et req[k] = last[k] + 1 : ajouter k à Q ; si Q non vide : envoyer (queue de Q, last) à la tête de Q. Au plus N messages par entrée (N-1 requêtes + le jeton), 0 si on détient déjà le jeton.
EN The token carries the queue and the last-served numbers; a request is fresh only if req[k] = last[k] + 1.
Ricart-Agrawala (Pi)
demander : ts := horloge ; send ⟨REQUEST, ts, i⟩ à tous ; attendre ⟨ACK⟩ de tous ; entrer en CS Rp: { ⟨REQUEST, ts, j⟩ reçu } si (pas en CS et ne veut pas) ou (veut mais (ts, j) < (mon ts, i)) alors send ⟨ACK⟩ à j sinon pending := pending ∪ {j} sortie : send ⟨ACK⟩ à chaque j ∈ pending ; pending := ∅
Suzuki-Kasami (Pj)
init : pour tout i : req[i] := last[i] := 0 entrée : req[j] := req[j] + 1 ; send ⟨j, req[j]⟩ à tous ; attendre le jeton (Q, last) ; CS sortie : last[j] := req[j] ; pour tout k ≠ j : si k ∉ Q et req[k] = last[k] + 1 : Q := Q + k si Q non vide : send (queue(Q), last) à tête(Q) Rp: { ⟨k, num⟩ reçu } req[k] := max(req[k], num)
Lamport (Pi)
demander : send ⟨REQUEST, ts⟩ à tous ; Q := Q + (ts, i) Rp: { ⟨REQUEST, ts, j⟩ } Q := Q + (ts, j) ; send ⟨ACK⟩ à j entrer : (ts, i) = tête(Q) et ACK de tous reçus sortie : Q := Q - (ts, i) ; send ⟨RELEASE⟩ à tous Rp ⟨RELEASE, j⟩ : Q := Q - (·, j)
slides
Énoncé. Deux appels f() parallèles, chacun incrémente c cent fois sans protection. Valeurs finales possibles ?
c ∈ [2, 2N].
EN The final value lies between 2 and 2N.
slides
Énoncé. Que se passe-t-il si on échange les deux écritures (last_interested puis interested) ?
L'échange casse ME1 ; le cycle de happened-before n'existe plus.
EN Swapping the two writes breaks the safety proof: there is no longer a happens-before cycle.
Par l'absurde : si Pj et Pk sont en CS, chacun a reçu l'ack de l'autre pour sa propre requête. Avec TS(j) < TS(k), Pj n'a pas ack Pk tant qu'il veut entrer ou est en CS (estampille plus petite) : Pk n'aurait pas pu entrer. Contradiction.
EN If both were in the critical section, the one with the larger timestamp would have received an ack from the other, which holds back its reply.
La relation d'attente suit l'ordre des estampilles : une requête n'attend que des requêtes d'estampille plus petite (les plus grandes reçoivent un ack), donc pas de cycle ; la plus petite entre.
EN Requests only wait for smaller timestamps, so the waiting relation is acyclic.
Lamport 3(N-1) ; Ricart-Agrawala 2(N-1) ; anneau à jeton 1 message par sortie (attente jusqu'à N-1) ; Suzuki-Kasami au plus N.
EN Lamport 3(N-1), Ricart-Agrawala 2(N-1), Suzuki-Kasami at most N messages.