Majority
A distributed system that waited for every machine before calling a write permanent would stop the first time any machine did. So it waits for a majority instead, and calls the write permanent while some machines have never heard of it. What makes that safe is not the counting. It is that any two majorities of the same set must share at least one member, so whatever group forms next cannot fail to contain someone who saw the write. That is a fact about sets rather than about networks, and this page settles it by enumerating every subset rather than by arguing.
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 Three acknowledge. That is a majority, and the write is now permanent
A majority acknowledges. The write is permanent from that instant, and the machines that are down still know nothing about it.
- a majority is
- 3 of 5
- acknowledged by
- 5 machine(s) still up
- the write is
- permanent
The write is permanent with 0 machine(s) that have never heard of it. Nothing will make it un-happen, because any group that forms next has to contain one of the 5 that did hear it.
3 Any two majorities of five share a machine, so the next leader cannot fail to see it
Why that is safe. 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, which is the reason a majority is enough.
4 Take machines away until no majority is possible, and watch it refuse rather than guess
Take machines away. At some point no majority is possible, and the cluster stops being able to promise anything — which is the correct behaviour and not a failure of it.
| down | still up | majority needs | can it commit? |
|---|---|---|---|
| 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 keeps working 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 |
| a write acknowledged by any majority is visible to every majority | yes | none of them can be missed |
| with 3 of 5 down it refuses rather than commits | yes | needs 3, has 2 |
| three of five commits and two of five does not | yes | the boundary is where it should be |
What is real here, and what is not
This is quorum intersection, not an implementation of Raft or Paxos
The one property on this page — any two majorities share a member — is what makes those algorithms safe, 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.