Paxos consensus

Comment N processus s'accordent durablement sur une valeur unique malgré pannes et délais — l'algorithme qui a tenu Google Chubby pendant vingt ans.

Problème

Plusieurs processus distribués doivent décider d'une valeur unique parmi un ensemble proposé (qui est le leader courant ? quelle est la prochaine entrée du journal ? quel est le master schedule ?). Les processus peuvent crasher et redémarrer ; les messages peuvent être perdus, dupliqués ou retardés mais non corrompus. Le théorème FLP (Fischer-Lynch-Paterson 1985) prouve qu'aucun consensus déterministe n'est possible dans un système purement asynchrone avec une seule panne. Paxos contourne cet obstacle en garantissant la sûreté (safety) en toutes circonstances et la vivacité (liveness) dès qu'une fenêtre de synchronie suffisante apparaît.

Forces

• FLP impossibility — le consensus parfait est impossible en asynchrone pur ; Paxos accepte de boucler en cas de duels indéfinis de leaders.
• Sûreté inconditionnelle — aucune valeur incorrecte n'est jamais décidée, même en cas de pannes ou de partitions.
• Complexité conceptuelle élevée — Lamport lui-même reconnaît que l'article original (Part-Time Parliament) a été incompris pendant huit ans.
• Tolérance aux pannes : Paxos tolère f pannes parmi 2f+1 nœuds (quorum N/2+1).
• Performances : multi-Paxos (variante optimisée) amortit l'overhead à 1 round-trip par décision après stabilisation.

Solution

Paxos repose sur trois rôles : proposers (qui proposent des valeurs), acceptors (qui votent), learners (qui apprennent la décision). Chaque proposition utilise un numéro de proposition unique et croissant (round number). Phase 1a (prepare) : le proposer envoie prepare(n) à un quorum d'acceptors. Phase 1b (promise) : chaque acceptor promet de ne plus accepter aucun n' < n, et retourne la valeur acceptée la plus récente. Phase 2a (accept) : le proposer envoie accept(n, v) où v est sa valeur (ou la valeur retournée la plus récente). Phase 2b (accepted) : chaque acceptor accepte si aucun n' supérieur n'a été promis. Quand une valeur est acceptée par un quorum, elle est chosen, et tous les futurs proposers la retourneront.

Structure

Proposer        Acceptors (A, B, C)         Learners
   │                  │                         │
   │ prepare(5) ───►  │                         │
   │ ◄── promise(5,_) │                         │
   │                  │                         │
   │ accept(5, "X") ► │                         │
   │ ◄── accepted(5,X)│                         │
   │                  │                         │
   │ if majority:     │                         │
   │ value "X" chosen ──────────────────────►   │
   │                                            │

Concurrent duel:
  P1 prepare(5) → some promises
  P2 prepare(7) → preempts P1 (higher n)
  P1 accept(5, "X") → rejected (acceptors promised 7)
  P1 retries with prepare(9) → ...
  → "dueling proposers" livelock prevented by leader election

Multi-Paxos optimisation:
  Elect distinguished proposer (leader)
  Skip phase 1 for subsequent rounds → 1 round-trip per decision

Implémentation EDI

Comme pour Raft, on consomme Paxos plutôt qu'on ne l'écrit. Apache Cassandra utilise Paxos pour ses Lightweight Transactions (LWT) — utile si un hub EDI veut une garantie de compare-and-set sur un statut partenaire. Google Spanner combine Paxos et TrueTime pour ses transactions multi-régions ; un hub EDI mondial qui s'appuie sur Spanner hérite des garanties externalisées. Apache ZooKeeper utilise ZAB (variante de Paxos) pour son atomic broadcast. Comprendre Paxos permet de calibrer la latence inter-DC nécessaire au consensus de quorum — une décision à 3 régions sur 3 continents traite en pratique 80-200 ms par round-trip, ce qui plafonne le throughput consensus à 5-12 décisions/seconde par leader sans pipelining.

Anti-patterns

• Implémenter Paxos soi-même — les bugs subtils sont innombrables ; même Lamport recommande d'utiliser une implémentation éprouvée.
• Ignorer la corruption des messages — Paxos suppose des messages non corrompus ; sans MAC ou TLS, un attaquant peut briser le consensus.
• Quorum à 2 nœuds — toute panne paralyse l'écriture ; toujours 3, 5 ou 7.
• Confondre Paxos basique et multi-Paxos — l'optimisation leader-distingué change radicalement les performances.
• Croire que Paxos résout les pannes byzantines — il faut BFT-Paxos ou PBFT pour cela.

Patterns liés

• Raft — reformulation compréhensible de Paxos.
• Byzantine Fault Tolerance — extension à des nœuds potentiellement malveillants.
• Leader Election — multi-Paxos en dépend.
• Partition Tolerance (CAP) — Paxos choisit C+P, pas A.

Sources

• Lamport L. — The Part-Time Parliament, ACM Transactions on Computer Systems, 1998 (rédigé 1989). lamport.azurewebsites.net
• Lamport L. — Paxos Made Simple, 2001, version pédagogique. paxos-simple.pdf
• Chandra T., Griesemer R., Redstone J. — Paxos Made Live: An Engineering Perspective, Google, PODC 2007. Retour d'expérience de Chubby. paxos made live
• Van Renesse R., Altinbuken D. — Paxos Made Moderately Complex, ACM Computing Surveys, 2015.
• Tanenbaum & van Steen — Distributed Systems, 3rd ed., 2017, chap. 6.