If a read consults R nodes and a write reaches W of N, then R + W node names are drawn from a pool of N, and R + W > N forces at least R + W − N of them to coincide. That is the pigeonhole principle applied to machine names, and the bound is attained, which is what makes it the guarantee rather than merely a limit. It is also strictly less than consistency, and this lesson says exactly how much less.
Core ideas
A counting argument, a check that the count is tight, and a careful statement of what the argument does not give you.
A read set of R nodes and a write set of W nodes name R + W nodes between them, all drawn from the same N. If R + W > N they cannot all be distinct, so at least R + W − N names appear in both sets. Nothing about time, ordering or protocol enters the argument — it is Discrete Mathematics' pigeonhole principle with nodes as pigeonholes.
A bound that is never reached would be the wrong number to design on. Here it is reached: at N = 3, R = 2, W = 2 the lab compares all 9 read-set and write-set pairs and finds the smallest intersection is exactly 1, which is R + W − N. So R + W − N is what you get in the worst case, and sizing a design as though you got more is sizing it wrong.
The guarantee is that at least one node in the read set holds the latest acknowledged write. It does not say the reader can identify which of the returned values that is, what happens when two writes are concurrent, or that the whole history looks like it happened at single instants. Those are separate questions, and “Linearizability by Enumeration” is where the last of them gets answered.
The material
A one-line proof, an enumeration that shows the bound is tight, and a careful account of what a quorum configuration does not buy.
Let a write be applied to a set of W nodes and a read consult a set of R nodes, both subsets of the same N. If R + W > N then the two sets intersect, and the intersection contains at least R + W − N nodes. If R + W ≤ N there exist a read set and a write set that are disjoint.
The read set and the write set together name R + W nodes, counted with repetition, from a pool of N distinct nodes. Each node can be named at most twice — once by each set — so the number of nodes named by both is at least R + W − N. When R + W > N that quantity is positive, so the sets intersect.
For the converse, if R + W ≤ N then the W nodes of the write and R further nodes can be chosen from the N without reusing any, and those R form a read set disjoint from the write set. Such a read returns no copy of the write at all.
□
The theorem is about set membership and it is proved in two lines, which is why it is the load-bearing fact in every quorum system. What takes care is the second half of the statement: the bound is a minimum, and a minimum is only useful if something attains it.
Two thirds of the pairs sit exactly on the bound, so a design that assumed a comfortable margin of agreement between the read set and the write set has assumed something that is false most of the time. The guarantee is one node, and one node is enough — provided the reader knows what to do with a set of answers that disagree.
The read set contains a node holding the latest acknowledged write. It also contains, in general, nodes holding older values, and the reader receives all of them without a label saying which is which. Version numbers or timestamps are what turn the overlap into an answer, and they bring their own difficulties — “Lamport Clocks” and “Physical Clocks and Drift” are both about how badly a naive version of that can go.
N = 3, R = 2, W = 2. Client one writes x = 1 to {1,2}; at the same moment client two writes x = 2 to {2,3}. Both writes satisfy the configuration and both are acknowledged. A reader consulting {1,3} sees 1 and 2 and overlaps with both write sets, exactly as the theorem promises. The theorem has done its job and the reader still does not know which value is current, because neither write happened before the other. That is a conflict rather than a staleness problem, and it is what “Vector Clocks and Concurrency” makes countable and “Conflict Resolution, Counted” decides.
So the right claim for a (N, R, W) configuration with R + W > N is: no acknowledged write can be missed entirely by a subsequent read. That is a real and useful guarantee. It is not “the read returns the current value”, and the gap between the two is where most of the remaining lessons on this course live.
Interactive
R + W > N, the minimum R + W − N, and the pair that misses when it does not
Method
Two integers decide it and the third step is where a real design usually goes wrong — not in the arithmetic, but in what it is asked to mean.
Strictly greater. R + W = N is not the boundary case of a guarantee, it is the absence of one, and “Sloppy Quorums and the Miss Probability” prices exactly how absent.
That is the number of nodes the read and write sets are guaranteed to share, and it is attained. If your design needs two shared nodes — because you intend to survive one of them being wrong — then R + W − N ≥ 2 is the condition, not R + W > N.
(N, R, W) = (3, 3, 1) gives fast writes and slow reads; (3, 1, 3) the reverse; (3, 2, 2) balances them. All three overlap. Choose by which of the two paths is hot, using the latency arithmetic of “Quorum Latency: the W-th Fastest”.
It gives you a node with the latest acknowledged write in every read set. It does not give you a way to recognise that node's answer, a resolution for concurrent writes, or linearizability. Writing that sentence into the design document is what stops a quorum from being quoted as consistency later.
A five-node cluster, and four proposals on the table. For each one the question is whether it overlaps at all and, if so, by how much in the worst case.
The first three configurations are equally safe and wildly different to operate. R = 1, W = 5 cannot tolerate a single node being down for writes; R = 5, W = 1 cannot tolerate one being down for reads; R = 3, W = 3 tolerates one being down on either path. The overlap arithmetic is blind to all of that, which is why it is a necessary condition and never the whole design.
The fourth line is the trap, and it is a popular one because R + W = N looks like a boundary you are standing on rather than one you are outside of. The exhibited pair settles it: a write to {1,2,3} and a read of {4,5} are both legal under that configuration and share nothing.
For a faded rehearsal, take N = 7 with R = 3 and W = 5. The supplied first move is R + W = 8 > 7, so it overlaps. Compute the minimum overlap, then find the smallest R that keeps the configuration overlapping if W is cut to 4, and say what that change does to the read path before you check it in the lab.
You should be able to decide any (N, R, W) at sight, compute the minimum overlap and know it is attained, exhibit a disjoint pair when the condition fails, and separate “no acknowledged write is missed” from “the read returns the current value”.
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.