Classic Paxos requires that any two quorums intersect in at least one node. The standard way to guarantee this is majority quorums: with 5 nodes, both phase 1 (prepare) and phase 2 (accept) need 3 nodes. Flexible Paxos (Howard, Malkhi, Spiegelman, 2016) proves this is stricter than necessary. The real safety requirement is that every phase 1 quorum intersects every phase 2 quorum — phase 1 quorums don't need to intersect each other, and phase 2 quorums don't need to intersect each other.

The rule of thumb: if you have N nodes and choose phase 1 quorum size Q1 and phase 2 quorum size Q2, safety holds as long as Q1 + Q2 > N. Majority Paxos is just one point on that line (Q1 = Q2 = ⌈(N+1)/2⌉).

Why this matters: in steady-state Multi-Paxos, phase 1 (leader election) happens rarely — only when a leader dies. Phase 2 (replicating each command) happens on every write. So shrinking Q2 at the cost of a larger Q1 is a great trade.

Concrete example. You run a 5-node Paxos cluster across three availability zones. Under classic majority, every write waits for 3 acks — meaning at least one cross-AZ round trip is almost always on the critical path. With Flexible Paxos, set Q2 = 2 and Q1 = 4. Now steady-state writes need only 2 acks — the leader plus its nearest replica, often in the same AZ. Cross-AZ p99 latency drops from ~8ms to ~2ms. The cost: leader elections need 4 nodes instead of 3, so if two nodes are down you can't elect a new leader. But leader elections happen once an hour at most; writes happen 10,000 times a second.

You can push this further with grid quorums: arrange N nodes in a √N × √N grid, make phase 1 quorums pick any full row, phase 2 quorums pick any full column. Every row intersects every column in exactly one node. For N=16, Q1 = Q2 = 4 instead of 9 — smaller than majority for both phases.

The catch: availability degrades asymmetrically. With Q2 = 2 out of 5, you tolerate 3 replica failures for writes — but only 1 failure for leader election (need 4). Model your failure scenarios: if a whole AZ can go down, make sure Q1 still fits in the remaining AZs.