Skip to content

CONCEPT Cited by 2 sources

Intersecting quorums

Definition

Intersecting quorums is the principle that the correctness of a single-leader consensus system depends on every write-quorum intersecting every read/election-quorum on at least one node — not on either quorum individually being a majority. Majority-quorum Paxos and Raft are one special case of intersecting quorums (where both quorums are set to (N/2)+1, giving symmetric intersection); FlexPaxos (Howard, Malkhi, Spiegelman 2017) is the generalisation that lets the two quorums differ as long as the intersection property holds.

Sugu Sougoumarane states the generalisation in plain architectural English in Part 3 of the consensus-at-scale series (2 years before Part 8 cites the FlexPaxos paper by name):

"For example, if durability is achieved with 2/5 nodes, then the election algorithm needs to reach 4/5 nodes to intersect with the durability criteria. In the case of a majority quorum, both of these are 3/5. But our generalization will work for any arbitrary property." (Source: sources/2026-04-21-planetscale-consensus-algorithms-at-scale-part-3-use-cases)

The invariant

For any pair of node sets:

  • Write set W (satisfies the durability predicate) — must be reached on the Request path.
  • Read set R (checked by the Election or consistent-read path) — must cover enough nodes that at least one node in R was in every W that might hold a write.

Invariant: for every valid W and every valid R, W ∩ R ≠ ∅.

If this holds, the election or consistent-read path will always find at least one node holding every durable write — safety is preserved. If this ever fails, a write could be durable on nodes the election missed, and the system splits.

The special case: majority quorum

Paxos and Raft's choice — both W and R are majorities — is an instance of the invariant:

  • Any two majorities of N nodes must intersect (pigeonhole: (N/2+1) + (N/2+1) > N).
  • Therefore writes (majority ack) and elections (majority votes) are always mutually-intersecting.

Majority is convenient because it is symmetric (same quorum size for write and read) and self-contained (no separate predicate to maintain). But it forecloses on the flexibility the general principle allows.

Generalisation: arbitrary predicates

Under the general principle, the operator can choose any W-predicate, and the corresponding R-predicate is derived by the "reach enough nodes to intersect every W" rule:

W predicate (durability) R predicate (election reach) Use case
Any 3 of 5 Any 3 of 5 (majority) Symmetric default.
Any 2 of 5 Any 4 of 5 Faster writes; wider election. Sugu's worked example.
Any 1 of N (= N replicas) All N nodes YouTube-style: single-ack completion; election scans everything.
≥ 1 per zone across ≥ 2 zones Covers all zones Cross-zone durability; election is zone-aware.
≥ 1 per region All regions reachable Cross-region durability.
k of 6 where k ≥ 4 k of 6 where k ≥ 3 Aurora-style 4-of-6 write / 3-of-6 read, so write + read > 6.

Worked example: 2-of-5

Part 3's canonical worked example. N = 5, W = any 2 nodes, R = any 4 nodes.

  • Pigeonhole: any W (size 2) and any R (size 4) must intersect because 2 + 4 = 6 > 5.
  • The asymmetry is the point: the request path pays for 2 acks (fast); the election path pays to reach 4 nodes (slower but rare).
  • Frequency asymmetry (hundreds of requests per second vs. one election per day) makes this trade-off favourable.

Aurora: a 4-of-6 real-world instance

Aurora's storage quorum (concepts/aurora-storage-quorum) is an intersecting-quorum system in production: 6 segments per page, 4-of-6 write ack, 3-of-6 read sufficient. 4 + 3 = 7 > 6, so write and read always intersect. Distinct from majority — on 6 replicas the majority is 4, but the read quorum is 3 (sub-majority). This gets a read-path cost advantage at the same safety level. Aurora chose this shape to survive 1-AZ-loss + 1-segment-loss without data loss.

Relationship to FlexPaxos

FlexPaxos (Howard, Malkhi, Spiegelman 2017) is the academic-canonical statement of the generalisation. The FlexPaxos result: majority quorum is just a special case of intersecting quorums; any pair of write-quorum and read/leader-quorum whose sets always intersect works equally well.

Part 8 of Sugu's series cites FlexPaxos explicitly: "FlexPaxos was the first advancement that highlighted that the majority quorum is just a special case of intersecting quorums. And intersecting quorums would allow you to configure systems with more flexibility." Part 3 states the principle without academic citation — "But our generalization will work for any arbitrary property."

Why intersecting quorums matter architecturally

  1. Durability-as-plugin becomes safe. With intersecting quorums, a durability predicate can be arbitrary as long as its paired election predicate covers it. See patterns/pluggable-durability-rules.
  2. Topology elasticity. Adding nodes in an already-covered zone doesn't change the quorum intersection — the same predicates continue to hold.
  3. Non-majority shapes become viable in production. YouTube's single-ack completion with wide election scan is correct as long as election reaches "all possible nodes that could have ack'd." Aurora's 4-of-6 write + 3-of-6 read is correct by the same principle.

Limits — the "reasonable requirements" constraint

Sugu's caveat from Part 8: "Of course, the requirements have to be reasonable." A durability predicate that cannot be covered by any election predicate (e.g., "write to A and B" + "read from C and D" with {A,B} ∩ {C,D} = ∅) is unsatisfiable under intersecting quorums — no safe consensus protocol exists for such a configuration. The plugin API (in Vitess: VTOrc's durability plugin) is responsible for rejecting unsatisfiable rules at configuration time.

Seen in

Last updated · 550 distilled / 1,221 read