Article 3.3 established, and this whole series has assumed since, that Paxos's Phase 1 and Phase 2 quorums are both simple majorities. Howard, Malkhi, and Spiegelman's 2016 Flexible Paxos paper proves something genuinely surprising, discovered nearly three decades after Paxos itself: that assumption was stronger than necessary. The actual safety requirement is only that Phase 1 quorums intersect Phase 2 quorums — not that either quorum is, by itself, a majority of all nodes. This one relaxation opens a design space Phase 5 never explored, and this article walks through the proof and the flexible quorum configurations it unlocks.
Revisiting article 5.2's safety proof — what was actually load-bearing
Recall article 5.2's worked example precisely: proposer P1's Phase 1 quorum and proposer P2's Phase 2 quorum needed to overlap — that overlap was the physical mechanism carrying "X was already accepted" forward, forcing P2 onto the same value. Notice what the proof actually used: it never required P1's quorum and P2's quorum to both individually be majorities of the full node set — it only required that whichever quorum P1 used for Phase 1 and whichever quorum P2 used for Phase 2 share at least one node. Phase 5's presentation used simple majorities for both because that's the easiest way to guarantee that overlap for arbitrary quorum choices — but it's not the only way to guarantee it.
Why this matters: decoupling election cost from replication cost
The practical payoff: Phase 1 (leader election, article 4.2/5.5) and Phase 2 (log replication, article 5.6) happen at very different frequencies in a real Multi-Paxos deployment — Phase 1 runs rarely (only on leader change), while Phase 2 runs constantly (every single write). Flexible Paxos lets you size these two quorums asymmetrically, trading off their respective costs independently rather than being locked into identical majority-sized quorums for both.
A concrete example: with 5 nodes, instead of requiring 3 nodes for both Phase 1 and Phase 2 (the standard majority approach), you could require only 2 nodes for Phase 2 (cheaper per-write replication — the frequent, latency-sensitive path) as long as Phase 1 requires enough nodes to guarantee intersection with any possible 2-node Phase 2 quorum — which, by a simple pigeonhole argument, means Phase 1 needs at least 4 of the 5 nodes (since a Phase 1 quorum of only 3 could potentially avoid overlapping some specific 2-node Phase 2 quorum drawn from the remaining nodes). You've made the frequent operation (Phase 2 writes) cheaper, at the cost of making the rare operation (Phase 1 elections) more expensive — a genuine, tunable trade-off Phase 5's fixed-majority approach never exposed as a knob at all.
Fig 1 — The intersection guarantee holds via simple counting (|Q1| + |Q2| > N), regardless of whether Q1 and Q2 are equal-sized.
Grid quorums and other configurations
Flexible Paxos's paper (and follow-up work) explores configurations beyond simple asymmetric sizing — arranging nodes in a logical grid, where a Phase 1 quorum is any full row and a Phase 2 quorum is any full column (or similar structured arrangements), guaranteeing intersection by the grid's geometry itself (any row and any column of a grid always share exactly one cell) rather than by counting alone. These structured quorum layouts can be tuned for specific deployment topologies — for instance, weighting quorum membership toward nodes in a primary datacenter for the frequent Phase 2 path, while requiring broader cross-datacenter participation for the rarer Phase 1 path — a genuinely useful knob for the geo-distributed deployments Phase 9 covers in depth.
FAQ
Does Flexible Paxos change anything about Raft, or only Paxos specifically?
The theorem is stated in terms of Paxos's explicit Phase 1/Phase 2 structure, but the underlying insight (only intersection matters, not majority-ness) applies to the equivalent quorum roles in Raft (election quorum vs. log-replication quorum) and VR (view-change quorum vs. normal-operation quorum) as well — it's a general property of the majority-overlap mechanism this whole series has traced, not a Paxos-specific quirk.
Is there ever a reason NOT to use flexible quorums, given the cost-tuning flexibility?
Yes — asymmetric quorums mean the system's fault-tolerance characteristics differ depending on which quorum type is involved (a deployment optimized for cheap Phase 2 writes has a Phase 1 quorum that tolerates fewer simultaneous node failures during an election). This is a genuine trade-off requiring careful analysis of your specific failure and workload assumptions, not a strictly-dominant improvement over standard majority quorums.
Does making Phase 2 quorums smaller than a majority weaken the "no split-brain" guarantee from article 1.2?
No, as long as the Q1∩Q2 intersection property is correctly maintained for every possible quorum pair — the split-brain prevention (article 1.2, 3.3) comes specifically from that intersection property, not from either quorum individually being a numerical majority. Flexible Paxos's whole point is that the intersection property can be satisfied by configurations other than "both are majorities."
Does EPaxos (7.1) use flexible quorums too?
EPaxos's fast quorum (article 7.1) is itself an example of a non-standard quorum size (larger than a simple majority, for different reasons — reliable conflict detection rather than Phase 1/Phase 2 cost trade-offs), showing this general theme of "quorum sizing is a genuine design space, not a fixed constant" recurring across multiple threads of modern Paxos research, each motivated by a different specific goal.
Takeaways
- Article 5.2's actual safety requirement was always just Phase 1 quorum ∩ Phase 2 quorum ≠ ∅ — Phase 5's "both are majorities" convention was sufficient but, Howard/Malkhi/Spiegelman prove, stronger than necessary.
- This unlocks asymmetric quorum sizing — since Phase 1 (rare, election) and Phase 2 (frequent, replication) have very different cost profiles, you can size them independently as long as intersection is guaranteed by counting (|Q1|+|Q2| > N) or structured layout (grid quorums).
- A concrete example: shrinking the frequent Phase 2 quorum below a majority, compensated by growing the rare Phase 1 quorum — cheaper writes, more expensive (but infrequent) leader elections.
- Grid quorums and other structured layouts extend this idea geometrically, useful for tuning geo-distributed deployments (Phase 9) toward the access patterns that matter most.
- The underlying insight — only intersection matters, not majority-ness — generalizes beyond Paxos specifically to any algorithm relying on the same overlap mechanism (article 3.3), including Raft and VR's equivalent quorum roles.
References & further reading
- Howard, Malkhi & Spiegelman — Flexible Paxos: Quorum Intersection Revisited (2016) — the primary source and proof.
- cvam.sight — Consensus 3.3: Quorums and Majority Voting — the overlap mechanism this article shows was always the true load-bearing requirement.
- cvam.sight — Consensus 5.2: Single-Decree Paxos — the worked example whose safety argument only ever needed intersection, not majority.