THE FOLD / CO-OP / THE PUSH / THE PAXOS QUORUM
THE PAXOS QUORUM
safety was settled by arithmetic before anyone wrote a line
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The entire safety of distributed consensus rests on one fact about finite sets: any two majorities of the same set must share a member. Everything else — ballots, promises, acceptors — is scaffolding around that one intersection.
LIT verified live. with 5 acceptors there are 10 majority quorums of size 3 and 45 pairs of them; 0 pairs are disjoint and the smallest intersection is exactly 1. With 7 acceptors, 35 quorums, 595 pairs, 0 disjoint. Now take 6 acceptors and quorums of size 3 — half, not a majority: 20 quorums, 190 pairs, and 10 of them are disjoint. Two decisions can be made with nobody in common, which is what ‘split brain’ means arithmetically. Fault tolerance follows the same counting: with 5 acceptors all 10 two-failure sets still leave a quorum, and all 10 three-failure sets leave none.
LIT verified live. with 5 acceptors there are 10 majority quorums of size 3 and 45 pairs of them; 0 pairs are disjoint and the smallest intersection is exactly 1. With 7 acceptors, 35 quorums, 595 pairs, 0 disjoint. Now take 6 acceptors and quorums of size 3 — half, not a majority: 20 quorums, 190 pairs, and 10 of them are disjoint. Two decisions can be made with nobody in common, which is what ‘split brain’ means arithmetically. Fault tolerance follows the same counting: with 5 acceptors all 10 two-failure sets still leave a quorum, and all 10 three-failure sets leave none.
2 HOW IT WAS WEAVED · AI + HUMAN
Leslie Lamport’s Paxos (1998, and 1990 in draft) rests on quorum intersection; the result is his and it long predates the protocol.
AVAN (AI) checked it by exhaustion because the interesting number is the one for the wrong configuration. That majorities intersect is easy to believe; that 10 of 190 half-sized quorum pairs on 6 nodes are disjoint is the concrete form of an error people actually make when they size a cluster. The even-numbered cluster is not slightly weaker, it is unsafe at that quorum size, and this is the count that says so.
AVAN (AI) checked it by exhaustion because the interesting number is the one for the wrong configuration. That majorities intersect is easy to believe; that 10 of 190 half-sized quorum pairs on 6 nodes are disjoint is the concrete form of an error people actually make when they size a cluster. The even-numbered cluster is not slightly weaker, it is unsafe at that quorum size, and this is the count that says so.
3 ONE DIMENSION
Any two majorities share a member. Any two halves need not.
4 TWO DIMENSIONS · INTERACTIVE
Pick two quorums and look for the overlap.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that a majority quorum makes consensus safe. The inverse is that the safety is not in the protocol at all — it is a counting argument, and the protocol merely refuses to outrun it. No amount of care in the message handling can rescue a quorum size that permits disjoint sets; no carelessness in it can break one that does not. Read backwards, all the difficulty of consensus is in the liveness, where FLP guarantees no protocol can always terminate — safety was settled by arithmetic before anyone wrote a line.
LIT with 5 acceptors there are 10 majority quorums of size 3 and 45 pairs of them, 0 disjoint, smallest intersection exactly 1; with 7 acceptors, 35 quorums and 595 pairs, 0 disjoint; but take 6 acceptors with quorums of size 3 - half, not a majority - and of the 20 quorums and 190 pairs, 10 are disjoint, which is what split brain means arithmetically; fault tolerance counts the same way, since all 10 two-failure sets on 5 acceptors still leave a quorum and all 10 three-failure sets leave none
FIG Leslie Lamport's Paxos rests on quorum intersection, a result that long predates the protocol. AVAN checked it by exhaustion because the interesting number is the one for the WRONG configuration: that majorities intersect is easy to believe, but that 10 of 190 half-sized quorum pairs on 6 nodes are disjoint is the concrete form of an error people actually make when sizing a cluster. The even-numbered cluster is not slightly weaker, it is unsafe at that quorum size, and this is the count that says so.
FIG Leslie Lamport's Paxos rests on quorum intersection, a result that long predates the protocol. AVAN checked it by exhaustion because the interesting number is the one for the WRONG configuration: that majorities intersect is easy to believe, but that 10 of 190 half-sized quorum pairs on 6 nodes are disjoint is the concrete form of an error people actually make when sizing a cluster. The even-numbered cluster is not slightly weaker, it is unsafe at that quorum size, and this is the count that says so.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE PUSH · David Lee Wise (ROOT0), with AVAN