Why Majority Quorums Intersect and What the Intersection Buys

A register replicated across five machines can survive two failures, but only if the protocol is careful about which machines it talks to for each operation. The careless version writes to all five and reads from all five. That works and is also the slowest possible design: every operation pays for the slowest of five responses, and any single unreachable machine stops progress entirely. The alternative is to contact a subset, and the entire theory of quorum systems is about choosing that subset so that information written by one operation cannot be missed by a later one.

The overlap condition

Take a register holding a single value, replicated to n nodes. A write is acknowledged once W nodes have stored the new value. A read collects values from R nodes and returns the one with the highest version number it saw. For the read to observe the most recent acknowledged write, the two sets must share at least one node: the writer’s newest value lives on some node in its write set, and if every node in the read set were outside that write set, the reader would see only older values.

Two sets drawn from the same n elements are guaranteed to intersect when R + W > n. The argument is a counting one. If the sets were disjoint, their union would contain R + W distinct nodes, which cannot exceed n. So a violation of the inequality is exactly the condition under which disjointness becomes possible, and the inequality is not merely sufficient but tight: with R + W = n a partition into two disjoint groups of those sizes always exists.

The same inequality, applied with W on both sides, gives 2W > n, which is why a write must reach a strict majority for successive writes to be ordered against each other. Without it, two writes could land on disjoint sets and the register would have two conflicting “latest” values with no rule to pick between them. This is the requirement that turns a set of quorums into a quorum system rather than a pair of read and write sets that merely happen to overlap. A scheme where any row intersects any column but two columns are disjoint satisfies the first property and fails the second.

Majorities satisfy both because any two sets larger than n/2 must share an element. That single fact explains most of the structure of practical consensus protocols: majorities of the same fixed membership intersect pairwise, so no additional coordination is needed to make a read meet a write or a write meet a write.

Counting the minimum quorum

The smallest majority is floor(n/2) + 1. For n = 3 that is 2, for n = 5 it is 3, for n = 7 it is 4. The number of tolerated crash failures is f = floor((n-1)/2), so n = 2f + 1 is the minimum configuration that tolerates f failures: three nodes tolerate one, five tolerate two, seven tolerate three. The relationship is not a coincidence of the formula; with n = 2f a majority is f + 1 nodes and the remaining f failures leave exactly f live nodes, one short of a quorum.

The arithmetic has an availability consequence that is easy to state and hard to internalize. A five-node cluster tolerates two failures, but it also stops serving when three nodes are unreachable, even if those three are reachable from each other. The minority side of a partition can hold three of five nodes and still be unable to commit anything, because it cannot reach a majority of the configured membership. Quorum counting is always against the configuration, never against the set of nodes currently believed to be alive; the distinction is what makes membership changes dangerous.

There is a second counting subtlety that matters more in practice than in proofs. A quorum acknowledgement means a node has the value in memory or in its page cache, not that it has reached stable storage. A protocol that acknowledges after W in-memory writes can lose an acknowledged write if all W nodes crash or lose power simultaneously. Durability requires the acknowledgement to follow an fsync or equivalent, which changes the latency of the write from a network round trip into a network round trip plus a disk flush on every node in the quorum. The counting argument is unchanged; the cost per counted node is not.

Asymmetric quorums and what they trade

Nothing in the inequality requires R and W to be equal. With n = 5, the pair (R=1, W=5) is legal, as is (R=5, W=1), as is (R=2, W=4). The constraint is only the sum. Choosing among these pairs is choosing which operation is cheap and which is fragile.

Setting W = n and R = 1 makes reads a single-node operation, but every write now requires every node to be up, so a single failure blocks all writes. Setting W = 1 and R = n inverts it: writes are trivially available and reads require the full cluster. Neither extreme is useful for a system that must survive failures in both directions, which is why symmetric majorities dominate. Where asymmetric splits do appear, they appear as a deliberate choice about read latency under the assumption that reads vastly outnumber writes and that write availability can be sacrificed.

Latency, not just availability, follows the quorum size. A write that requires W acknowledgements completes when the W-th fastest node responds, so a larger quorum pulls in slower nodes and raises the tail. On a wide-area deployment where the slowest replica is an order of magnitude slower than the median, the difference between W = 2 and W = 3 in a five-node cluster is the difference between the second-fastest and third-fastest response, which can be tens of milliseconds. Consensus protocols inherit this property directly; the election and replication machinery is built on top of exactly this acknowledgement counting.

The deeper point about asymmetric quorums is that the intersection requirement is per phase, not global. Flexible Paxos makes this explicit: phase one and phase two of the protocol each need a quorum, and the only requirement is that every phase-one quorum intersects every phase-two quorum. A protocol can therefore use a large phase-one quorum and a small phase-two quorum, provided the two sizes still sum to more than n. The phase-two quorum is the one on the critical path of every decision, so shrinking it buys latency while the phase-one quorum, contacted only when a leader is establishing itself, absorbs the availability cost. This is not a loophole in the intersection argument; it is the argument applied to the sets that actually need to overlap.

Where quorum arithmetic stops being enough

Intersection guarantees that a reader meets the last writer. It does not guarantee that the reader can tell which value is newer, and it does not guarantee that the nodes agree on what the current attempt is.

The first gap is ordering information. Two values need a comparable version, whether a term number, a log index, or a timestamp with a tiebreak. If two writes carry version 7 because they were issued concurrently by different coordinators, intersection delivers both to the reader and the reader has no basis for a choice. Consensus protocols resolve this by making the version a total order that only one coordinator can extend at a time; Paxos does it with proposal numbers and the acceptor’s promise, Raft with terms and the single leader per term.

The second gap is quorum membership itself. A node that believes it is in configuration C1 counts acknowledgements against C1; a node in C2 counts against C2. If C1 and C2 are different sets of machines, both sides can assemble what looks like a majority and both can commit. No amount of intersection arithmetic within a single configuration prevents this, because the two quorums are not drawn from the same universe. This is the reason reconfiguration protocols are constrained to move through intermediate states where the old and new quorums are both required, and it is why “just update the config file” is a correctness bug rather than an operational shortcut.

The third gap is that intersection is a statement about sets, not about time. A node can be in the read set and still return a stale value if it has not yet applied the write it holds, for example because the write was appended to its log but not committed to its state machine. Protocols separate the durable log from the applied state for exactly this reason, and reads have to be ordered behind the commit index rather than merely served from whatever the local state machine contains.

Quorums are not majorities of the living

The most common misreading of quorum systems is that a quorum is a majority of the nodes that are currently reachable. It is not. A quorum is a majority of the nodes named in the current configuration, and reachability only determines whether that quorum can be assembled. A cluster of five where three nodes have been decommissioned but not removed from the configuration still needs three acknowledgements from the remaining two, which is impossible; the cluster is down even though every live node is healthy.

This is why configuration membership is itself a consensus problem, and why the practical advice is to remove a failed node before adding its replacement rather than running with a configuration that overstates the cluster. It is also why witness or tiebreaker nodes exist: a lightweight participant that stores no data but counts toward the majority can restore quorum arithmetic in a two-node primary/standby pair, at the cost of a third failure domain that must be reachable for writes.

The arithmetic is small enough to check by hand, which is its main virtue. Before trusting any replicated design, the useful exercise is to write down n, the quorum sizes for each operation, and then try to construct two disjoint sets that the protocol would accept. When such a construction exists, the protocol has a bug that no amount of testing under benign conditions will reveal.