Plusieurs processus proposent chacun une valeur, il faut en choisir une seule, la même pour tous, alors que certains crashent et que le réseau n'a aucune borne de délai. C'est le consensus, et un théorème célèbre dit que c'est impossible sans une aide supplémentaire : le détecteur de fautes.
Le consensus exige quatre propriétés : terminaison (tout correct décide), accord (même valeur), validité (valeur proposée) et intégrité (une seule décision). FLP : impossible de garantir accord et terminaison ensemble en asynchrone pur, dès qu'un seul processus peut crasher, car on ne distingue pas un processus mort d'un processus lent. On ajoute donc un détecteur de fautes défini par sa complétude (les morts sont suspectés) et son exactitude (les vivants ne le sont pas), d'où les classes P, S, ◇P, ◇S. Avec P : consensus hiérarchique, un chef par tour (rang 1, puis 2, ...) qui impose sa valeur ; la variante uniforme demande en plus un acquittement de tous avant de décider. Avec ◇S : il faut une majorité de corrects (Chandra-Toueg). Sans détecteur : Paxos, qui préserve toujours la sûreté et ne garantit la terminaison que si un chef stable émerge.
01 · Le problème
L'histoire commence avec les bases de données réparties : une transaction touche plusieurs sites, et tous doivent faire la même chose, valider ou annuler. C'est le atomic commit, le premier besoin de consensus.
Chaque processus appelle propose(v) avec sa valeur, puis reçoit au bout d'un moment decide(v'). Exemple : trois sites A, B, C proposent « valider », « annuler », « valider ». Ils doivent tous finir avec la même réponse, et cette réponse doit être l'une de celles proposées. Sans crash et sans retard, c'est trivial (le plus petit identifiant gagne). La difficulté vient uniquement des pannes et de l'absence de borne sur les délais.
Pourquoi s'y intéresser : le consensus est la brique de la diffusion à ordre total, de la réplication d'état (tous les réplicas appliquent les mêmes opérations dans le même ordre), de l'élection de leader et, avec des fautes byzantines, de l'ajout d'un bloc dans une blockchain.
Tout processus correct finit par décider.
Deux processus corrects ne décident jamais différemment.
La valeur décidée a été proposée par quelqu'un.
Un processus décide au plus une fois.
Dans la version uniforme, l'accord porte sur tous les processus, y compris ceux qui crashent plus tard : « deux processus ne décident jamais différemment », point. Un processus qui décide puis tombe a donc le droit de laisser une trace que personne ne contredira. C'est plus fort, donc plus coûteux, et les sections 05 et 06 montrent la différence sur un cas concret.
La diffusion fiable garantit que tous les corrects livrent le même ensemble de messages. Le consensus choisit une seule valeur parmi des propositions concurrentes. On peut construire l'ordre total à partir du consensus (un consensus par position dans la séquence), et le consensus à partir d'un ordre total : les deux problèmes sont équivalents.
02 · FLP et les modèles
Résultat de Fischer, Lynch et Paterson (1985), noté FLP dans le cours : en asynchrone, avec des processus déterministes, le consensus est impossible dès qu'un seul processus peut crasher (modèle fail-silent : un processus crashé ne fait plus rien).
L'intuition tient en deux phrases. La décision peut dépendre d'un processus, et on n'a aucun moyen de savoir s'il est mort (inutile d'attendre) ou lent (il faut l'attendre). Attendre risque le blocage, ne pas attendre risque le désaccord.
Chaque message arrive en moins de δ, chaque pas de calcul prend entre deux bornes, les horloges dérivent d'une quantité bornée. Un crash se détecte par simple timeout.
Ni sur les délais, ni sur la vitesse des processus, ni sur les horloges. C'est le modèle d'Internet, et celui de FLP.
Il existe une borne sur les délais, mais on ne la connaît pas, ou elle ne tient qu'à partir d'un moment inconnu. Le cadre naturel des détecteurs ◇P et ◇S.
Crash-stop : le processus s'arrête et ne fait plus rien. Crash-recovery : il s'arrête puis redémarre. Omissions : il perd des messages. Byzantin : il peut mentir. Les détecteurs de fautes de ce chapitre visent le crash-stop ; Paxos vise aussi le crash-recovery.
Il faut affaiblir le modèle asynchrone pur. Trois routes : (1) lui ajouter un détecteur de fautes, chapitre en cours ; (2) borner le nombre de crashs f, par exemple n = 2f + 1 processus et une majorité f + 1 qui décide ; (3) accepter un consensus probabiliste, qui termine avec une probabilité 1 sans le garantir sur chaque exécution.
03 · Détecteurs de fautes
Un détecteur de fautes est un module local qui répond à la question « ce processus est-il en panne ? ». Il cache les délais derrière des événements ⟨crash | p⟩ (ou ⟨suspect | p⟩). Compromis permanent : détecter vite (risque de se tromper) ou détecter sûrement (risque de bloquer le système).
Pi interroge Pj toutes les T unités. Si pas de réponse en T, Pi marque Pj en panne. Détection au pire en 2T : T pour envoyer le ping, T pour attendre la réponse.
Pj envoie un numéro de séquence croissant toutes les T' unités. Si Pi n'a rien reçu de nouveau depuis T, il déclare Pj en panne. Un seul sens de message, moins de trafic.
Même en asynchrone il y a toujours une borne de fait entre deux machines. Le détecteur s'appuie dessus (ou sur un délai logique comme un nombre d'instructions) pour distinguer lent et mort.
Deux familles de propriétés, chacune en deux niveaux. La complétude dit que les morts sont suspectés. L'exactitude dit que les vivants ne le sont pas. Un détecteur qui suspecte tout le monde en permanence est complet mais inutile, un détecteur qui ne suspecte jamais personne est exact mais inutile : il faut les deux.
Tout processus crashé est finalement suspecté par tous les corrects.
Tout processus crashé est finalement suspecté par au moins un correct.
Aucun correct n'est jamais suspecté.
Il existe au moins un correct qui n'est jamais suspecté.
À partir d'un moment, aucun correct n'est plus suspecté (♦ = « eventually »).
À partir d'un moment, il existe un correct que personne ne suspecte plus.
| Exactitude \ Complétude | Forte | Faible |
|---|---|---|
| Forte | P (parfait) | Q |
| Faible | S (strong) | W (weak) |
| Finale forte | ◇P (eventually perfect) | ◇Q |
| Finale faible | ◇S (eventually strong) | ◇W |
Huit classes, mais on peut renforcer une complétude faible en complétude forte : chaque processus diffuse la liste de ses suspects, et chacun suspecte q tant qu'on ne l'a pas entendu parler. On ne garde donc que les quatre classes à complétude forte : P, S, ◇P, ◇S. P simule tout le reste ; S et ◇P simulent ◇S ; ◇S est le plus faible qui suffit à résoudre le consensus.
// borne δ sur le délai, période γ de heartbeat upon event <HBTimeout> : forall pi ∈ Π : send HeartBeat to pi startTimer(γ, HBTimeout) upon event receive HeartBeat from pj : alive := alive ∪ {pj} upon event <DetectTimeout> : crashed := Π \ alive forall pi ∈ crashed : trigger <crash | pi> alive := ∅ startTimer(δ + γ, DetectTimeout)
Complétude forte : un processus crashé n'envoie plus de heartbeat, donc tout le monde finit par constater son absence. Exactitude forte : deux heartbeats successifs d'un processus vivant sont séparés d'au plus γ + δ (calcul local négligé), donc personne ne le prend à tort pour mort. Tout repose sur la borne δ connue : c'est ce qui rend P impossible en asynchrone.
Ici la borne δ existe mais est inconnue. On part d'un timeout T et on le rallonge à chaque erreur : un processus suspecté qui se manifeste est « restauré » et T augmente. Après un nombre fini d'erreurs, T dépasse γ + δ et le détecteur ne se trompe plus.
suspected := ∅ ; T := T0 upon event <HBTimeout> : // comme pour P upon event receive HeartBeat from pj : alive := alive ∪ {pj} upon event <DetectTimeout> : forall pi ∈ Π : if pi ∉ alive and pi ∉ suspected then suspected := suspected ∪ {pi} trigger <suspect | pi> if pi ∈ alive and pi ∈ suspected then suspected := suspected \ {pi} trigger <restore | pi> T := T + Δ alive := ∅ ; startTimer(T, DetectTimeout)
Preuve de l'exactitude finale (question du cours : pourquoi le nombre d'itérations est fini). Chaque fausse suspicion de p par q incrémente le timeout de q d'au moins Δ > 0. Comme le système finit par être synchrone avec une borne δ, il existe un rang k tel que T0 + kΔ > γ + δ. Au-delà, q reçoit tout heartbeat de p avant son timeout, donc ne le suspecte plus. Le nombre de fausses suspicions est donc borné par ⌈(γ + δ − T0)/Δ⌉ par processus surveillé. Complétude : un crashé ne parle plus, il reste suspecté pour toujours.
« Suspecter » n'est pas « savoir ». Avec ◇P, un correct peut être suspecté pendant une durée finie mais inconnue, donc aucun algorithme ne doit supposer qu'une suspicion est vraie maintenant. C'est exactement ce qui oblige les algorithmes à base de ◇ à exiger une majorité (section 07) et ce qui rend P, lui, si confortable : chaque ⟨crash⟩ est une vérité.
04 · Consensus avec P
Premier algorithme de consensus, sur un détecteur parfait P et une diffusion best effort (beb : tout va bien sauf si l'émetteur crashe). Idée du cours : les processus passent par des tours 1 à n. Au tour i, le processus de rang i est le chef : il décide sa proposition courante et la diffuse. Les autres attendent soit la proposition du chef (ils l'adoptent), soit la détection de son crash.
Implements: Consensus (cons) Uses: BestEffortBroadcast (beb), PerfectFailureDetector (P) upon event <Init> : suspected := ∅ ; round := 1 currentProposal := nil broadcast := false ; delivered[] := false upon event <crash | pi> : suspected := suspected ∪ {pi} upon event <Propose | v> : if currentProposal = nil then currentProposal := v
upon event <bebDeliver | p_round, value> : currentProposal := value delivered[round] := true upon event delivered[round] = true or p_round ∈ suspected : round := round + 1 upon event p_round = self and broadcast = false and currentProposal ≠ nil : trigger <Decide | currentProposal> trigger <bebBroadcast | currentProposal> broadcast := true
Les scénarios de cette page sont exécutés avec la version complète de la section 06 (algorithme 5.2 du livre de Guerraoui et Rodrigues), qui n'ajoute à l'algorithme I que le test d'adoption et la variable proposer. Sans panne, ils se comportent comme l'algorithme I.
On passe le tour d'un chef mort (détecteur, complétude) ou d'un chef vivant (son message finit par arriver). Après n tours, chacun a été chef et a décidé.
Soit i le plus petit rang parmi les corrects. Au tour i, tous les corrects reçoivent vi et l'adoptent. Tous les chefs suivants rediffusent vi, donc tous les corrects décident vi.
Tout le monde doit devenir chef avant la fin : n tours et jusqu'à n(n−1) messages, même sans panne. Le défaut du cours : la convergence peut être longue.
« Comment s'assurer qu'un message n'arrive pas trop tard, dans le mauvais tour ? » Un message d'un chef déjà passé ne doit pas écraser une valeur plus récente. La réponse est dans la section 06 : on étiquette chaque message par son tour r et on n'adopte que si r > proposer, la variable qui mémorise le dernier chef adopté.
05 · Consensus uniforme avec P
Dans l'algorithme I, un chef décide avant que personne n'ait rien reçu : s'il crashe juste après, il a décidé seul. Pour l'accord uniforme, le chef doit d'abord s'assurer que tous les processus non détectés ont adopté sa valeur. Un tour comporte donc deux pas de communication : PROPOSAL du chef vers tous, puis ACK de chacun vers le chef. Seulement alors, le chef décide et le dit par reliable broadcast.
upon event <Init> : detectedranks := ∅ ; ackranks := ∅ ; round := 1 ; proposal := ⊥ ; decision := ⊥ ; proposed := [⊥]N upon event <P, Crash | p> : detectedranks := detectedranks ∪ {rank(p)} upon event <uc, Propose | v> such that proposal = ⊥ : proposal := v upon round = rank(self) ∧ proposal ≠ ⊥ ∧ decision = ⊥ : trigger <beb, Broadcast | [PROPOSAL, proposal]> upon event <beb, Deliver | p, [PROPOSAL, v]> : proposed[rank(p)] := v if rank(p) ≥ round then trigger <pl, Send | p, [ACK]> upon round ∈ detectedranks : if proposed[round] ≠ ⊥ then proposal := proposed[round] round := round + 1 upon event <pl, Deliver | q, [ACK]> : ackranks := ackranks ∪ {rank(q)} upon detectedranks ∪ ackranks = {1, ..., N} : trigger <rb, Broadcast | [DECIDED, proposal]> upon event <rb, Deliver | p, [DECIDED, v]> such that decision = ⊥ : decision := v ; trigger <uc, Decide | decision>
Ici un processus ne change de tour que quand il détecte le crash du chef (round ∈ detectedranks). Un chef vivant ne se contourne pas : on attend sa décision par RB.
On stocke la proposition reçue dans proposed[rank] et on l'acquitte, mais on ne l'adopte qu'en quittant le tour de son auteur, donc s'il crashe.
Le chef décide quand chaque rang est soit détecté mort, soit a acquitté. L'ack d'un processus vivant prouve qu'il a la valeur.
Dans le second scénario (slide 39), la valeur a du chef crashé survit : p2 et p3 l'avaient reçue, elle est dans leur proposed[1], et dès qu'ils détectent le crash ils l'adoptent. Le tour 2 rediffuse donc a, et personne n'a pu décider autre chose avant.
n PROPOSAL, n ACK, puis un reliable broadcast : un nombre de messages en O(n) et trois pas de communication, contre n tours pour l'algorithme I.
Chaque crash de chef coûte un tour de plus. Le pire cas est f + 1 tours (les f premiers chefs crashent).
Deux décisions diffusées par pi et pj (j > i) : pi a reçu l'ack de tous les non-détectés, et par l'exactitude de P pj était vivant donc l'a acquitté, donc a adopté vi. Validité et intégrité viennent des liens et du code.
06 · Version complète, retards et non-uniformité
C'est l'algorithme I écrit proprement, tel que le cours le détaille aux slides 43 et 44. Il ajoute deux variables : proposer, le rang du dernier chef dont on a adopté la valeur (0 au départ), et un tableau delivered[] pour retenir quels tours ont parlé, y compris les tours futurs.
upon event <Init> : detected := ∅ ; round := 1 ; proposal := ⊥ ; proposer := 0 for i = 1..N : delivered[i] := broadcast[i] := false upon event <crash | pi> : detected := detected ∪ {rank(pi)} upon event <cPropose | v> ∧ proposal = ⊥ : proposal := v upon round = rank(self) ∧ proposal ≠ ⊥ ∧ broadcast[round] = false : // je suis le chef broadcast[round] := true trigger <cDecide | proposal> // je décide pour de bon trigger <bebBroadcast | [DECIDED, round, proposal]> upon round ∈ detected ∨ delivered[round] = true : // tour suivant si livré ou crashé round := round + 1 upon event <bebDeliver | p, [DECIDED, r, v]> : if (r < rank(self)) ∧ (r > proposer) then // n'adopter que du "plus récent" proposal := v ; proposer := r delivered[r] := true // dans tous les cas
On n'adopte que les valeurs de rangs plus petits que le sien. Un message de rang supérieur ou égal (le sien propre compris, car la diffusion se livre à soi-même) arrive quand mon tour est déjà passé : j'ai décidé ma proposition, elle est figée. L'adopter ferait diverger ce que je dis de ce que j'ai décidé.
Parmi les rangs plus petits que le sien, on garde le plus grand reçu : c'est le tour le plus récent, qui a lui-même absorbé les tours précédents. Un message d'un rang plus petit que proposer est en retard (cas « late message ») et ne doit pas faire revenir en arrière.
Même quand le test est faux, le message compte pour faire avancer le tour : sans lui le processus attendrait le chef de ce tour pour toujours. Le test ne protège que proposal et proposer, jamais la progression.
Cet algorithme est un consensus correct (accord entre les corrects), pas uniforme : un chef décide avant d'avoir parlé à qui que ce soit. S'il crashe entre les deux, il a décidé une valeur que personne d'autre n'a vue.
Un crash n'est pas détecté au même instant par tous les processus (les slides tracent une ligne verticale par simplification). Le détecteur de p3 peut avoir annoncé le crash de p1 alors que l'un de ses messages est encore dans le réseau. Le scénario ci-dessous reprend la slide 31 : le message (1, a) arrive chez p3 après la proposition de p2.
Ici le message en retard arrive après que p3 a décidé, donc il ne gênerait rien de toute façon. Pour voir le vrai danger, il faut qu'il arrive entre deux tours, quand p4 a déjà adopté b mais attend encore le tour de p3 (qui vient de crasher). Même exécution deux fois, d'abord sans le test.
Sans le test, p4 écrase b par a et décide a alors que p2 (correct comme lui) a décidé b : l'accord est violé entre deux corrects. Avec le test, la deuxième moitié r > proposer rejette (1, a) car p4 a déjà adopté le tour 2. C'est précisément la réponse à la question « comment éviter qu'un message arrive dans le mauvais tour ».
07 · Détecteurs imparfaits : S et ◇S
Jusqu'ici le détecteur P ne se trompait jamais. Un détecteur réaliste se trompe : il suspecte un processus lent, puis se corrige. Chandra et Toueg ont montré qu'on peut tout de même décider, à condition de bien choisir quand le détecteur a le droit de mentir.
Un détecteur est jugé sur deux axes : la complétude (voit-on les morts ?) et l'exactitude (soupçonne-t-on des vivants ?). On ne garde que la complétude forte, car on sait la fabriquer à partir de la faible. Avec S (un correct jamais suspecté), le consensus marche jusqu'à n−1 pannes : on attend ce processus-là, qui est vivant. Avec ◇S (exact seulement à partir d'un moment inconnu), il faut f < n/2 : le protocole de Chandra-Toueg fait tourner un coordinateur, décide quand une majorité a accepté sa proposition sans objection, et utilise des timestamps pour qu'une valeur déjà adoptée par une majorité ne soit jamais écrasée. ◇S est le plus faible détecteur qui permette de décider.
Deux promesses se combinent. Complétude : un processus qui crashe finit par être suspecté (par tous les corrects : forte, par au moins un : faible). Exactitude : on ne suspecte pas les vivants (jamais aucun correct : forte ; au moins un correct n'est jamais suspecté : faible ; ou bien c'est vrai à partir d'un certain moment seulement : le préfixe ◇, « eventually », finale forte ou finale faible). Deux niveaux de complétude fois quatre d'exactitude : huit classes.
| exactitude forte | exactitude faible | finale forte (◇) | finale faible (◇) | |
|---|---|---|---|---|
| complétude forte | P parfait | S strong | ◇P | ◇S |
| complétude faible | Q | W | ◇Q | ◇W |
Piège de vocabulaire : « strong » et « weak » ne quantifient pas la même chose. Pour la complétude, on compte ceux qui suspectent ; pour l'exactitude, on compte ceux qui sont suspectés. Un détecteur qui suspecte tout le monde en permanence est complet, et ne sert à rien : l'exactitude est ce qui l'en empêche.
Une classe A simule B si, avec un détecteur de A, on peut écrire un petit algorithme qui sort un détecteur de B. P simule S et ◇P simule ◇S sans rien faire : un détecteur exact dans tous les cas l'est déjà « faiblement ». P simule ◇P et S simule ◇S en lisant « un jour » comme « dès maintenant ».
L'autre sens est faux, et les preuves sont des variantes du même argument : on exhibe une exécution où le détecteur simulé violerait sa propre définition. Exemple : si ◇P simulait S, on résoudrait le consensus avec f ≥ n/2 pannes, ce que la section sur la partition (plus bas) interdit.
Si seulement certains corrects voient un crash, on peut le leur faire raconter aux autres. Chacun diffuse régulièrement la liste que lui donne son détecteur faible, et chacun suspecte ce qu'on lui rapporte, jusqu'à ce que l'accusé parle lui-même.
// Algorithme 13.1 (Yale) : de la complétude faible à la forte initially suspects := ∅ forever : S := ensemble que mon détecteur faible suspecte envoyer S à tous les processus upon receiving S from q : suspects := (suspects ∪ S) \ {q} // q parle : q est vivant, on le retire
Exemple. Trois processus, p3 crashe, seul p2 le voit (le détecteur de p1 est faible). p2 envoie « {p3} » à tout le monde : p1 ajoute p3 à ses suspects, et comme p3 ne parlera plus jamais, la suspicion est définitive. Complétude forte. Si en revanche p2 avait accusé p1 à tort, tous ajouteraient p1, mais le prochain message de p1 le retire de la liste de chaque récepteur : une accusation fausse ne survit pas à un processus vivant. C'est le « \ {q} » qui préserve l'exactitude (la preuve de Yale le vérifie classe par classe). On peut donc raisonner avec les quatre classes à complétude forte : P, S, ◇P, ◇S.
◇S est le détecteur minimal. Chandra, Hadzilacos et Toueg (1996) ont montré que tout détecteur qui permet de résoudre le consensus (dans le cadre f < n/2) permet aussi de simuler ◇S : aucune information plus pauvre ne suffit. On cite ce résultat, la preuve est longue. Version « leader » : Ω, dont chaque processus sort un identifiant de processus, et qui promet qu'à partir d'un moment tous les corrects sortent le même correct pour toujours. Ω et ◇S s'équivalent en puissance, et c'est ce que Paxos suppose.
Intuition. Avec S, il existe un correct c que personne ne suspecte jamais. Donc tout le monde finit par attendre c, et ce que c a vu finit chez tous. Le reste des détecteurs peut raconter n'importe quoi : cela fait perdre des informations, pas de la cohérence. Le protocole fait trois phases : se raconter les entrées (n−1 tours de bavardage), garder seulement ce que tout le monde connaît (intersection), puis choisir selon une règle commune.
// Algorithme 13.2 (Yale) : consensus avec S, tolère f ≤ n-1 V := {⟨p, vp⟩} δ := {⟨p, vp⟩} // V : tout vu ; δ : nouveautés Phase 1 : for i := 1 to n-1 : envoyer ⟨i, δ⟩ à tous attendre ⟨i, δq⟩ de tout q que je ne suspecte pas δ := (∪q δq) \ V // seulement les nouveautés V := V ∪ (∪q δq) Phase 2 : envoyer ⟨n, V⟩ à tous attendre ⟨n, Vq⟩ de tout q que je ne suspecte pas V := V ∩ (∩q Vq) // on élague ce qui n'est pas connu de tous Phase 3 : decide une valeur de V choisie par une règle commune (ex. plus petit identifiant)
Chaque paire ⟨q, vq⟩ n'est envoyée par un processus qu'une seule fois (le tour qui suit celui où il l'apprend, c'est le rôle de δ). Une paire encore en circulation au tour n−1 a donc traversé une chaîne de n−1 processus : tous les autres. C'est la raison d'être des n−1 tours.
Combien de pannes ? Jusqu'à n−1 : il suffit que c survive. C'est la limite haute possible, puisque sans aucun correct, personne ne décide. Coût : n tours d'échanges, chacun de n messages par processus, soit environ n³ messages ; on n'utilise S que parce que la tolérance aux pannes est maximale.
La preuve s'appuie sur « c n'est jamais suspecté, donc tout le monde l'attend ». Avec ◇S, c peut être suspecté pendant tout le début de l'exécution : plus personne ne l'attend, chacun ne voit que lui-même, et tous décident leur propre entrée. Le consensus est fini avant que le détecteur ne devienne exact. Il faut un autre garde-fou : ne jamais agir sans avoir entendu une majorité. C'est Chandra-Toueg.
Trois idées. (1) Des tours avec un coordinateur tournant (tour r : p((r-1) mod n)+1) : un coordinateur a au moins une fois son tour pendant que le détecteur est exact. (2) Une majorité avant de rien faire ou décider : les mensonges du détecteur ne peuvent pas nous isoler. (3) Un timestamp sur chaque estimation, le numéro du tour où elle a été adoptée : si une valeur a pu être décidée, elle est portée par une majorité avec un timestamp élevé, et le coordinateur suivant la reprend. C'est exactement l'architecture de Paxos, avec un coordinateur déterminé par le numéro de tour au lieu de proposants qui surgissent.
Quatre phases par tour : 1. tout le monde envoie (tour, estimation, timestamp) au coordinateur ; 2. celui-ci attend une majorité, retient l'estimation de plus grand timestamp et la propose à tous ; 3. chacun attend cette proposition ou la suspicion du coordinateur : il répond ack (en adoptant la valeur, timestamp := tour) ou nack (sans rien changer) ; 4. le coordinateur attend une majorité de réponses, et si aucune n'est un nack, il diffuse la décision par reliable broadcast.
// Algorithme 13.4 (Yale) : consensus de Chandra-Toueg, ◇S, f < n/2 estimate := input ts := 0 for r := 1, 2, 3, … : c := ((r-1) mod n) + 1 // coordinateur tournant phase 1 : envoyer ⟨r, estimate, ts⟩ à c phase 2 : if je suis c : attendre ⟨r, est, ts⟩ d'une majorité (moi compris) estimate := l'est de plus grand ts parmi elles envoyer ⟨r, estimate⟩ à tous phase 3 : attendre ⟨r, v⟩ de c ou suspecter c if reçu ⟨r, v⟩ : estimate := v ; ts := r ; envoyer ack(r) à c else : envoyer nack(r) à c phase 4 : if je suis c : attendre ack(r) ou nack(r) d'une majorité if aucun nack parmi elles : rbBroadcast(decide, estimate) upon rbDeliver(decide, v) : decide v ; s'arrêter // Algorithme 13.3 (Yale) : reliable broadcast, sous-routine procedure broadcast(m) : envoyer m à tous upon receiving m : if je n'ai jamais vu m : envoyer m à tous ; livrer m à moi-même
Majorité = ⌊n/2⌋+1. Le coordinateur s'envoie ses propres messages (il compte dans sa majorité et s'adresse son ack). Le RB relaie : si un seul correct reçoit la décision, tous les corrects la reçoivent, même si le coordinateur crashe en pleine diffusion.
Entrées : p1 = a, p2 = b, p3 = c, p4 = b, p5 = a. Tous les timestamps valent 0, donc le coordinateur du tour 1 peut retenir n'importe quelle des estimations de sa majorité ; l'exemple départage par le plus petit identifiant. Tout se passe en un seul tour.
Mêmes entrées. p5 crashe dès le départ. Au tour 1, p2 suspecte p1 à tort (p1 est vivant et même correct) : il répond nack, et le coordinateur ne décide pas, alors que p1, p3 et p4 ont bien adopté la valeur a avec le timestamp 1, c'est-à-dire une majorité. Puis p4 crashe. Il reste exactement trois corrects (p1, p2, p3), une majorité pile : c'est la limite f < n/2. Au tour 2, le coordinateur p2 reprend de force la valeur a, parce que son timestamp (1) bat celui de sa propre estimation b (0).
Le texte dit « si le coordinateur reçoit un ack d'une majorité, il décide », le pseudo-code dit « si aucun nack ne figure parmi la majorité de réponses attendue ». Les deux coïncident quand on attend exactement ⌊n/2⌋+1 réponses et qu'on décide seulement si elles sont toutes des ack : c'est la lecture suivie ici (et dans l'article original). Elle compte les réponses, pas les ack, et c'est ce qui rend l'exécution B instructive : au tour 1, trois ack existent au total, mais la nack de p2 arrive avant le dernier et figure parmi les trois premières réponses, donc p1 ne décide pas. Décider sur une majorité d'ack malgré un nack resterait sûr, car une majorité aurait adopté la valeur. Attendre des ack plutôt que des réponses serait en revanche faux pour la terminaison : voir le rôle des nack ci-dessous.
Deux ensembles de plus de n/2 processus ont toujours un élément commun. Si un coordinateur décide au tour r, une majorité a adopté (v, r) ; tout coordinateur ultérieur écoute une majorité, donc au moins un processus qui connaît (v, r) ou mieux. Même argument que Paxos. Et comme f < n/2, il reste toujours une majorité de vivants à attendre.
Le coordinateur reprend l'estimation de plus grand timestamp, pas la sienne ni la première reçue. Dans l'exécution B, p2 abandonne b (ts 0) pour a (ts 1) : c'est exactement ce qui empêche un deuxième coordinateur de défaire une valeur déjà soutenue par une majorité.
Un processus qui suspecte le coordinateur abandonne le tour. S'il ne disait rien, le coordinateur attendrait peut-être des ack qui ne viendront jamais (ici, trois sur cinq suspectent : p1 resterait avec un seul ack). Le nack le libère, et signale en plus « ne décide pas, je n'ai pas adopté ». Sans lui, plus de terminaison.
Supposons que le coordinateur du tour r diffuse decide(v). Il a vu des ack de la part d'une majorité Q : tous ces processus ont donc (v, r) au moment de répondre. Montrons par récurrence sur r' ≥ r que toute estimation avec un timestamp ≥ r vaut v. Au tour r' > r, le coordinateur lit les estimations d'une majorité Q' ; Q et Q' partagent un processus, dont le timestamp est ≥ r (il ne baisse jamais), donc le plus grand timestamp lu est ≥ r, et par récurrence la valeur correspondante est v. La proposition est v, et tout ce qui est adopté au tour r' est (v, r'). Aucune autre valeur ne peut donc plus jamais être proposée ni décidée. La seule subtilité est que deux coordinateurs puissent diffuser une décision : alors c'est la même valeur.
Personne ne reste bloqué : les attentes des phases 1, 2 et 4 sont des attentes de majorité, et une majorité de corrects répond toujours (ceux qui ont déjà décidé rediffusent la décision, que le bloqué reçoit par le RB) ; l'attente de la phase 3 se termine par la suspicion d'un coordinateur mort (complétude forte). Donc on fait au plus un nombre fini de tours avant la stabilisation. À partir du moment t où un correct c n'est plus jamais suspecté, au premier tour où c est coordinateur (il revient tous les n tours), tout correct reçoit sa proposition, répond ack, c reçoit une majorité d'ack sans nack et diffuse la décision : tout correct décide.
Coût : environ 3n messages par tour (n estimations, n propositions, n réponses), plus la décision en RB (jusqu'à n² avec les relais). Dans le meilleur cas (exécution A), un seul tour. Piège : croire que « majorité d'ack » suffit à décider sans regarder les réponses précédentes, ou oublier le nack de la phase 3.
Peut-on garder Chandra-Toueg et tolérer plus de pannes avec ◇P, en étant plus malin ? Non, même avec ◇P (donc a fortiori ◇S). Argument de partition de Yale : ◇P a le droit de mentir pendant un long début d'exécution, et le consensus doit se terminer malgré tout.
Le ressort de l'argument : ne pas pouvoir distinguer « l'autre moitié est morte » de « l'autre moitié est lente et ◇P ment ». Si l'algorithme doit tolérer f = n/2 pannes, il doit décider en n'ayant entendu que n/2 processus, ce que font les deux moitiés, chacune pour une valeur différente. Quand ◇P cesse enfin de mentir, c'est trop tard. Avec f < n/2, chaque processus attend plus de n/2 réponses, et deux telles familles ne sont jamais disjointes : l'exécution à deux moitiés ne peut plus se produire.
| Détecteur | Pannes tolérées pour le consensus | Pourquoi |
|---|---|---|
| P, S | f ≤ n−1 (au moins un correct) | l'exactitude est vraie pendant toute l'exécution pour au moins un correct : attendre ce processus est sûr |
| ◇P, ◇S | f < n/2 (majorité de corrects) | l'exactitude n'arrive qu'un jour : avant, on doit exiger une majorité pour ne pas décider seul |
08 · Paxos et Ring Paxos
Les algorithmes vus jusqu'ici supposent un détecteur parfait (P) ou une synchronie qui finit par arriver (◇S). Paxos prend un modèle plus rude : réseau asynchrone, messages perdus, processus qui plantent puis redémarrent. La sûreté ne dépend jamais du timing. La vivacité, elle, attend que le système se calme.
Des proposeurs veulent imposer une valeur, des acceptors votent, des learners constatent le résultat. Chaque tentative porte un numéro unique et croissant. Phase 1 : le proposeur demande à une majorité d'acceptors de promettre d'ignorer les numéros plus petits, et ils lui révèlent leur dernier vote. Phase 2 : il demande le vote ; si un vote antérieur existe, il doit reprendre la valeur de plus haut numéro, pas la sienne. Deux majorités se recoupent toujours, ce qui empêche de contredire une valeur déjà choisie. La vivacité exige un leader stable, sinon deux proposeurs peuvent se doubler sans fin.
Pas de borne de temps, messages perdus ou en retard, pas de fautes byzantines. Un acceptor garde son état sur disque : il peut redémarrer sans renier ses promesses. Il faut une majorité d'acceptors vivants (f < n/2).
Le proposeur propose, l'acceptor vote, le learner apprend la valeur choisie. Un même processus peut tenir les trois rôles. Dans le papier Ring Paxos, un coordinateur joue le proposeur de chaque tour.
Chaque tour porte un numéro unique (par exemple un compteur suivi de l'identifiant du processus). Un numéro plus grand signifie un tour plus récent : il peut annuler les promesses faites à un tour plus ancien.
Un comité doit fixer une date de réunion, mais le téléphone est mauvais et les secrétaires ne se coordonnent pas. Chaque secrétaire tire un ticket numéroté. Avant de proposer sa date, il appelle les membres : « Promettez-vous de ne plus écouter un ticket plus petit que le mien ? Et avez-vous déjà accepté une date ? » Un membre qui a promis au ticket 5 refuse ensuite toute demande du ticket 4. Si l'un des membres a déjà accepté une date, le secrétaire adopte cette date au lieu de la sienne : elle a peut-être déjà été choisie par une majorité, et la changer créerait deux décisions.
Les slides, Rutgers et Yale parlent de prepare, promise, accept. Le papier Ring Paxos (exo 4) numérote les messages 1A à 2B et nomme les variables rnd, v-rnd, v-val. Le visualiseur ci-dessous emploie le premier vocabulaire, les exercices le second.
| Étape | Slides, Rutgers, Yale | Papier Ring Paxos | Contenu |
|---|---|---|---|
| Phase 1a | prepare(n) | (1A, c-rnd) | le proposeur demande une promesse pour son numéro |
| Phase 1b | promise(n, dernier vote) | (1B, rnd, v-rnd, v-val) | l'acceptor promet et révèle son dernier vote |
| Phase 2a | accept(n, v) | (2A, c-rnd, c-val) | le proposeur demande de voter pour v |
| Phase 2b | accepted(n, v) | (2B, v-rnd, v-val) | l'acceptor a voté |
| Phase 3 | learn / décision | (décision, v-val) | majorité de votes au même numéro : valeur choisie |
| État d'un acceptor | numéro promis, dernier vote | rnd, v-rnd, v-val | rnd : plus haut numéro écouté. v-rnd, v-val : dernier vote (0 et ⊥ au départ) |
| État du proposeur | numéro, valeur | c-rnd, c-val | numéro du tour en cours et valeur choisie pour ce tour |
upon proposer envoie la valeur v do c-rnd := un numéro unique, plus grand que tous ceux déjà utilisés send (1A, c-rnd) to tous les acceptors upon (1B, rnd, v-rnd, v-val) d'une majorité avec rnd = c-rnd do k := le plus grand v-rnd reçu if k = 0 then c-val := v // aucun vote : libre else c-val := le v-val reçu avec v-rnd = k send (2A, c-rnd, c-val) to tous les acceptors upon (2B, v-rnd, v-val) d'une majorité tous avec v-rnd = c-rnd do send (décision, v-val) to les learners
upon (1A, c-rnd) do if c-rnd > rnd then rnd := c-rnd // la promesse send (1B, rnd, v-rnd, v-val) upon (2A, c-rnd, c-val) do if c-rnd >= rnd then rnd := v-rnd := c-rnd // le vote v-val := c-val send (2B, v-rnd, v-val)
Deux tests, deux comparaisons différentes : strictement plus grand pour promettre (un numéro ne se promet qu'une fois), plus grand ou égal pour voter (le vote qui suit la promesse porte le même numéro). Les acceptors doivent écrire rnd, v-rnd, v-val sur disque avant de répondre.
P1 veut imposer x avec le numéro 1, P2 veut imposer y avec le numéro 2, et le réseau les met en concurrence. Les valeurs, les numéros et les états de la colonne de droite sortent d'une exécution réelle de l'algorithme ci-dessus, pas d'un dessin fait à la main.
P1, P2 : proposeurs et learners. a1, a2, a3 : acceptors. La colonne de droite donne rnd, v-rnd, v-val des acceptors et c-rnd, c-val des proposeurs.
Le plus grand numéro gagne le droit de parler, pas le droit d'imposer sa valeur. P2 a le numéro le plus élevé et pourtant c'est la valeur de P1 qui est décidée. Si P2 avait reçu les promesses de a2 et a3 seulement (aucun vote antérieur), il aurait gardé y : x n'avait alors qu'un seul vote sur trois, donc n'était pas choisi, et rien n'est contredit.
Une valeur est choisie quand une majorité d'acceptors a voté pour elle au même numéro n. On veut montrer qu'aucun tour n' > n n'impose une autre valeur. Pour atteindre sa phase 2, le tour n' a reçu des promesses d'une majorité T. La majorité S qui a voté (n, v) et T se recoupent : un acceptor a est dans les deux. Deux cas :
C'est exactement ce que montre l'étape 5 du visualiseur : les accept du tour 1 arrivent trop tard chez a2 et a3, ils sont refusés. La promesse sert à rendre le passé figé : après avoir promis le numéro 2, un acceptor ne peut plus voter au tour 1, donc ce qu'il rapporte reste vrai.
Un acceptor vote localement. La valeur est choisie dès qu'une majorité a voté, mais il est possible que personne ne le sache : le coordinateur peut avoir planté avant de voir les votes. La valeur reste pourtant protégée, parce que tout tour suivant la retrouvera dans les promesses (voir l'exo 4, question 3, où le coordinateur tombe juste après le second vote).
Deux proposeurs peuvent se doubler à l'infini : P1 prépare le numéro 1, P2 prépare le 2 ce qui invalide l'accept de P1, P1 revient avec le 3 qui invalide celui de P2, et ainsi de suite. Aucun acceptor ne vote jamais. C'est le même obstacle que FLP : en asynchrone, on ne peut pas à la fois toujours rester sûr et toujours terminer. Paxos choisit la sûreté, et ne termine que s'il existe un intervalle assez long avec un seul proposeur actif qui ne plante pas.
Deux remèdes en pratique : un recul aléatoire exponentiel après un échec, ou une élection de leader en arrière-plan : seuls les acceptors qui reconnaissent le leader traitent ses messages. Ce mécanisme d'élection est un détecteur de pannes, le plus faible suffisant pour le consensus, appelé Ω (Yale, section 12.2.4). Bon cas, sans panne ni concurrent : quatre délais de message avec l'annonce aux learners. Le slide de conclusion parle de deux phases aller-retour par proposeur au pire avant de parvenir au consensus.
Structure proche de Chandra-Toueg (Yale, section 13.4) : un estimé accompagné d'un timestamp, une majorité interrogée, la valeur de plus grand timestamp reprise. Ici le timestamp est v-rnd, mais le proposeur n'est pas imposé par un tour tournant : n'importe qui peut se présenter avec un numéro plus grand.
08 · Multi-Paxos, SMR et Ring Paxos
Un consensus isolé ne sert à rien. On l'utilise en série pour fabriquer un journal commun, sur lequel on bâtit un service tolérant aux pannes.
Plusieurs réplicas du même service déterministe appliquent les mêmes commandes dans le même ordre : ils restent identiques. Il faut donc que chaque commande reçue arrive à tous les réplicas corrects et que personne ne soit en désaccord sur l'ordre : c'est la diffusion atomique (chap. 4, ordre total), qui se réduit à une suite de consensus, un par case du journal. Chubby, Zab (ZooKeeper) et d'autres reposent là-dessus (slide de conclusion).
Si le même leader reste en place, on saute la phase 1 entre deux cases consécutives : il suffit d'un aller-retour accept, accepted par commande (Yale, section 12.3). Le numéro de tour est coupé en un numéro majeur (changé quand le leader change) et un numéro mineur. Paxos Made Live parle de master et ajoute le traitement par lots de commandes soumises par plusieurs threads.
Le papier de Marandi, Primi, Schiper et Pedone (DSN 2010) cherche un débit maximal en grappe. Constat de départ : l'ip-multicast d'un seul émetteur est fiable et bien plus rapide que l'unicast, mais plusieurs émetteurs simultanés provoquent des pertes (plus de 15 % de paquets perdus avec cinq émetteurs à fort débit, figure 2 du papier). D'où l'architecture :
Prop : proposeur. Coord : coordinateur, dernier de l'anneau. A1, A2 : acceptors de l'anneau. Spare : acceptor de réserve. Lrn : learner. Pointillés or : ip-multicast. Les variables sont celles du papier (Algorithme 2).
Avec le papier : débit utile jusqu'à 90 % de la capacité d'un réseau gigabit (indice MTE), latence de livraison sous 5 ms, et débit à peu près constant quand le nombre de récepteurs augmente (jusqu'à 25 testés). Les implémentations de Paxos en ip-multicast seul ou en unicast seul restent sous 5 %. La latence théorique est de f + 3 délais de message. Le coordinateur reste le processus le plus chargé (88 % de CPU au pic).
Si le coordinateur ou un acceptor de l'anneau tombe, un nouveau coordinateur est élu et refait la phase 1 en posant un nouvel anneau sans l'acceptor fautif. Comme dans Paxos, plusieurs coordinateurs peuvent coexister sans mettre la sûreté en danger ; la vivacité attend un coordinateur unique stable.
| Critère | Hiérarchique (slides 43-44) | Chandra-Toueg | Paxos |
|---|---|---|---|
| Hypothèse de synchronie | détecteur parfait P (bornes de temps) | ◇S : la synchronie finit par arriver | aucune pour la sûreté ; Ω pour la vivacité |
| Pannes tolérées | crash-stop, jusqu'à n - 1 | crash-stop, f < n/2 | crash-recovery, f < n/2 acceptors |
| Qui parle quand | le processus de rang r au tour r, ordre fixé d'avance | coordinateur tournant, c = ((r-1) mod n) + 1 | tout proposeur peut ouvrir un numéro à tout moment |
| Comment la valeur est choisie | on adopte la proposition du tour le plus récent (r > proposer) ; au final s'impose la valeur du plus petit rang correct | valeur du plus grand timestamp parmi une majorité d'estimés | valeur du plus grand v-rnd parmi une majorité de promesses |
| Ce qui protège une valeur déjà décidée | l'exactitude de P : on ne saute un tour que si son leader a livré ou a vraiment planté | recoupement de majorités | recoupement de majorités |
| Décision | le leader décide à son tour, sans attendre d'acquittement (non uniforme) | majorité d'ack, puis reliable broadcast | majorité de votes au même numéro |
| Uniforme ? | non, dans la version des slides | oui | oui |
1. Paxos : phase 1 (prepare, promise) puis phase 2 (accept, accepted), numéros uniques croissants, décision à la majorité. 2. Règle clé : reprendre la valeur du plus grand v-rnd reçu, jamais la sienne si un vote existe ; la sûreté vient du recoupement de deux majorités. 3. Sûreté toujours, vivacité seulement avec un leader stable (Ω) : sinon duel de proposeurs, cf. FLP. 4. Multi-Paxos saute la phase 1 sous un leader stable ; Ring Paxos met les votes en anneau, un seul émetteur multicast. 5. Paxos résout le consensus en asynchrone avec f < n/2, donc CP au sens de CAP.
09 · CAP, PACELC et cohérence à terme
Le consensus donne une cohérence forte, mais il coûte des messages, de la latence et, sans majorité, de la disponibilité. La conclusion du cours (slide 46) invite à viser une cohérence plus faible quand l'application le permet, comme Dynamo ou Cassandra. Cette partie explique ce que l'on gagne et ce que l'on paie.
CAP : quand le réseau se coupe (P), un système répliqué doit choisir entre répondre (A), au risque d'une réponse périmée, et refuser pour rester cohérent (C, au sens linéarisable). La partition n'est pas un choix : on ne choisit que CP ou AP. PACELC ajoute le cas normal : sans partition, il reste un compromis entre latence et cohérence. La cohérence à terme est le prix de A et de la latence : les copies divergent puis convergent, mais les écritures concurrentes sont poussées vers l'application (le talon d'Achille). Dynamo les détecte avec des horloges vectorielles, garde les versions concurrentes (siblings) et laisse l'application fusionner.
Deux agences d'une même banque tiennent chacune un registre du compte de Camille, qui contient 100 euros. La ligne téléphonique entre les agences tombe. Camille, dans l'agence 1, demande à retirer 80 euros. Son frère, dans l'agence 2, fait la même demande sur le même compte. Chaque agence a le choix.
Aucune agence ne paie tant qu'elle ne peut pas vérifier auprès de l'autre. Le solde reste juste, mais deux clients repartent bredouilles : le service est indisponible.
Chaque agence paie. Les clients sont servis, mais le compte est maintenant à moins 60 euros : les deux registres se contredisent et il faudra réparer après coup.
Tant que la ligne est coupée, attendre l'autre agence c'est être indisponible, et ne pas l'attendre c'est risquer la contradiction. Le théorème CAP est cette observation, démontrée proprement.
La linéarisabilité : tout se passe comme s'il n'existait qu'une copie de la donnée et que chaque opération s'exécutait instantanément, dans un ordre unique qui respecte le temps réel. Toute lecture renvoie la dernière écriture terminée, ou une erreur. Ce n'est pas le C d'ACID, qui parle des invariants d'une transaction.
Toute requête reçue par un nœud non défaillant obtient une réponse qui n'est pas une erreur, en temps fini. La réponse n'a pas à être la plus récente. Exigence forte : même un nœud isolé dans une minorité doit répondre.
Le système continue de fonctionner alors que le réseau perd ou retarde un nombre quelconque de messages entre nœuds. Concrètement : des sous-groupes de nœuds vivants ne se parlent plus, sans savoir si les autres sont tombés ou seulement coupés.
Le théorème (conjecture de Brewer en 2000, démontrée par Gilbert et Lynch en 2002) : pendant une partition, on ne peut pas garantir à la fois C et A. L'idée de la preuve tient en trois lignes. Deux réplicas, une partition, une écriture sur l'un et une lecture sur l'autre. Si le second répond, il renvoie une valeur qui ne peut pas être la dernière (C violée). S'il refuse ou attend, une requête d'un nœud sain n'a pas de réponse (A violée).
Un réseau réel perd des paquets, retarde des messages, tombe en panne par segments : un commutateur, un câble, une pause de ramasse-miettes assez longue pour ressembler à un crash. On ne choisit pas d'avoir des partitions, on choisit ce que le système fait pendant. C'est pourquoi le menu « 2 parmi 3 » est trompeur : sans partition, on peut avoir C et A ensemble (Brewer l'a reconnu en 2012). Le choix CP ou AP ne se pose que pendant la panne.
« CA » veut dire : cohérent et disponible, et qui ne tolère pas les partitions. Deux lectures honnêtes de cette étiquette.
Conclusion à retenir : dans un système réparti, « CA » revient à « CP ou AP, selon ce que fait le code le jour de la panne ». La page Wikipedia du théorème note d'ailleurs qu'aucune base NoSQL n'est à classer CA.
Il ne parle pas de latence (voir PACELC, juste après), et il ne dit pas que tout le système doit faire le même choix : Cassandra laisse régler la cohérence par opération. Enfin le C de CAP est la cohérence la plus forte (linéarisabilité). Dire « mon système n'a pas le C de CAP » ne veut pas dire qu'il est incohérent : il a une garantie plus faible, comme la cohérence à terme.
09 · PACELC
Les partitions sont rares. Le reste du temps, un système réparti fait quand même un compromis, et c'est lui qui pèse sur le quotidien : la latence. Daniel Abadi l'a formulé en 2012 sous le nom PACELC.
Si Partition : choisir entre A et C. Else (sinon, en fonctionnement normal) : choisir entre Latence et Cohérence. Un système se note par deux paires : PA/EL (disponible, rapide, cohérence faible), PC/EC (cohérent tout le temps), et les deux mélanges PA/EC et PC/EL.
Lire sur la copie locale, au contraire, répond en un aller-retour local, quitte à voir une valeur périmée. Un quorum de lecture ou d'écriture réglable (instrument de la section Dynamo, plus bas) permet de placer le curseur.
| Système | Partition | Sinon | Remarque |
|---|---|---|---|
| Dynamo (papier d'Amazon), Cassandra, Riak | PA | EL | Cohérence à terme par défaut ; R, W et le niveau de cohérence sont réglables. |
| MongoDB | PA | EC | Classification de Wikipedia ; dépend de la configuration. |
| PNUTS (Yahoo) | PC | EL | Choisit la cohérence en partition, la latence sinon. |
| BigTable, HBase | PC | EC | Cohérent en toutes circonstances. |
| VoltDB / H-Store | PC | EC | Base ACID complète. |
| DynamoDB (le service AWS) | PA ou PC | EC | Classé diversement selon les sources : modèle à leader, lectures à terme par défaut. Voir la nuance Dynamo et DynamoDB plus bas. |
Source des classements : page Wikipedia sur PACELC. Ils sont discutés et changent avec la configuration choisie par l'utilisateur : à lire comme des tendances, pas comme des étiquettes figées.
09 · Cohérence à terme
Si le prix de C est de l'indisponibilité et de la latence, on peut choisir de ne pas payer : laisser les copies diverger un moment, et garantir seulement qu'elles se rejoignent.
Cohérence à terme (eventual consistency) : si plus aucune écriture n'a lieu sur une donnée, alors, à terme, toutes les lectures renvoient la dernière valeur écrite. Les mises à jour se propagent de façon asynchrone ; en attendant, deux réplicas peuvent répondre différemment.
Image : plusieurs personnes éditent chacune une copie d'un document partagé hors ligne. Leurs vues diffèrent pendant un moment, puis se synchronisent. Tout est dans le « puis » : la garantie ne dit ni quand, ni vers quelle valeur.
| C de CAP (linéarisabilité) | Cohérence à terme | |
|---|---|---|
| Nature | Propriété de safety : à chaque instant, aucune lecture périmée. | Propriété de liveness : les copies finissent par converger. |
| Lecture juste après une écriture | Voit forcément l'écriture. | Peut renvoyer l'ancienne valeur. |
| Écritures concurrentes | Ordonnées de façon unique, par coordination. | Acceptées de chaque côté, conflits à régler après. |
| Coût | Quorum, leader, consensus. | Peu de coordination : rapide et disponible. |
On retrouve la distinction du chapitre 4. Un système à cohérence à terme renonce au C de CAP pour obtenir A et la latence : c'est pour cela qu'il se classe AP.
Converger est facile à promettre, mais converger vers quoi ? Quand deux clients écrivent la même donnée sur deux réplicas séparés, le retour du réseau livre deux versions sans moyen automatique de savoir laquelle est la bonne. La base ne comprend pas le sens des données : elle déplace le problème vers l'application. Là est le talon d'Achille : la cohérence à terme évite la coordination en écriture, et rend en échange la résolution des conflits obligatoire.
| Stratégie | Principe | Avantage | Coût |
|---|---|---|---|
| Dernier écrivain gagne (LWW) | Chaque version porte un horodatage, la plus récente gagne, l'autre est jetée. | Trivial, aucune logique applicative. | Perd des écritures acquittées, et dépend d'horloges physiques qui se décalent. |
| Fusion applicative | Le code métier combine les versions (union d'un panier, types de données à fusion sûre comme les CRDT). | Aucune écriture perdue. | À écrire pour chaque type de donnée ; peut ressusciter des éléments supprimés. |
| Siblings | Le système garde toutes les versions concurrentes et les rend au client à la lecture. | Rien n'est écarté en silence. | Le client doit traiter plusieurs réponses. |
| Montrer à l'utilisateur | On lui demande de trancher (comme un conflit de fusion dans git). | Le seul qui connaisse le sens, c'est lui. | Mauvaise expérience, pas toujours possible. |
« Dernier écrivain gagne » donne l'apparence d'une cohérence : tout le monde converge vers la même valeur. Mais cette valeur peut avoir oublié une écriture que le système avait acquittée. Les horloges vectorielles servent justement à ne pas confondre « plus récent » et « concurrent ».
09 · Dynamo en pratique
Le papier Dynamo: Amazon's Highly Available Key-value Store (DeCandia et al., SOSP 2007) décrit le magasin clé-valeur derrière, entre autres, le panier d'achat. Son mot d'ordre : toujours accepter l'écriture (always writeable), quitte à réconcilier plus tard.
Dynamo est le système interne décrit dans le papier de 2007 : hachage cohérent, quorums N, R, W, horloges vectorielles, siblings rendus au client, réconciliation par l'application. DynamoDB est le service d'AWS, inspiré de Dynamo mais bâti autrement : chaque partition a un leader et deux réplicas, l'écriture est acquittée quand une majorité l'a persistée, et l'on choisit pour chaque lecture entre cohérence forte (via le leader) et cohérence à terme (n'importe quel réplica). Il n'expose ni horloges vectorielles ni siblings : un PutItem remplace l'élément, et les tables globales multi-régions réconcilient par dernier écrivain gagne. L'énoncé du prof et le corrigé mélangent les deux : les horloges vectorielles de la suite sont celles du papier Dynamo, pas celles que l'on manipule dans DynamoDB. Cassandra, elle, reprend de Dynamo la distribution et la réplication et résout les conflits par horodatage.
On hache chaque clé sur un anneau de positions. Le coordinateur de la clé est le premier nœud rencontré dans le sens horaire ; il stocke la donnée et la réplique sur les N-1 nœuds suivants. Cette liste est la preference list, avec quelques suppléants en plus pour les pannes. Chaque machine tient plusieurs positions (des nœuds virtuels) pour répartir la charge. Avantage du hachage cohérent : ajouter ou retirer un nœud ne déplace que les clés voisines, pas toutes.
Chaque donnée a N copies. Une écriture est réussie quand W nœuds l'ont confirmée ; une lecture est réussie quand R nœuds ont répondu. La condition qui compte : R + W > N. Alors tout ensemble de R lecteurs rencontre au moins un des W nœuds qui ont reçu la dernière écriture (deux parties de N éléments, de tailles R et W, se coupent dès que R + W > N). Le papier cite la configuration (N, R, W) = (3, 2, 2). Mettre W = 1 rend l'écriture toujours acceptée tant qu'un nœud répond ; mettre R + W ≤ N donne la cohérence à terme avec une latence plus basse, puisqu'on n'attend que le R-ième ou W-ième répondant le plus rapide.
Les attentes en ms sont illustratives (latences fictives de 2 à 150 ms, du réplica le plus proche au plus lointain), pour montrer que la latence suit le R-ième ou le W-ième le plus rapide. Le recoupement R + W > N garantit qu'on rencontre un réplica à jour, pas la linéarisabilité complète : voir le sloppy quorum juste après.
Un quorum strict serait indisponible dès qu'un des N nœuds attitrés est en panne. Dynamo utilise donc un sloppy quorum : lectures et écritures s'adressent aux N premiers nœuds en bonne santé de la liste, pas forcément les N premiers de l'anneau. Si le nœud A est en panne pendant une écriture, sa copie part chez un suppléant D, avec une indication (hint) qui nomme le destinataire prévu. D la garde à part et la remet à A quand il revient : c'est le hinted handoff. Conséquence : avec un sloppy quorum, R + W > N ne garantit plus que lecture et écriture se recoupent, car elles peuvent porter sur des ensembles de nœuds différents.
Chaque version d'un objet porte une horloge vectorielle : une liste de couples (réplica, compteur). Attention à la différence avec le chapitre 2 : ici les composantes sont les réplicas qui coordonnent les écritures, pas les clients. Deux versions sont comparées composante par composante :
// V, W : horloges vectorielles (dictionnaires réplica → compteur, 0 par défaut) précède(V, W) : (∀ r : V[r] ≤ W[r]) ∧ (∃ r : V[r] < W[r]) // V est un ancêtre de W : on peut l'oublier concurrentes(V, W) : ¬ précède(V, W) ∧ ¬ précède(W, V) ∧ V ≠ W // aucune ne domine : on garde les deux put(clé, valeur, ctx) // exécuté par le coordinateur r V := copie de ctx ; V[r] := V[r] + 1 supprimer les versions locales qui précèdent V stocker (valeur, V) ; répliquer ; succès si W - 1 autres nœuds répondent get(clé) : renvoie toutes les versions non dominées, et un ctx = maximum composante par composante
Le contexte est ce qui relie une lecture à l'écriture suivante : le client le reçoit au get et le renvoie tel quel au put. C'est lui qui dit « je modifie ce que j'ai lu ». Sans lui, un put aveugle repartirait d'un vecteur vide et créerait une version concurrente de tout le reste. Le papier tronque les vecteurs à une dizaine de couples (en supprimant le plus ancien) pour limiter leur taille, au prix de comparaisons moins précises.
Deux mécanismes se complètent. La réconciliation syntaxique se fait toute seule : une version qui en précède une autre est écartée. La réconciliation sémantique est celle de l'application : si les versions sont concurrentes, le client reçoit les siblings et décide (pour un panier, l'union). Le papier note que cette fusion ne perd jamais un « ajout au panier », mais que des éléments supprimés peuvent réapparaître. Lors d'une lecture qui découvre des réplicas en retard, le coordinateur écrit la version à jour vers eux : c'est le read repair.
Le read repair ne répare que les clés lues. Pour les autres, chaque nœud maintient, par plage de clés, un arbre de Merkle : les feuilles sont les hachages des valeurs, chaque nœud interne est le hachage de ses enfants. Deux réplicas comparent les racines : si elles sont égales, les plages sont identiques et rien ne circule ; sinon on descend dans les sous-arbres qui diffèrent, jusqu'aux clés à synchroniser. On transfère très peu de données et on lit peu le disque. C'est cette anti-entropie, en tâche de fond, qui rapproche les copies après une partition.
CAP : pendant une partition, choisir CP (refuser) ou AP (répondre) ; C = linéarisabilité, pas le C d'ACID ; « CA » n'existe qu'hors partition.
PACELC : sans partition, latence contre cohérence ; la cohérence forte coûte des quorums et des allers-retours.
Cohérence à terme : liveness, pas le C de CAP ; talon d'Achille = conflits d'écriture déplacés vers l'application (LWW, fusion, siblings).
Quorums : R + W > N pour que lecture et écriture se recoupent ; le sloppy quorum et le hinted handoff gardent la disponibilité.
Horloges vectorielles : le coordinateur incrémente SA composante à partir du contexte ; ni l'une ni l'autre ne précède = concurrentes = siblings. Dynamo n'est pas DynamoDB.
10 · Exercices corrigés
Dans l'ordre des énoncés du prof : exercices des slides, puis Exo 1 à Exo 5 du dossier Moodle, puis le homework CAP et DynamoDB.
Un seul compteur sert à la fois à envoyer les heartbeats et à détecter. Est-ce un bon algorithme ? Comportement si Δ est mal calibré, délai entre deux heartbeats, délai maximal de détection.
Réponses rédigées par moi à partir du code des slides. Le prof n'a pas publié de corrigé de cet exercice.
upon event <Init> : alive := Π ; suspected := ∅ ; period := TimeDelay ; startTimer(period) upon event <Timeout> : if (alive ∩ suspected) ≠ ∅ then period := period + Δ forall pi ∈ Π : if pi ∉ alive and pi ∉ suspected then suspected := suspected ∪ {pi} ; trigger <suspect | pi> else if pi ∈ alive and pi ∈ suspected then suspected := suspected \ {pi} ; trigger <restore | pi> trigger <pp2pSend | pi, [HEARTBEAT]> alive := ∅ ; startTimer(period) upon event <pp2pDeliver | src, [HEARTBEAT]> : alive := alive ∪ {src}
Le même period fixe la cadence des heartbeats et la fenêtre de détection. C'est simple et correct pour ◇P, mais couplé : quand le réseau est lent, period augmente, donc on envoie moins souvent des heartbeats, ce qui retarde encore la détection. La version du cours (slide 18) sépare γ (émission, fixe) et T (timeout, croissant), ce qui évite ce couplage.
Si TimeDelay est inférieur au délai réel, chaque processus suspecte à tort tous les autres au premier timeout, les restaure au suivant (le heartbeat est arrivé entre-temps) et augmente alors la période de Δ. Le cycle suspect, restore, période + Δ se répète, mais chaque tour allonge strictement la période : après au plus ⌈(δ − TimeDelay) / Δ⌉ cycles (δ, la borne inconnue sur le délai), elle dépasse le délai et les fausses suspicions cessent. Si Δ est minuscule, il y en a beaucoup ; si Δ est énorme, il y en a peu mais la détection ensuite est lente. Compromis typique.
Au début : TimeDelay. À un instant quelconque : period = TimeDelay + j · Δ, où j est le nombre de timeouts passés où un processus suspecté a été trouvé vivant. Attention : l'incrément est fait une seule fois par timeout, que 1 ou 10 processus soient restaurés. La période ne diminue jamais.
Supposons une borne δ sur les délais et la période stabilisée à P. Si q crashe à l'instant c, son dernier heartbeat arrive au plus à c + δ. Le premier timeout qui suit peut encore le compter (il est dans la fenêtre), le suivant ne le voit plus et suspecte. D'où une détection au plus à c + δ + 2P. Et P est lui-même borné, puisque les incréments s'arrêtent quand la période dépasse les délais : P ≤ max(TimeDelay, δ + Δ). Sans borne δ, il n'existe aucune borne de détection.
Le deuxième processus tombe avant son ACK, un message est perdu dans la diffusion d'origine, trouver une exécution qui décide b, pourquoi le test rank(p) ≥ round.
Les trois scénarios sont exécutés par le simulateur : les valeurs de proposal, ackranks et detectedranks sont celles de l'algorithme, pas dessinées.
Le chef n'attend pas un ack qui ne viendra jamais : detectedranks ∪ ackranks = {1, 2, 3} dès que p2 est détecté, car p2 est dans detectedranks. p1 décide a et le dit par RB à p3. p2 est mort sans décider : l'accord uniforme tient.
Un message « perdu » à l'émission, c'est un chef qui crashe au milieu de sa boucle d'envoi : la copie pour p3 est partie, celle pour p2 jamais. Dans cette exécution la valeur décidée est b, pas a.
Remarquer que p3 a proposal = a en quittant le tour 1 (il avait stocké proposed[1] = a), et pourtant il décide b : sa décision vient du DECIDED b du chef du tour 2, pas de sa variable locale. Cela ne pose aucun problème : p1 n'avait rien décidé (il n'a jamais reçu d'ack), et le chef du tour 2 décide seulement après l'ack de tous les non-détectés, p3 compris. b est une valeur proposée, la validité tient.
Si rank(p) < round, le processus a déjà quitté le tour de p sans adopter sa valeur (elle n'était pas encore arrivée : ou bien elle n'y était pas, ou bien arrivée en retard). Lui laisser acquitter serait mentir : p croirait que ce processus a la valeur et pourrait décider alors que ce processus, passé au tour suivant, porte autre chose, d'où un désaccord. Avec un détecteur parfait, ce cas n'arrive que si p est réellement crashé et l'ack serait inutile : le test fait surtout porter la preuve de sûreté sur un invariant local (« si j'ai acquitté p, je n'ai pas dépassé son tour sans adopter sa valeur ») qui reste vrai même avec un détecteur imparfait. Il économise aussi un message.
Une exécution sans panne et deux avec pannes qui illustrent la non-uniformité ; est-ce un consensus correct ? uniforme ? Question ajoutée : une exécution où le test (r < rank(self)) ∧ (r > proposer) échoue, et pourquoi il est important.
Algorithme étudié : celui de la section 06. Les exécutions sont simulées. Le corrigé d'étudiant fourni par le prof contient quatre cas (sans panne, p1 crashe après décision, un cas avec p2 qui décide b, et le cas du message en retard, « case n°4 ») ; ils sont repris ci-dessous avec les valeurs recalculées.
Voir la figure de la section 04. Chaque processus devient chef à son tour avec a adopté du tour 1 : p1 décide a, p2 adopte a puis décide a, p3 adopte a (de p2, le plus récent) puis décide a. Les tests r < rank(self) échouent à chaque fois qu'un processus reçoit son propre message ou celui d'un rang supérieur, et le processus ignore la valeur mais marque delivered.
Exécution 1 : p1 décide a puis crashe avant que son message ne parte (figure 06). p2 détecte le crash, devient chef du tour 2, ne connaît que sa proposition et décide b ; p3 décide b. Les corrects (p2, p3) sont d'accord, mais p1 a décidé a : désaccord uniforme violé. Exécution 2 : p1 puis p2 crashent chacun après avoir décidé a et b sans rien envoyer ; p3, seul survivant, décide c. Trois valeurs décidées, une seule parmi les corrects.
Oui, par les quatre propriétés. Validité : une valeur n'entre dans proposal que depuis un cPropose local ou un message reçu, et beb ne crée aucun message. Intégrité : on décide uniquement quand round = rank(self) et broadcast[round] = false, puis le drapeau passe à vrai : au plus une fois. Accord : soit i le plus petit rang parmi les corrects. p_i n'est jamais détecté (exactitude de P), donc personne ne dépasse le tour i sans livrer (i, vi). Les rangs inférieurs à i sont crashés. Tout message de rang ≥ i porte vi (par récurrence : le chef du tour i + 1 n'agit qu'après avoir livré (i, vi)), et les messages plus anciens sont rejetés par r > proposer. Donc tous les corrects décident vi. Terminaison : chaque tour finit, par un message d'un chef correct (validité de beb) ou par la détection d'un chef crashé (complétude forte de P), donc chaque correct atteint son propre tour et décide.
Non, les exécutions ci-dessus le montrent : le chef décide avant de diffuser. S'il tombe dans l'intervalle, sa décision n'engage personne. C'est exactement ce que corrige l'algorithme II par le tour d'ack.
(r < rank(self)) ∧ (r > proposer) n'est pas vérifiéIl y a deux façons de faire échouer le test, une par moitié, et elles servent à deux choses différentes.
Moitié 1 fausse : r ≥ rank(self). Cas le plus fréquent : mon propre message (r = rank(self)) ou celui d'un chef de rang supérieur, arrivé après mon tour. Dans la figure sans panne de la section 04, p2 reçoit son propre (2, a) puis le (3, a) de p3 : le test est faux, proposal et proposer ne bougent pas, mais delivered[2] et delivered[3] passent à vrai. Ce que ça protège : une fois chef j'ai décidé ma proposition, qui doit rester celle que j'ai annoncée.
Moitié 2 fausse : r ≤ proposer, donc un message en retard, et c'est le cas des exécutions avec pannes qui sert l'argument. Reprenons les figures 06 : dans celle de p1 crashé, p3 a adopté le tour 2 (proposer = 2) quand (1, a) arrive enfin : 1 < 3 est vrai, 1 > 2 est faux, le message est rejeté et p3 garde b. Ici c'est sans conséquence (p3 a déjà décidé), mais dans la version à quatre processus de la section 06 la moitié 2 est le seul rempart : sans elle p4 décide a alors que p2 a décidé b, avec elle p4 décide b.
Les deux moitiés rejettent des messages du passé au sens de la hiérarchie : la moitié 1 rejette ceux d'un tour que moi j'ai déjà joué (ou joue), la moitié 2 ceux d'un tour qu'un autre chef plus récent a déjà remplacé. Et comme les crashs ne sont pas détectés simultanément par tous, ces messages en retard existent vraiment : le test est ce qui rend l'algorithme insensible à l'ordre d'arrivée des messages de tours différents.
Q1 : jouer l'algorithme ◇S (Yale 13.4) à cinq processus, sans panne puis avec deux fautifs. Q2 : cinq questions de généralisation sur les détecteurs, la majorité, l'ordre des propositions et Paxos.
Énoncé du prof : lire le chapitre 13 des notes de James Aspnes (Yale). Les deux scénarios de Q1 sont exécutés par le script de la page : les tableaux ci-dessous sont générés par la même simulation que les animations de la section ◇S, donc cohérents avec elles.
Rappel du protocole (voir l'algorithme 13.4 plus haut). Tour r, coordinateur p((r-1) mod 5)+1. Phase 1 : estimations vers le coordinateur. Phase 2 : il attend 3 estimations (majorité de 5), retient celle du plus grand timestamp, la propose. Phase 3 : chacun reçoit (ack, adopte, ts := r) ou suspecte le coordinateur (nack, ne change rien). Phase 4 : il attend 3 réponses et diffuse decide par RB si aucune n'est un nack. Entrées : p1 = a, p2 = b, p3 = c, p4 = b, p5 = a.
Scénario 1 : aucune panne. Le coordinateur du tour 1 est p1. Les trois premières estimations arrivées sont celles de p1, p3 et p2, toutes de timestamp 0 : p1 garde a (plus petit identifiant, convention de l'exemple), le diffuse en (1, a). Personne ne suspecte p1, donc les cinq processus passent à (a, 1) et répondent ack. p1 voit des ack sans nack : decide(a) en reliable broadcast, et les cinq décident a. Le tableau suivant donne l'état (estimation, timestamp) de chacun après chaque phase.
Scénario 2 : deux processus fautifs. Les fautifs sont p5 (crash au départ) et p4 (crash après le tour 1). On ajoute la fausse suspicion typique de ◇S : au tour 1, p2 suspecte p1 avant d'avoir reçu sa proposition, alors que p1 est correct. Tour 1 : p1 retient a (parmi p1, p2, p3 arrivés les premiers), le propose. p1, p3 et p4 adoptent (a, 1) et répondent ack ; p2 répond nack et reste à (b, 0). Les trois premières réponses reçues par p1 sont celles de p2 (nack, très rapide), puis p1 et p3 (ack) : un nack, donc pas de décision. Pourtant une majorité (p1, p3, p4) tient maintenant (a, 1). Tour 2, coordinateur p2 : p4 est mort, p2 ne reçoit que trois estimations, (b, 0) de lui-même, (a, 1) de p1 et (a, 1) de p3. Le plus grand timestamp est 1, donc p2 abandonne b et propose (2, a). Les trois vivants adoptent (a, 2), répondent ack, p2 diffuse decide(a) : les trois corrects décident a.
Avec seulement ◇S, on décide encore : la fausse suspicion de p1 coûte un tour, pas la sûreté. La valeur a, déjà adoptée par une majorité au tour 1, est celle que le tour 2 décide, grâce aux timestamps et à l'intersection des majorités (p1 et p3 se trouvent dans les deux). Les deux fautifs laissent trois corrects sur cinq : exactement une majorité, c'est le cas limite f < n/2. Un troisième crash bloquerait tout coordinateur en attente de 3 réponses.
Animations pas à pas : exécution A (sans panne), exécution B (deux fautifs).
◇P et ◇S ont le droit de se tromper sans limite de durée avant un instant inconnu. Pendant cette période, un processus ne peut pas distinguer un autre processus mort d'un processus vivant mais suspecté à tort : les deux sont silencieux et suspectés. La terminaison oblige à décider malgré tout. Si f ≥ n/2, deux moitiés disjointes de n/2 processus peuvent se suspecter mutuellement et décider chacune sur ses propres entrées (0 d'un côté, 1 de l'autre), avant que le détecteur ne devienne exact : l'accord est violé. En exigeant f < n/2, tout processus attend plus de n/2 réponses : deux familles de réponses s'intersectent, et l'intersection propage ce qui a déjà été décidé. C'est l'argument de partition de Yale 13.5 (voir le schéma animé de la section).
Avec P (jamais de fausse suspicion) ou S (au moins un correct jamais suspecté), l'exactitude est vraie dès le départ, pas seulement un jour. Un suspect de P est réellement mort ; avec S, un processus peut en attendre un autre sans craindre que ce dernier soit « faussement mort » pour c. Le processus c ne se plaint jamais, tout le monde l'attend, et ce qu'il sait finit chez tous (algorithme 13.2). Aucune majorité n'est nécessaire, car aucun mensonge ne peut isoler les processus de c. Le seuil se lit sur la condition : il faut au moins un processus correct, soit f ≤ n−1. Avec S, c'est l'hypothèse même de l'exactitude faible (un correct existe). Sans correct, plus personne ne décide ; le consensus n'a plus de sens.
Une valeur peut être décidée par certains, puis ses témoins crasher ou devenir injoignables : les processus restants doivent la retrouver et la reprendre, sans qu'aucun survivant n'ait de preuve complète qu'elle a été décidée. Pour cela, ils comparent deux propositions concurrentes et doivent savoir laquelle prime : sans ordre, deux coordinateurs peuvent chacun recueillir une majorité pour des valeurs différentes. Un rang croissant (le numéro de tour et le timestamp dans Chandra-Toueg, le numéro de ballot dans Paxos, le rang du processus dans le consensus hiérarchique) donne la règle « la plus récente gagne » : le nouveau proposant lit les rangs, reprend la valeur du rang le plus élevé qu'il voit, et par intersection de majorités il voit nécessairement la valeur décidée. Le rang sert aussi à invalider les retardataires : un message de rang inférieur arrivé trop tard est ignoré, il n'écrase pas une valeur plus récente. Le sens (le plus petit rang gagne dans le consensus hiérarchique, le plus grand dans Paxos) n'a aucune importance : ce qui compte, c'est un ordre total et une règle de lecture unique pour tous.
Un détecteur transforme un silence en suspicion par timeout. Cela n'a de sens que si un crash (crash-stop) se manifeste par un silence permanent et si un processus vivant répond, en général, dans un délai fini. Deux hypothèses sont donc cachées. Modèle de pannes : en byzantin, une machine peut mentir, répondre aux heartbeats tout en trichant sur le reste, ou envoyer des messages différents à chacun : le silence n'est plus le symptôme, et il faut d'autres outils (authentification, quorums 3f+1). En crash-recovery, le silence n'est plus permanent, et les spécifications changent. Communication : si les délais n'ont aucune borne, un processus lent est indiscernable d'un mort et aucun timeout n'est correct ; par FLP, un détecteur ◇P serait alors un moyen de contourner l'impossibilité du consensus, donc il n'est pas implémentable en asynchrone pur. On suppose une synchronie partielle : une borne existe mais est inconnue, ou n'est valable qu'à partir d'un moment. ◇P s'implémente alors avec un timeout qui augmente à chaque erreur (algorithme du cours : T := T + δ quand une suspicion est retirée), jusqu'à dépasser la borne. P, lui, exige une synchronie complète (borne connue).
Ce que suppose Paxos : un système asynchrone, pas de détecteur fiable, des crashs (pas de byzantin dans la version de base), f < n/2 accepteurs en panne. La sûreté (validité et accord) est garantie toujours, quelles que soient les lenteurs ou les proposants concurrents. La vivacité n'est garantie que si, à partir d'un moment, un seul proposant stable agit : un leader, c'est-à-dire le détecteur Ω, la forme la plus faible de détecteur de pannes. Paxos suppose donc encore un détecteur, mais seulement pour la terminaison.
Pourquoi le code est plus complexe que les algorithmes à base de P ou S. Avec P, chaque processus a une vue fiable des vivants : un tour = un coordinateur connu, une seule proposition par tour, et un message de rang inférieur qui arrive trop tard n'est qu'une affaire de numérotation du tour. Dans Paxos, rien de tout cela n'est disponible : (1) plusieurs proposants peuvent croire être leader en même temps (la sûreté ne doit pas en souffrir), (2) un message peut arriver très tard et d'un tour passé, (3) personne ne sait si une valeur a déjà été décidée, parce que ses témoins peuvent être partis. D'où les deux phases : prepare/promise (« je veux le ballot n ; promets de n'accepter rien de plus petit, et dis-moi ce que tu as déjà accepté ») qui découvre les valeurs déjà peut-être choisies et invalide les ballots plus anciens, puis accept/accepted qui n'impose que la valeur du plus grand ballot trouvé. Chaque accepteur doit mémoriser trois choses (promesse, dernier accepté, rang). L'élection du leader est un module à part (Ω) : le prof a d'ailleurs fait remarquer sur la copie notée A- que l'élection n'est pas dans l'algorithme étudié.
1) P et S : f ≤ n−1, un correct jamais suspecté suffit ; ◇P et ◇S : f < n/2, par l'argument de partition. 2) Chandra-Toueg : coordinateur tournant, majorité d'estimations, plus grand timestamp, ack/nack, decide par RB si aucun nack. 3) Les nack servent la terminaison, les timestamps l'accord, l'intersection des majorités les relie. 4) Il faut un ordre croissant (tour, timestamp, ballot) pour que « la plus récente gagne ». 5) Les détecteurs supposent le crash-stop et une synchronie partielle ; Paxos s'en passe pour la sûreté et ne suppose qu'Ω pour la vivacité.
Lire le papier de Google (Chandra, Griesemer, Redstone, PODC 2007) sur l'implémentation réelle de Paxos. Pas de question formelle : voici ce qu'on en retient.
Synthèse établie sur le texte du papier. Contexte : remplacer la base répliquée d'un tiers dans Chubby (service de verrous de Google, une cellule = typiquement cinq réplicas dont un master) par un journal répliqué fondé sur Paxos, puis une base de données au-dessus.
Paxos tient en une page de pseudo-code, l'implémentation compte plusieurs milliers de lignes de C++. Le gonflement ne vient pas du langage : il faut implémenter des fonctionnalités et optimisations dispersées dans la littérature, dont certaines inédites. Les preuves d'une page ne passent pas à l'échelle d'un tel code. Le monde réel ajoute des pannes que l'algorithme ne prévoit pas : bugs, erreurs d'opérateur, spécification qui change. Leur conclusion : le résultat est fondé sur un protocole non prouvé, et la communauté a manqué d'outils et d'attention pour les tests.
De bas en haut : un journal répliqué (Paxos exécuté pour chaque entrée), une base de données faite d'un instantané local et d'un journal de rejeu, puis Chubby. L'API du journal soumet une valeur et appelle un callback sur chaque réplica. Le journal ne crée pas ses propres threads, ce qui permet des tests déterministes (point 7).
Paxos de base impose cinq écritures sur disque, chacune forcée, sur le chemin critique (propose, promise, accept, acknowledge, commit) : le flush peut dominer la latence. L'optimisation connue : omettre le message propose tant que le coordinateur ne change pas (le « master »). Reste une écriture par instance et par réplica, en parallèle. On peut aussi grouper plusieurs valeurs de threads différents dans une même instance. Un réplica en retard utilise un mécanisme de rattrapage (catch-up) à partir des journaux des autres.
Un disque qui perd son état fait renier des promesses, ce qui viole une hypothèse centrale de Paxos. Détection : une somme de contrôle dans chaque fichier, et un marqueur laissé dans GFS au premier démarrage (un disque vide qui retrouve ce marqueur sait qu'il a été effacé). Reconstruction : le réplica participe comme membre sans droit de vote, il rattrape son retard mais ne répond ni promise ni acknowledge, jusqu'à avoir vu passer une instance complète lancée après sa reprise. Alors il ne peut plus avoir renié de promesse.
Un journal qui grossit sans fin pose deux problèmes : l'espace disque et le temps de reprise. L'application prend des instantanés (snapshots) et informe le framework, qui tronque alors le journal. Un « snapshot handle » relie l'instantané à un numéro d'instance Paxos ; la prise en trois phases évite de bloquer le réplica ; un échec est sans effet tant que le framework n'est pas prévenu. Un réplica trop en retard reçoit un instantané d'un autre. Au-dessus, la primitive MultiOp (liste de tests, puis opérations si vrai, autres si faux, appliquée atomiquement) donne compare-and-swap et un style de transactions, et a permis d'ajouter la condition sur l'époque.
Sur plus de 100 années-machine : des threads en trop affamant des threads clés et provoquant des changements de master en chaîne ; un retour arrière avec un vieil instantané, par un opérateur sans documentation et sans développeur présent, a perdu 15 heures de données ; une mise à jour ratée a fait perdre environ 30 minutes ; une différence de sémantique avec Chubby (opération réussie après perte du rôle de master) a imposé les numéros d'époque ; un blocage du noyau Linux 2.4 sur le flush d'un petit fichier juste après un gros instantané, contourné en écrivant les gros fichiers par petits morceaux. Leçon : des scripts de déploiement automatisés et testés plutôt que des opérateurs.
Le papier répond à la question du prof : Paxos « simple » ne suffit pas, il faut compter avec disques, baux de lecture, changements de groupe, instantanés et surtout des tests. Les mesures montrent un débit de 1,2 à 4,4 fois celui de la base remplacée selon la charge (cinq serveurs, tests écrits).
Lire le papier Ring Paxos (sans la section 6) : réplication de machine à états, scénarios du Paxos ad hoc de la section 3, panne du coordinateur, coordinateur dédié, ordre des propositions.
On réplique un service sur plusieurs machines. Chaque réplica est une machine à états déterministe : son état ne dépend que de l'état initial et de la suite des commandes appliquées. Si tous partent du même état et appliquent les mêmes commandes dans le même ordre, ils restent identiques, et la panne de quelques réplicas n'empêche pas les autres de répondre. Cela revient à deux exigences sur la diffusion des requêtes : (i) tout réplica correct reçoit toute requête ; (ii) deux réplicas ne sont jamais en désaccord sur l'ordre. C'est la diffusion atomique (ordre total), qu'on implémente par une suite d'instances de consensus : l'instance k décide quelle commande occupe la case k du journal.
Dans cette version, les proposeurs envoient leur valeur à un coordinateur. À réception, le coordinateur augmente c-rnd et lance la phase 1a (tâche 1). Dans les schémas : ID1 coordinateur, ID2 proposeur, ID3 second proposeur, trois acceptors A1 à A3. Le papier précise que si un proposeur n'apprend pas sa valeur au bout d'un certain temps, il la repropose. Tous les chiffres viennent d'une exécution simulée de l'algorithme.
a) Sans panne. Une valeur, un tour, trois acceptors. Le coordinateur n'a besoin que d'une majorité de réponses à chaque phase ; les messages en trop sont ignorés.
ID2 et ID3 : proposeurs et learners. ID1 : coordinateur. A1, A2, A3 : acceptors. Un message ne s'affiche qu'à l'étape où il est envoyé ; l'état des acceptors (colonne de droite) n'évolue qu'à la réception.
b) Deux proposeurs, le second avant tout vote. ID3 envoie B à ID1 alors qu'aucun acceptor n'a voté : ID1 n'a même pas fini la phase 1 du tour 1. La tâche 1 recommence avec un c-rnd plus grand. Les 1B du tour 1 sont ignorés (la tâche 3 ne retient que rnd = c-rnd). Tous les v-rnd valent 0 au tour 2, donc ID1 est libre et propose la dernière valeur reçue, B. Le tour 1 est abandonné, la valeur A est écartée pour cette instance.
ID2 et ID3 : proposeurs et learners. ID1 : coordinateur. A1, A2, A3 : acceptors. Un message ne s'affiche qu'à l'étape où il est envoyé ; l'état des acceptors (colonne de droite) n'évolue qu'à la réception.
c) Deux proposeurs, un acceptor déjà entré en phase 2. A1 a voté (1, A) quand B arrive. Le tour 2 démarre. Chez A2 et A3, la phase 1a du tour 2 double les copies lentes de 2A du tour 1 : elles sont refusées, car c-rnd = 1 est inférieur à rnd = 2. Le coordinateur reçoit les 1B de A1 (v-rnd = 1, v-val = A) et de A2 : plus grand v-rnd = 1, il doit proposer A. A est décidé, B attend une autre instance.
ID2 et ID3 : proposeurs et learners. ID1 : coordinateur. A1, A2, A3 : acceptors. Un message ne s'affiche qu'à l'étape où il est envoyé ; l'état des acceptors (colonne de droite) n'évolue qu'à la réception.
Variante (même simulateur) : si les 1B reçus en premier avaient été ceux de A2 et A3, tous à v-rnd = 0, ID1 aurait proposé B et A1 aurait voté (2, B) : B est décidé. C'est correct, car A n'avait qu'un seul vote sur trois, donc n'était pas choisi. L'issue dépend du hasard des messages ; la sûreté, non.
On reprend le scénario sans panne, mais ID1 plante au pire moment : les deux votes de A1 et A2 pour A existent (valeur choisie), et la décision n'est jamais envoyée. Une élection en arrière-plan désigne ID3, seul coordinateur, qui choisit c-rnd = 2, plus grand que celui de l'ancien. ID3 n'a aucune idée du tour 1 : il fait la phase 1. A1 et A2 lui renvoient (v-rnd = 1, v-val = A). Même si les premières réponses reçues sont celles de A3 (v-rnd = 0) et de A1, il voit k = 1 et reprend A, abandonnant sa propre valeur B. Toute majorité recoupe {A1, A2}, donc aucune ne peut ignorer ce vote. Le consensus s'achève sur A.
ID2 et ID3 : proposeurs et learners. ID1 : coordinateur. A1, A2, A3 : acceptors. Un message ne s'affiche qu'à l'étape où il est envoyé ; l'état des acceptors (colonne de droite) n'évolue qu'à la réception.
La valeur peut être choisie sans être connue. Le nouveau coordinateur la retrouve parce que sa phase 1 interroge une majorité, qui recoupe celle du vote. C'est pour cela qu'il doit prendre un c-rnd plus grand que celui de l'ancien : sinon les acceptors, qui ont promis le numéro de l'ancien, ignoreraient son 1A.
Arguments tirés du papier :
Nuance : dans Paxos « classique », il n'y a pas de rôle fixe, n'importe quel proposeur lance un tour. Le papier s'en rapproche tout en posant, comme Multi-Paxos, un coordinateur en régime normal.
Les deux algorithmes appliquent la même idée : la proposition la plus récente remplace l'ancienne, mais elle doit reprendre la valeur de l'ancienne si celle-ci a pu être décidée. La différence est l'échelle de temps qui définit « plus récent ».
Algorithme hiérarchique (slides 43-44). Le rang est un tour fixé d'avance : le processus de rang r parle au tour r, donc les petits rangs parlent d'abord. Le test de réception (r < rank(self)) and (r > proposer) a deux branches. r < rank(self) : on n'adopte que les propositions des tours qui précèdent le sien. r > proposer : on n'adopte qu'une proposition d'un tour plus grand que celui de la dernière adoptée ; un message en retard d'un tour plus ancien est jeté (l'invariant de la slide : n'adopter que du plus récent). Donc, localement, c'est le plus grand r qui gagne, comme dans Paxos. Mais chaque leader rediffuse la proposition qu'il détient, et un processus ne passe au tour suivant que s'il a livré le message du tour courant ou si son leader a vraiment planté (exactitude de P). Du coup, le plus petit rang correct parle le premier et tous les tours suivants rediffusent sa valeur : c'est elle qui s'impose à la fin chez les processus corrects. Un leader de rang plus bas qui plante après avoir décidé peut avoir décidé autre chose : d'où la non-uniformité.
Paxos. Le numéro de ballot est un horodatage : un numéro plus grand est un tour plus récent, il révoque les promesses faites aux tours précédents. Aucun ordre de parole n'est fixé ; n'importe quel proposeur peut se présenter à n'importe quel moment avec un numéro plus grand. Ce qui protège une valeur déjà choisie n'est pas le calendrier, mais le recoupement de majorités : le nouveau tour reprend le v-val de plus grand v-rnd.
| Hiérarchique | Paxos | |
|---|---|---|
| Ce que le nombre représente | un tour fixé d'avance (rang) | un horodatage choisi à la volée (ballot) |
| Qui l'emporte localement | le plus grand r reçu | le plus grand numéro promis ou voté |
| Qui l'emporte globalement | la valeur du plus petit rang correct, parce qu'il parle le premier et que les suivants la recopient | la valeur du dernier tour réussi, qui recopie celle du plus grand v-rnd rencontré |
| Pourquoi une valeur décidée survit | P est exacte : on n'enjambe un tour que si son leader a livré ou a planté | une majorité de promesses recoupe toute majorité de votes |
Lequel est « meilleur » ? Chacun dans son cadre. Hiérarchique : simple et rapide sans panne (le rang 1 décide en un tour), tolère n - 1 pannes, mais exige le détecteur parfait et un ordre statique, avec un rang bas favorisé quoi qu'il arrive. Paxos : tolère l'asynchrone, les pertes et les faux soupçons, sans priorité fixe, au prix d'une majorité vivante, d'un numéro à choisir, du duel de proposeurs et d'un leader pour la vivacité. L'apparente opposition (bas contre haut) disparaît dès qu'on ramène les deux à la même question : « qui est le plus récent, et que doit-il reprendre ? ».
Q1 : pourquoi Paxos résout le consensus pour les cas de la catégorie CP.
CAP : quand le réseau se coupe en deux parties qui ne se parlent plus (P), on ne peut pas garder à la fois la cohérence (C, ici un journal linéarisable où tous les réplicas voient les mêmes décisions) et la disponibilité (A, toute requête à un nœud vivant obtient une réponse). Paxos choisit C.
Le lien avec FLP est le même : en asynchrone, on ne peut pas tout garantir. Paxos garde toujours la sûreté et ne promet la vivacité que si un leader stable et une majorité sont joignables. Même sans partition, il paie un aller-retour vers une majorité pour chaque décision (PACELC : cohérence plutôt que latence). Une base comme Dynamo prend le parti inverse, traité ailleurs.
Q1 : résumer CAP en 15 lignes. Q2 : cohérence à terme et talon d'Achille en 10 lignes. Q3 : un scénario où les horloges vectorielles servent dans DynamoDB.
Le prof a publié une copie notée A-. Ses idées sont justes pour l'essentiel ; on les reprend avec d'autres mots, plus précisément, et on signale en callout les deux endroits où la copie est discutable (Q3). Chaque question distingue le texte à rendre (court, à la taille demandée) de l'explication qui justifie.
Texte à rendre
Le théorème CAP dit qu'un système de données réparti ne peut pas garantir en même temps la Cohérence (C : toute lecture renvoie l'écriture la plus récente, comme s'il n'y avait qu'une copie, c'est la linéarisabilité), la Disponibilité (A : toute requête reçue par un nœud non défaillant obtient une réponse, pas une erreur) et la Tolérance aux Partitions (P : le système continue de fonctionner quand le réseau perd ou retarde des messages entre nœuds). Les partitions finissant toujours par arriver, P n'est pas un choix : l'alternative réelle est CP ou AP, et elle ne se pose que pendant une partition. Un système CP refuse ou bloque les requêtes qu'il ne peut pas valider : il reste juste mais devient indisponible pour une partie des clients. Un système AP répond toujours avec sa copie locale, quitte à renvoyer une valeur périmée ou à accepter des écritures concurrentes sur des copies qui divergent, réconciliées après coup (Dynamo, Cassandra). Un système « CA » n'existe que sans partition, par exemple sur un seul site. Hors partition, C et A sont compatibles ; le compromis restant (latence contre cohérence) est décrit par PACELC.
Explication. Les deux erreurs à éviter : confondre le C de CAP avec celui d'ACID (cohérence d'une transaction), et croire qu'on choisit « deux parmi trois » une fois pour toutes. Le choix se fait au moment de la partition, et peut varier selon l'opération. La preuve en trois lignes : deux réplicas partitionnés, une écriture d'un côté, une lecture de l'autre ; répondre viole C, refuser viole A. Le visualiseur de la section CAP rejoue exactement cette scène.
La copie définit C par « tous les nœuds voient des données identiques simultanément ». C'est une image acceptable mais imprécise : ce qui est exigé est la linéarisabilité (une lecture voit la dernière écriture terminée), pas l'identité instantanée de toutes les copies. Le reste de sa Q1 (P obligatoire, CP refuse, AP répond et réconcilie, Cassandra réglable par opération) est correct.
Texte à rendre
La cohérence à terme est un modèle faible : si plus aucune écriture n'a lieu sur une donnée, toutes les copies finissent par renvoyer la dernière valeur écrite. En attendant, les réplicas peuvent diverger et une lecture peut renvoyer une valeur périmée, car les mises à jour se propagent de façon asynchrone. On l'accepte pour garder la disponibilité et une faible latence. Son talon d'Achille est le conflit d'écriture : deux clients modifient la même donnée sur deux réplicas séparés, et au retour du réseau le système a deux versions sans moyen automatique de savoir laquelle est la bonne. Converger ne veut pas dire converger vers la bonne valeur. Le problème le plus dur, la résolution des conflits, quitte donc la base de données pour retomber sur le développeur : dernier écrivain gagne (simple mais perd des écritures), fusion applicative (juste mais à écrire pour chaque type de donnée) ou versions multiples présentées au client.
Explication. Les trois stratégies de la copie (LWW, fusion applicative, présenter les conflits à l'utilisateur) sont exactement celles du tableau de la section cohérence à terme. La phrase à ne pas rater : la cohérence à terme évite la coordination à l'écriture, mais n'évite pas le conflit, elle le reporte. Le papier Dynamo dit la même chose en moins de mots : l'application doit « acknowledger » l'existence possible de plusieurs versions d'un même objet.
Le scénario (le panier d'Alice, repris de la copie et corrigé). Alice a un ordinateur et un téléphone, ses requêtes sont servies par deux réplicas, R1 et R2. Chaque réplica coordonne les écritures qu'il reçoit.
| Moment | Réplica | Version | Panier | Vecteur | Relation |
|---|---|---|---|---|---|
| t=0 | R1, puis R2 | D1 | {Laptop} | [R1:1] | aucune encore |
| t=2 | R2 | D2 | {Laptop, Mouse} | [R1:1, R2:1] | D1 précède D2 |
| t=3 | R1 | D3 | {Laptop, Cable} | [R1:2] | D1 précède D3 |
| t=4 | R1 et R2 | D2 et D3 | (les deux) | [R1:1, R2:1] et [R1:2] | concurrentes |
| après fusion | R1, puis R2 | D4 | {Laptop, Cable, Mouse} | [R1:3, R2:1] | D2 et D3 précèdent D4 |
Pourquoi les horloges vectorielles sont nécessaires. Avec un simple horodatage physique (dernier écrivain gagne), l'anti-entropie garderait la version la plus récente, par exemple D3, et le Mouse d'Alice disparaîtrait sans que personne ne le sache (ou Cable, si l'horloge du téléphone avance de quelques secondes). Le visualiseur de la section Dynamo rejoue le même scénario dans les deux modes. Les vecteurs permettent de : détecter la concurrence (et ne pas la confondre avec une simple mise à jour séquentielle), conserver les deux écritures, laisser l'application les fusionner intelligemment, et garantir qu'aucune écriture n'est perdue en silence. Ce scénario illustre bien le choix AP de Dynamo : on accepte les écritures des deux côtés de la partition, puis on réconcilie.
1. Le vecteur de R2 à t=2. La copie écrit que R2 produit {Mouse} avec [R2:1], et dit que R2 « a perdu le Laptop parce qu'il travaille sur des données périmées ». C'est incohérent avec son propre texte : l'état de R2 était [R1:1] avec {Laptop} (synchronisé avant la partition), et une écriture à partir de cet état copie le contexte puis incrémente sa propre composante, donc [R1:1, R2:1] avec {Laptop, Mouse}. Un état périmé garde le Laptop ; on ne le perd qu'avec un put aveugle, sans avoir lu. Le résultat final (versions concurrentes) ne change pas, car [R2:1] et [R1:2] sont aussi concurrentes, mais la bonne démonstration est plus forte : [R1:1, R2:1] montre que R2 avait vu la première écriture de R1.
2. Le vecteur après fusion. La copie annonce une version fusionnée [R1:2, R2:1]. Ce vecteur est le contexte (le maximum des deux), pas la nouvelle version : l'écriture fusionnée est un nouvel événement, que le coordinateur date en incrémentant sa composante, d'où [R1:3, R2:1], comme l'exemple D5 du papier ([(Sx,3), (Sy,1), (Sz,1)]). Raison pratique : si R1 et R2 réconcilient chacun de leur côté en même temps et gardent [R1:2, R2:1], deux contenus potentiellement différents porteraient le même vecteur, et le conflit deviendrait indétectable.
Nuance de vocabulaire. La copie dit que « DynamoDB renvoie les deux versions en siblings ». C'est vrai du papier Dynamo (2007), pas du service DynamoDB d'AWS, qui ne rend pas de siblings et fait du dernier écrivain gagne sur les tables globales. L'énoncé parle de DynamoDB : on le lit comme « un magasin à la Dynamo ».
Lecture : section 1 de l'article Cassandra (CAP, PACELC), sections 1 à 3 de PaxosUse. Q1 Paxos et CP, Q2 stockage CA, Q3 cohérence à terme, Q4 fusion de versions.
Voir la section Paxos.
Garantir la cohérence (linéarisable) et la disponibilité, mais sans tolérer les partitions. Deux façons de le lire :
Donc, pour un système réparti sur un réseau réel, « CA » ne désigne pas une troisième famille : tolérer P, c'est avoir un comportement défini en cas de partition, et ce comportement est CP ou AP. L'étiquette CA décrit un fonctionnement sans panne réseau.
Cohérence à terme. Si plus personne n'écrit une donnée, tous les réplicas finissent par renvoyer la dernière valeur. Entre-temps, une lecture peut renvoyer une valeur périmée.
Est-ce le C de CAP ? Non. Le C de CAP est la linéarisabilité : à chaque instant, une lecture voit la dernière écriture terminée. C'est une propriété de safety. La cohérence à terme est une propriété de liveness (la convergence arrivera) qui autorise explicitement les lectures périmées. C'est même ce que l'on abandonne, par rapport au C de CAP, pour gagner en disponibilité et en latence.
Pourquoi AP par défaut. Par défaut, une lecture DynamoDB est à cohérence à terme : elle peut être servie par n'importe quel réplica, y compris un réplica coupé du leader pendant une partition. Il répond (A) avec une valeur éventuellement périmée (pas de C). La lecture à cohérence forte, activée par un paramètre, passe par le leader et peut échouer si celui-ci est injoignable : elle se comporte en CP. D'après la documentation d'AWS, les lectures à terme coûtent aussi deux fois moins d'unités de lecture, ce qui est la face « latence et coût » de PACELC. Les tables globales multi-régions poussent plus loin le choix AP : écriture locale, réplication asynchrone entre régions, conflit résolu par dernier écrivain gagne.
« DynamoDB est AP » est une simplification. Pour les écritures d'une région, DynamoDB acquitte quand une majorité de réplicas de la partition a persisté la donnée, derrière un leader : c'est plutôt un comportement CP (sources : article d'Alex DeBrie sur la cohérence à terme de DynamoDB ; la page PACELC de Wikipedia le classe PA/EC ou PC/EC selon les lectures). Le « AP par défaut » de l'énoncé se défend pour les lectures par défaut et pour les tables globales ; il ne décrit pas tout le service. Je n'ai pas vérifié ce comportement par une expérience : c'est une lecture de la documentation publique.
Pourquoi. Dynamo accepte les écritures même pendant une partition ou une panne (always writeable). Deux écritures concurrentes sur deux réplicas séparés produisent donc deux versions de l'objet, qui n'ont aucune relation d'ordre. Il faut les ramener à une seule, sinon les copies ne convergent jamais vers une valeur unique, ou convergent en perdant une écriture.
Comment.
get renvoie toutes les versions non dominées (les siblings) avec un contexte qui est le maximum de leurs horloges.put. Le coordinateur incrémente sa composante : la nouvelle version domine les deux siblings, qui sont supprimés. C'est la réconciliation sémantique.Voir le visualiseur d'horloges vectorielles pour le déroulé complet sur le panier d'Alice, avec les vecteurs recalculés à chaque étape.
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 65 questions. Tire un échantillon au hasard, correction immédiate et explication à chaque réponse.
suspects := (suspects ∪ S) \ {q}. Un accusé vivant se retire en parlant.period = TimeDelay + j · Δ, incrémenté une fois par timeout où un suspect est trouvé vivant. Défaut : période longue, heartbeats rares, détection encore plus lente.proposed[rank(p)].