A quorum write is acknowledged when W of N replicas have replied, so it waits for an order statistic rather than for everyone: P(ack by t) = P(at least W of N replied by t), the same binomial tail that a k-of-n availability is. Hold W fixed and raise N and the write gets faster — 8 ms at N = 3, 4 ms at N = 4 — which is the opposite of what everyone expects, and it quietly breaks the overlap condition on the way.
Core ideas
One distributional fact, one counter-intuitive consequence, and the cost the consequence hides.
The coordinator sends to all N and acknowledges as soon as W have come back. The wait is therefore the W-th smallest of N reply times, and P(ack by t) is the probability that at least W of N independent replies landed by t — exactly the binomial tail Availability and Failure used for k-of-n, with success probability F(t).
At a fixed t, each replica independently has probability F(t) of having replied. Adding another replica adds another Bernoulli trial without raising the threshold W, so the probability of reaching W by t goes up, and the p99 goes down or stays put. On the distribution here W = 2 costs 8 ms at N = 3, 4 ms at N = 4 and 2 ms at N = 8.
Raising N with W fixed is free latency and expensive correctness: the overlap condition R + W > N has an N on the wrong side of it. Going from three replicas to four with R = W = 2 takes a configuration that overlapped to one that does not, and the read now misses the write one time in six. The fast answer and the correct answer are different answers.
The material
Where the binomial tail comes from, why a larger N is faster, and what the same change does to the overlap.
A quorum write with parameters (N, W) is sent to all N replicas and acknowledged when W of them have replied. If replies are independent with CDF F, then P(acked by t) = Σ C(N,k) F(t)^k (1 − F(t))^(N−k) summed over k = W to N — the probability that at least W of N replies arrived by t.
This is the same sum as a k-of-n availability and the lab computes it with the same code, which is the point: “at least W of N replied by t” and “at least k of n are up” are one question asked of two different Bernoulli trials.
Two of the rows are worth pausing on. W = N is the synchronous write of an earlier lesson and it costs 24 ms; relaxing the same three-node cluster to W = 2 costs 8 ms, a third as much, for a write that is still on two machines. And then adding a fourth replica — a change everybody describes as making writes more expensive — halves it again.
Because W is a threshold and N is the number of attempts at it. Each replica is an independent chance to be among the first two back; more chances means the second one arrives sooner. The write is not waiting for the extra replica, it is racing it, and a race with more entrants finishes its second place earlier.
Nothing about the fourth replica is faster than the first three. What changed is that the event “fewer than two replies by 4 ms” now requires three or four stragglers instead of two, and stragglers are rare enough that requiring one more of them pushes the probability below the 1% the p99 is asking about.
The same cluster runs R = 2, W = 2 at N = 3: R + W = 4 > 3, so it overlaps and the minimum overlap is 1. Add the fourth replica for the latency and now R + W = 4 = N, which overlaps nothing — and “Sloppy Quorums and the Miss Probability” prices the damage as C(N−W, R)/C(N, R) = C(2,2)/C(4,2) = 1/6. One read in six misses the write. Restoring the guarantee means R = 3, which makes every read wait for the third fastest of four instead of the second of three. The write got faster by making the read slower, and no dashboard would have shown the trade.
So the useful rule is not “more replicas are slower” or “more replicas are faster”. It is that N moves the latency of a fixed-W quorum down and moves the overlap condition against you at the same time, and both effects have to be computed whenever N changes.
Interactive
A binomial tail, and why more replicas make a fixed-W write faster
Method
The arithmetic is a binomial tail. The discipline is remembering that N appears in two places in your design and you have only changed one of them.
W is the threshold the quorum is defined by. F is a measurement, and as with any tail question you need the distribution rather than a mean.
P(at least W of N by t) with success probability F(t). Sum from k = W to N, or subtract the terms below W from one, whichever is shorter — at small W the second is much shorter.
That is the quorum's p99. Compare it with the W = N case, which is the synchronous write, to see what the relaxation bought.
Every increase in N at fixed W improves the latency and erodes the overlap. If the configuration no longer overlaps, either raise R — and recompute the read's latency by this same method — or keep the smaller N.
A three-node cluster acknowledges writes at two replicas. The p99 is 8 ms and the team wants it lower. Somebody proposes removing a replica, on the grounds that fewer machines are fewer things to wait for.
The proposal is exactly backwards and the binomial tail says why in one line: with W fixed at two, each replica is another chance to be one of the first two back. At N = 2 there are no spare chances at all and the write waits for both, which is the 24 ms maximum of the synchronous lesson.
The second line of the lab's arithmetic is the one to keep. Between N = 3 and N = 4 the p99 halves, and between N = 4 and N = 8 it halves again to 2 ms, which is the floor of this distribution — no configuration can beat the fastest time any replica ever replies in.
For a faded rehearsal, the team accepts N = 4 for the write and now has R = W = 2 on four nodes. The supplied first move is that R + W = 4 is no longer greater than N = 4. Work out what R must become, compute the read's p99 at that R by the same binomial tail, and state the net change to a read-then-write round trip before checking either figure.
You should be able to write P(ack by t) as a binomial tail, evaluate it at a handful of times, read a p99 off it, sweep N and predict the direction before computing, and state what the same sweep did to R + W > N.
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.