Quorums

Why is the agreement of a bare majority enough to call something decided?

Five machines hold copies of the same data. A write arrives, three of them acknowledge it, and the system reports success — even though two machines have not seen it and might never.

That looks like a strange definition of "written". Two of the five could serve a stale answer a moment later. So why is three out of five treated as decided, rather than as a majority opinion that happens to be popular? And why three specifically — what would break at two?

Begin with the alternative. Require all five, and every write is only as available as the least available machine: one node down, one node slow, one node behind a partition, and nothing can be written at all. Availability collapses as you add replicas, which is the opposite of what replicating was for. So waiting for everyone is not conservatism; it is a design that gets worse the more redundancy you buy.

Now go to the other extreme. Accept a write when any single node has it. Fast and available — but now a later read that asks a different single node may see nothing, and two writers talking to two different nodes can both believe they succeeded. Nothing ties the two operations together.

So the interesting question is what property we actually need in between. Say it precisely: a read must be guaranteed to encounter at least one node that saw the write. Not all of them — one is enough, provided you can tell which value is newer.

And now the arithmetic falls out. If a write is acknowledged by W nodes out of N, and a read consults R nodes out of N, when must the two sets share a member? Exactly when W plus R is greater than N. Below that, the two sets can be disjoint — there is room in N for them to avoid each other entirely. Above it, they cannot: by the pigeonhole principle, two sets whose sizes sum to more than the total must overlap in at least one element.

That is the entire mechanism, and it is worth pausing on how modest it is. No voting, no persuasion, no wisdom of crowds — a quorum is a counting argument about set intersection. Majority is simply the symmetric solution: if any two quorums must overlap without knowing in advance which is a read and which a write, each has to exceed half, so the smallest such size for five is three.

Now ask the second thing majority buys, which is different from the first. Can two conflicting writes both be accepted? Each would need a majority, and two majorities of the same five must share at least one node — and that node will not accept both. So the same overlap that guarantees a read sees the write also guarantees that only one of two competing decisions can be made. One property, two consequences: nothing decided is lost, and nothing is decided twice.

That also explains the odd cluster sizes. Five nodes tolerate two failures; six nodes still tolerate only two, because the majority is now four. The sixth machine adds cost, adds a participant that can fail, and adds nothing to fault tolerance — which is why membership counts in these systems are odd.

One clarification about the overlap, since it is easy to overstate. Intersection guarantees that the reader touches a node holding the newer value. It does not by itself tell the reader which of the returned values is newer — that requires versioning, whether a term number, a sequence number, or a vector clock. Overlap makes the right answer present in the responses; ordering metadata is what identifies it.

Three refinements.

First, W and R are a dial, not a constant. The requirement is only that they sum to more than N, so a read-heavy store can set W to N and R to one, making reads a single fast hop at the cost of writes needing everyone. Dynamo-style systems expose exactly this trade, and majority-majority is the balanced point rather than the only legal one.

Second, and most often misunderstood: overlapping quorums do not by themselves give strong consistency. A read that consults enough nodes will encounter the newest acknowledged value, but if the system merely returns what it sees, a client can still read a newer value and then an older one afterwards. Linearizability needs more — the reader must write back what it found, or route through a leader that has confirmed its own currency with a round of the same counting. Majority overlap is a component of consistency, not the whole of it.

Third, the whole argument rests on an assumption worth naming: that nodes fail by stopping, not by lying. Majority counting protects against a node being absent. It does not protect against a node reporting a value it never stored, because the counting has no way to weigh honesty. Tolerating that case requires more nodes and a different argument — Byzantine agreement needs more than two-thirds honest participants rather than a bare majority, which is why the ordinary quorum reasoning above stops applying the moment lying is on the table.

• Raft, and how leader election and log replication both reduce to the same overlap argument.
• Sloppy quorums and hinted handoff, where availability is bought by relaxing the intersection.
• Byzantine fault tolerance, and why the threshold moves from one half to two thirds.

Every term the collection defines is gathered in the glossary.