Closing Phase 7 with four narrower, more specialized variants that each address one specific weakness this phase has surfaced along the way, plus a full comparison across every algorithm covered since 7.1. Matchmaker Paxos tackles reconfiguration's specific safety subtleties head-on. PigPaxos attacks Multi-Paxos's own leader-fan-out bottleneck (the same class of problem article 6.5 solved for BFT) using a gossip-relay pattern. BPaxos applies Narwhal's data/ordering separation (article 6.5) back to the crash-fault setting. Rabia takes the opposite approach from nearly everything else in this phase — simplifying via randomization instead of adding mechanism. Together, these round out the picture before this series turns to production systems in Phase 8.
Matchmaker Paxos: reconfiguration's subtle safety trap
OmniPaxos (7.7) treated reconfiguration as important enough to design in from the start; Matchmaker Paxos (Whittaker, Ailijiang, and colleagues) goes further and specifically formalizes a subtle safety hazard in reconfiguration that's easy to get wrong: when cluster membership changes while a Phase 1 (leader election, article 5.2) is in flight, a naive implementation can end up with acceptors from the old configuration and acceptors from the new configuration disagreeing about which quorum is authoritative — a scenario that can silently reintroduce article 1.2's split-brain risk specifically at the moment of membership change, even in an otherwise-correct implementation. Matchmaker Paxos introduces a dedicated "matchmaker" role that mediates configuration changes explicitly, ensuring the old and new configurations' quorums are properly reconciled before a reconfiguration is considered complete — a precise, formal treatment of exactly the hazard OmniPaxos's "first-class reconfiguration" design goal (7.7) was informally motivated by.
PigPaxos: fixing the leader's fan-out bottleneck
Recall article 6.5's Narwhal/Bullshark motivation, restated for the crash-fault setting: even in Multi-Paxos's efficient fast path (article 5.3), the leader still personally sends every AppendEntries-equivalent message to every follower directly — a fan-out cost that scales linearly with cluster size and can become a real bottleneck at larger deployments, structurally the same shape of problem article 6.5 named for BFT protocols, just in the crash-fault-tolerant setting. PigPaxos's fix borrows a pattern from peer-to-peer gossip protocols: instead of the leader sending directly to every follower, it sends to a small, random relay subset, which then re-broadcasts to the rest — reducing the leader's own direct fan-out load while still propagating updates to the full cluster, trading a small amount of added latency (one extra relay hop) for meaningfully reduced leader-side bandwidth pressure at scale.
BPaxos: separating ordering from broadcast, for crash faults
BPaxos applies a structurally similar idea to article 6.5's Narwhal/Bullshark separation, but for the crash-fault-tolerant setting this whole phase has otherwise stayed within (rather than 6.5's Byzantine setting): decouple the mechanism that disseminates command data across replicas from the separate mechanism that decides their final order, letting each be optimized and scaled independently — directly mirroring the architectural lesson article 6.5 introduced, demonstrating that "separate data movement from ordering" is a genuinely reusable systems pattern that transfers across the crash-fault/Byzantine boundary, not a Byzantine-specific trick.
Fig 1 — BPaxos is direct evidence that architectural lessons transfer across the crash-fault/Byzantine boundary this series has otherwise kept separate.
Rabia: simplifying via randomization
Rabia (Pan, Ren, and colleagues) takes a genuinely different direction from every other variant in this phase — instead of adding mechanism to optimize a specific metric (latency, throughput, cost), it uses randomization to remove mechanism, aiming for a simpler protocol overall. Building on article 2.5's randomization escape hatch (originally introduced there as one of FLP's ways around the impossibility result), Rabia uses a randomized consensus core to avoid some of the more intricate corner-case handling that deterministic protocols like Multi-Paxos and Raft need (particularly around the dueling-proposer/split-vote liveness edge cases discussed in articles 4.2 and 5.2) — trading a small amount of expected-case overhead (randomized protocols typically need a few rounds in expectation, rather than a deterministic worst-case bound) for meaningfully simpler implementation and easier-to-reason-about correctness.
Phase 7 closing comparison
| Variant | Assumption relaxed / mechanism used | Primary benefit |
|---|---|---|
| EPaxos (7.1) | Fixed leader, total order | Locality, per-command parallelism |
| Flexible Paxos (7.2) | Symmetric majority quorums | Tunable election/replication cost trade-off |
| Fast/Generalized Paxos (7.3) | Leader routing / total order (Lamport's own precursors) | Latency; direct ancestors of EPaxos |
| Cheap/Compartmentalized Paxos (7.4) | Uniform node cost / monolithic leader role | Steady-state cost; independent scaling |
| Atlas (7.5) | EPaxos's conservative fast-quorum size | Fast-quorum availability at scale |
| Caesar (7.6) | EPaxos's reactive-only conflict detection | Lower slow-path frequency under contention |
| OmniPaxos (7.7) | Monolithic election / bolted-on reconfiguration | Production engineering, operational safety |
| Matchmaker / PigPaxos / BPaxos / Rabia (7.8) | Naive reconfiguration / leader fan-out / bundled ordering / deterministic complexity | Targeted fixes for specific, narrow weaknesses |
Closing Phase 7, opening Phase 8
Phase 7 has been the most research-dense phase in this series — eight papers, each addressing a specific, well-motivated gap in Multi-Paxos's original bundled design. Phase 8 now shifts entirely from algorithms to systems: how etcd, Apache ZooKeeper, Consul, Kafka's KRaft, and Kubernetes actually deploy the Raft and Zab mechanisms this series built in Phase 5, the real operational trade-offs those systems make, and how Jepsen's testing methodology catches the gap between "the algorithm is proven correct" and "this specific implementation is actually correct" — the same gap OmniPaxos's engineering-first philosophy (7.7) was implicitly responding to.
FAQ
Which of the Phase 7 variants would you actually pick for a new production system today?
Genuinely depends on your specific constraints, consistent with this whole phase's honest-trade-off framing — most new systems in practice reach for well-engineered Multi-Paxos or Raft implementations (Phase 8's subject) rather than any of the more specialized research variants, precisely because the specialized variants each trade general-purpose simplicity for a narrow, specific benefit that only matters if you actually have that specific bottleneck.
Is Rabia's randomization approach compatible with any of the other Phase 7 ideas?
In principle, randomization (Rabia's core idea) and quorum-shape flexibility (Flexible Paxos, 7.2) or leaderless ordering (EPaxos, 7.1) address different axes and could in theory be combined, though none of the papers covered in this phase explicitly do so — a plausible direction for future research building on this phase's material.
Does BPaxos being crash-fault-tolerant mean it's automatically less capable than Narwhal/Bullshark?
Not automatically less capable — it operates under a genuinely different, weaker threat model (crash-only, article 1.1) that most non-blockchain production systems actually have, meaning BPaxos doesn't need the extra safety machinery (3f+1, cryptographic signatures, article 6.1-6.2) that Narwhal/Bullshark's Byzantine setting requires, which can make it a lighter-weight, more efficient choice specifically for deployments that don't need Byzantine tolerance in the first place.
Takeaways
- Matchmaker Paxos formalizes and fixes a subtle reconfiguration safety hazard — old/new configuration quorums disagreeing during a live membership change.
- PigPaxos fixes Multi-Paxos's leader fan-out bottleneck with a gossip-relay pattern, the crash-fault analog of article 6.5's BFT bottleneck.
- BPaxos ports Narwhal/Bullshark's data/ordering separation (6.5) to the crash-fault setting — proof the architectural pattern transfers across fault models.
- Rabia is this phase's outlier: simplifies via randomization (article 2.5's escape hatch) rather than adding mechanism to optimize a metric.
- The whole phase compresses to one insight: every variant relaxes one or two of Multi-Paxos's four bundled assumptions (fixed leader, total order, symmetric quorums, uniform cost) while the majority-overlap safety core (article 3.3) never changes.
- Phase 7 is now complete — Phase 8 shifts from algorithms to real production systems (etcd, ZooKeeper, Consul, Kafka, Kubernetes, Jepsen).
References & further reading
- Whittaker et al. — Matchmaker Paxos: A Reconfigurable Consensus Protocol (2020) — the primary Matchmaker Paxos reference.
- Charapko, Ailijiang & Demirbas — PigPaxos: Devouring the Communication Bottlenecks in Distributed Consensus (2021) — the primary PigPaxos reference.
- Whittaker et al. — Bipartisan Paxos (BPaxos) — the primary BPaxos reference.
- Pan, Wang, Ren et al. — Rabia: Simplifying State-Machine Replication Through Randomization (2021) — the primary Rabia reference.
- cvam.sight — Consensus Algorithms series hub — Phase 8 (Consensus in Production) picks up next.