Majority
A system that waited for every machine to acknowledge a write would stop the first time any machine did. A majority leaves room for failures: any later majority of the same cluster shares at least one machine with the group that acknowledged. Some machines may have never heard of the write, but no later majority can avoid everyone who did. That is what this page checks by enumerating every subset. Preserving the write requires additional protocol rules; overlapping sets alone do not establish permanence.
New to quorums? Start here
Waiting for every machine to confirm a write means one slow machine stops everything, and one dead machine stops it forever. So the rule is a majority instead.
The reason a majority and not any subset: any two majorities of the same set must share at least one member. So a later reader asking a majority is guaranteed to reach somebody who saw the write, whatever the two groups were. What that member then does with it is the protocol's business, not the set theory's.
A message that takes time and may not arrive
A message takes time to travel from one computer to another. Sending it does not establish that it arrived, and receiving one message does not establish that an earlier one arrived first.
Messages may be delayed, lost, duplicated or reordered. A protocol defines how the participants respond to those possibilities. Some machines here model only one of them; the page says which assumptions its result needs.
The machine for this idea on its own is Packet Switching, if you would rather press it than read about it.
Three of five is enough, and the reason is a fact about sets
1 Five machines, a write, and the one that takes it
A cluster, and a write that arrives at one of them.
5
0
2 A majority acknowledges the write
A majority acknowledges, and the machines that are down still know nothing about it. What the intersection guarantees is that any later majority contains somebody who saw this; making that into permanence takes rules this page does not model, about terms, leaders and which value a node may accept next.
- a majority is
- 3 of 5
- acknowledged by
- 5 machine(s) still up
- the write is
- reachable from any later majority
The write is acknowledged with 0 machine(s) that have never heard of it, and any majority that forms next has to contain one of the 5 that did. That is what the counting buys: a later majority cannot miss this write. Whether it can still be undone is a question about the protocol on top, which this page does not model.
3 Any later majority shares a machine with the acknowledging majority
Why the groups overlap. Every majority of this cluster, against every other, asking whether they share a machine. Not a sample — all of them.
| a majority | another | shared |
|---|---|---|
| alpha bravo charlie | alpha bravo delta | alpha bravo |
| alpha bravo charlie | alpha charlie delta | alpha charlie |
| alpha bravo charlie | bravo charlie delta | bravo charlie |
| alpha bravo charlie | alpha bravo echo | alpha bravo |
| alpha bravo charlie | alpha charlie echo | alpha charlie |
| alpha bravo charlie | bravo charlie echo | bravo charlie |
| alpha bravo charlie | alpha delta echo | alpha |
| alpha bravo charlie | bravo delta echo | bravo |
256 pairs of majorities checked and 8 shown, 0 of them disjoint. There is no pair that does not overlap, so any later majority includes someone who acknowledged.
4 Take machines away until no majority is possible, and watch it refuse rather than guess
Take machines away. At some point too few remain to acknowledge as a majority, and this model refuses the write.
| down | still up | majority needs | enough acknowledgments? |
|---|---|---|---|
| 0 | 5 | 3 | yes |
| 1 | 4 | 3 | yes |
| 2 | 3 | 3 | yes |
| 3 | 2 | 3 | no, it refuses |
| 4 | 1 | 3 | no, it refuses |
| 5 | 0 | 3 | no, it refuses |
A cluster of 5 can obtain a majority acknowledgment with 2 machine(s) down and stops at 3. Adding one more machine would not raise that number.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| every one of 256 pairs of majorities of 5 shares a machine | yes | no two are disjoint |
| and at every cluster size from 3 to 9, odd and even alike | yes | floor(n/2)+1 is enough at all of them |
| every later majority contains a member of the acknowledging majority | yes | none of them can be missed |
| with 3 of 5 down it refuses without enough acknowledgments | yes | needs 3, has 2 |
| three of five meets the acknowledgment threshold and two does not | yes | the boundary is where it should be |
What is real here, and what is not
What the counting proves is reachability, and permanence is a bigger word
Any two majorities of the same set share a member, so a later majority cannot fail to contain somebody who saw this write. That is the whole of what the set theory gives, and it is worth having. It is not permanence. Turning reachability into a write that cannot be undone takes rules this page does not model: terms, leaders, and which value a node is allowed to accept next. The panel said so, and the readout beside it used to say “the write is permanent” and “nothing will make it un-happen” anyway, three inches below its own caveat. An outside reader caught it. The readout now says what the intersection buys and names the question it leaves open.
This is quorum intersection, not an implementation of Raft or Paxos
The one property on this page, that any two majorities share a member, is one ingredient in those algorithms, and it is the whole of what is modelled here. There are no terms, no elections, no log matching, no leader completeness argument, and no network. A real consensus protocol spends almost all of its length on what happens when messages are delayed, duplicated or reordered, and none of that appears. Dating the machine 2014 points at the Raft paper because that is where this argument is set out most readably, not because the idea is from 2014: it is Lamport's, and older.
Nothing here is distributed
Five machines is five entries in an array in one browser tab. Nothing is sent anywhere and no message can be lost, which means the page cannot show you the failures that make consensus hard. It can only show you why the counting rule is the right counting rule.
The enumeration is complete up to nine machines and stops there
A set of n has 2^n subsets, so checking every pair of majorities is a 4^n job. (An earlier version of this sentence said every subset has 2^n members, which is not what a power set is; an outside reader caught it.) At nine machines that is already 256 majorities and 65,536 pairs, computed on load. The claim on this page is therefore exactly what is checked: it holds for every cluster size from three to nine. It is true for all n, and the proof of that is two lines of arithmetic rather than an enumeration, but this page does not run the two lines — it counts.
Even-sized clusters are included on purpose
A majority of four is three, not two, so a four-machine cluster tolerates exactly one failure, the same as three, while having one more machine to go wrong. That is the standard argument for odd cluster sizes and it falls straight out of the table in the last panel rather than being asserted beside it.
Sources
- D. Ongaro and J. Ousterhout, In Search of an Understandable Consensus Algorithm, USENIX ATC 2014. Where the quorum-intersection argument is set out most plainly.
- L. Lamport, The Part-Time Parliament, ACM TOCS 16(2), 1998. The Paxos paper, where the majority requirement and its intersection argument originate.
- Logical Art, the studio this belongs to.