A majority of n is ⌊n/2⌋ + 1, and any two majorities intersect, which is why consensus is built on them. The failures tolerated are f = ⌊(n − 1)/2⌋, so 2f + 1 is the only cluster size worth buying: four nodes tolerate one failure exactly as three do, while needing three of four up instead of two of three. With nodes up 99% of the time that makes four nodes strictly less available than three — 99.940797% against 99.9702%.
Core ideas
The intersection property, the integer that follows from it, and the availability that follows from the integer.
Two subsets of n each larger than n/2 cannot be disjoint — it is the overlap theorem with R = W = ⌊n/2⌋ + 1. That is what stops two leaders being elected in the same term and two conflicting decisions being committed: any two decisions share a node, and a node does not vote both ways.
The cluster keeps working while a majority is still up, so it tolerates n − (⌊n/2⌋ + 1) failures, which is ⌊(n − 1)/2⌋. At n = 3 that is 1; at n = 4 it is also 1; at n = 5 it is 2. f only moves on the odd sizes, and n = 2f + 1 is the cheapest cluster tolerating f.
Going from three nodes to four takes the majority from 2 to 3 while f stays at 1. You now need three specific machines up instead of two, out of a pool with one more thing in it that can break. With independent 99% nodes that is a net loss: 99.940797% against 99.9702%, and the fourth machine has been bought to make the cluster worse.
The material
Why consensus is built on majorities, what an even cluster size actually buys, and the binomial tail that prices both.
A majority of n nodes is any subset of size ⌊n/2⌋ + 1. A cluster that requires a majority to make progress tolerates f = ⌊(n − 1)/2⌋ failures, and the relation is usually written n = 2f + 1: to tolerate f, buy 2f + 1 nodes.
The intersection property is the reason for all of it. Two majorities of the same n must share a node, by the same pigeonhole argument that “Quorums Overlap” proved, so a node that has voted for one decision can refuse a conflicting one. Nothing else about a majority is special — it is simply the smallest quorum that overlaps itself.
Read down the f column and the design rule falls out: 3, 5, 7. The even sizes are transitional — they carry the cost of the next size up and the tolerance of the one below. That is why production clusters are almost always odd, and why the advice is repeated so often that its reason gets lost.
The arithmetic is not a curiosity, it is the direct consequence of needing three specific things to work instead of two. Availability of a k-of-n system falls as k rises and rises as n does, and the even step raises k by one while raising n by one — and at 99% per node the first effect wins.
From three nodes, the upgrade is five, not four. Five tolerates two failures instead of one and is available 99.99901494% of the time against 99.9702% — a factor of about thirty in the downtime, for two more machines. Four tolerates one failure and is available 99.940797%, which is worse than the three it replaced. If the budget allows one more node and not two, the right answer is to keep three and spend the money on making a node's own availability better, because that is the quantity every figure in this table is a function of.
Every number here assumes failures are independent, and Availability and Failure's “Correlated Failure” exists to say how badly that can go. Three nodes in one rack share a switch, a power feed and an operator; the majority arithmetic is then describing a cluster that does not exist and the real availability is closer to one node's. Spreading the 2f + 1 across failure domains is what makes the independence assumption approximately true, and it is the whole reason to care where the nodes are.
Interactive
f = floor((n − 1)/2), and the availability of the quorum that follows
Method
Start from the failures you intend to survive, not from the number of machines you happen to have.
“How many failures must this survive” is a product question with an answer; “how many nodes should we run” is not. One failure means three nodes, two means five, three means seven, and nothing in between is worth buying.
n − majority must equal the f you chose. Doing this explicitly is what catches an even n: at n = 4 the majority is 3 and n − 3 = 1, which is the tolerance you would have had for one machine less.
A = Σ C(n,k) p^k (1 − p)^(n−k) from k = majority to n. Do it for your n and for n − 1 and n + 1, so that the shape of the table is in front of you rather than remembered.
Name the failure domains the nodes are spread across. If two of three share a rack, the binomial tail is optimistic and the number to report is much closer to that rack's availability than to 99.9702%.
A three-node consensus cluster is running and a fourth machine has become available. The proposal is to add it, on the grounds that four is more than three. Both halves of the question — tolerance and availability — have exact answers.
Four numbers went the wrong way and one stayed still. The fourth node buys no additional tolerance, roughly doubles the expected downtime, adds a third to the storage and write work, and gives the operator one more machine to patch. There is no reading of that table in which it is an improvement.
The five-node row is the honest alternative and it is a large step: two tolerated failures and about a thirtieth of the downtime. Whether it is worth two machines is a real question; whether the four-node cluster is worth one machine is not.
For a faded rehearsal, suppose the nodes are only 95% available each rather than 99%. The supplied first move is that the n = 3 majority availability becomes 3(0.95)²(0.05) + (0.95)³. Compute it, do the same for n = 4 and n = 5, and say whether the even-size penalty is larger or smaller at 95% than it was at 99% — then check both in the lab.
You should be able to compute ⌊n/2⌋ + 1 and f for any n, evaluate the majority's availability as a k-of-n binomial tail, say why every even size is dominated by the odd one below it, and name the independence assumption and the failure domains it needs.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.