A system that needs k of its n replicas is available with probability Σ_{j≥k} C(n,j)Aʲ(1 − A)ⁿ⁻ʲ, the upper tail of a binomial. Series and parallel are the two ends of it: k = n is the product and k = 1 is 1 − ∏(1 − Aᵢ). Whether another replica helps depends entirely on whether k rises with n, and if it does the answer is no.
Core ideas
A quorum is a counting question about how many replicas are up, and the answer contains both of the previous lessons as special cases.
With n replicas that are independently up with probability A, the number up is Binomial(n, A), so P(exactly j up) = C(n,j)Aʲ(1 − A)ⁿ⁻ʲ. A k-of-n system is available when at least k are up, which is the sum of those terms from j = k to j = n — the upper tail. The lab lists every term and sums them exactly, and the whole row sums to 1.
Setting k = n demands every replica and the tail collapses to the single term Aⁿ, which is the series product. Setting k = 1 demands any one and the tail is everything except j = 0, which is 1 − (1 − A)ⁿ — the parallel formula. These are identities, and the lab checks both on screen rather than asserting them.
At A = 99%, 3-of-5 is 99.9990149% and 5-of-5 is 95.0990%, which is worse than a single machine's 99%. Going from n = 1 to n = 5 helped or hurt entirely according to what happened to k. A quorum that grows with the fleet, like k = n, is a chain wearing a redundancy costume.
The material
Where the coefficients come from, how the formula contains the previous two lessons, and the configuration in which redundancy runs backwards.
A system is k-of-n when it serves as long as at least k of its n components are up. If the components are independent and each is up with probability A, then A(k, n) = Σ_{j=k}^{n} C(n,j) Aʲ (1 − A)ⁿ⁻ʲ. The term at j is the probability that exactly j are up: C(n,j) ways to choose which, Aʲ for those being up and (1 − A)ⁿ⁻ʲ for the rest being down.
The column sums to exactly 1, which is the cheapest available check on a binomial: a set of terms that does not sum to one has a wrong coefficient somewhere in it. The lab prints that sum for whatever n you set, and the coefficients are exact integers, so the twelfth row of Pascal's triangle is right rather than nearly right.
At k = n only the j = n term survives, so A(n, n) = Aⁿ, which is the series product of n identical components. At k = 1 every term except j = 0 survives, so A(1, n) = 1 − (1 − A)ⁿ, which is the parallel formula. Three formulas, one of them; the lab computes all three and prints their agreement.
Each replica 99%. 1-of-5 is 99.999999990000% — ten nines, and the parallel formula to the digit. 3-of-5 is 99.9990149% — five nines, 5 min 10.65 s a year. 5-of-5 is 95.0990% — one nine, 17 d 21 h a year, and identical to (99/100)⁵. The same five machines span nine orders of magnitude in downtime depending only on how many of them have to agree.
Compare 5-of-5 at 95.0990% with a single machine at 99%. Four replicas were added and the availability fell by a factor of about fifty in downtime, because each new replica was also a new thing that had to be up. This is the honest answer to “should we add another node”: it depends on whether the quorum rule holds k fixed as n grows.
Majority quorums, k = ⌈(n+1)/2⌉, sit between the two extremes and do improve with n, because k grows at half the rate n does: 2-of-3 is 99.97020% and 3-of-5 is 99.9990149% at the same per-node 99%. That is the arithmetic behind five-node clusters, and it is also why going from five to seven buys much less than going from three to five.
A team runs three replicas and, worried about durability, changes writes to require acknowledgement from all three rather than two. Write availability moves from 2-of-3, 99.97020%, to 3-of-3, 97.0299% — from three nines to one, and from 2 h 36 min to 10 d 20 h a year. Nothing about the hardware changed. The lab reproduces this in two slider moves: set n = 3, then k = 2 and k = 3.
One boundary to keep in view: this lesson counts replicas that are up and says nothing about whether they agree on the data. A quorum that is available can still return a stale read, and the rule that prevents that — read and write sets overlapping — is a different condition on k that belongs to the replication course.
Interactive
A binomial tail, and the two compositions it collapses to at its edges
Method
Two of these steps are arithmetic and two are about what the number means once you have it. The second pair is where quorum decisions are actually made.
Reads and writes often have different quorums, and the availability of a write is not the availability of a read. Compute them separately; a system quoted as one number is usually quoting whichever is better.
Σ_{j≥k} C(n,j)Aʲ(1 − A)ⁿ⁻ʲ. Write the terms out rather than reaching for a closed form — there is not one — and check that all n + 1 terms sum to one before trusting the part you kept.
Evaluate the same n at k = n and at k = 1. The first must equal the series product Aⁿ and the second the parallel 1 − (1 − A)ⁿ. If either disagrees, a coefficient or an exponent is wrong.
Fixed k means more replicas help. k = n means they hurt. A majority rule means they help with diminishing returns. That single question decides whether adding a node is an improvement, and it is answered by the quorum rule rather than by the node count.
The smallest quorum question that comes up in practice, and the one where the intuition that more agreement is safer does the most damage.
Three nodes requiring two are a hundred times better than one node. The same three nodes requiring three are three times worse than one node, and the only thing that changed was a constant in a configuration file. The j = 2 term, 0.029403, is where all of the difference lives: it is the probability that exactly one node is down, which 2-of-3 survives and 3-of-3 does not.
For a faded rehearsal, take n = 5 at the same per-node 99% and work out 4-of-5. The supplied first move is that you need the terms at j = 4 and j = 5, which are already listed in the material above. Produce the availability and its annual downtime, place it between the 3-of-5 and 5-of-5 figures, and then answer the design question: going from three nodes to five, what must happen to k for the change to be an improvement at all?
You should be able to sum a binomial tail exactly, recover the series and parallel formulas from it by setting k = n and k = 1, check the terms against a sum of one, and explain a configuration in which five replicas are less available than one.
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.