Distributed consensus, replication, and fault tolerance / personal lessonsLesson 6 of 17
Lesson browserDistributed consensus, replication, and fault tolerance lessonsPrevious: Replication and the meaning of successNext: Consensus, safety, and the limits of progress
Distributed systems · Lesson 6

Quorums and the information in an intersection

Derive majority overlap and identify what overlap cannot prove.

By the end: Calculate availability thresholds and explain why shared members need durable protocol rules.

Derive the overlap rather than memorize it

A quorum is a set sufficient for a protocol action. Suppose N fixed replicas contain a write-response set of size W and a read-response set of size R. If those sets were disjoint they would need W+R distinct replicas. When W+R exceeds N that is impossible. At least W+R−N members must be shared. If this difference is negative, the minimum is zero.

A strict majority contains more than half the members, so any two majorities intersect. With five members a majority is three. Sets {A,B,C} and {C,D,E} share C. With four members a majority is also three, so moving from three to four does not increase the number of unavailable members a majority-based system can tolerate. Five members are needed to tolerate two unavailable members while still forming a majority.

Calculate overlap for identities rather than message counts

The overlap argument counts replica identities in a fixed membership. It does not count packets or entries. Suppose the configured members are A, B, C, D, and E. A write receives durable replies from A, B, and C. A later read obtains replies from C, D, and E. There are six memberships in the two response sets but only five possible distinct members, so at least one identity must occur twice. Here that identity is C. Repeated replies from A would not enlarge either set. A quorum calculation starts by removing duplicates and checking that each identity belongs to the relevant configuration.

To derive the general bound, the combined number of distinct members equals the first set's size plus the second set's size minus their intersection size. That combined set cannot contain more than N members. Therefore the intersection must contain at least W plus R minus N members, or zero when that difference is negative. With N equal to 7 and set sizes 5 and 4, at least 2 identities must be shared. Try selecting the first set as A through E. Only F and G lie outside it, so a four-member second set must take at least two members from the first.

The strict inequality matters. With five members, a two-member write set and a three-member read set can be disjoint. Choose A and B for the write and C, D, and E for the read. Their sizes sum to five, leaving no forced intersection. Some other choices of those sizes do intersect, but a protocol that needs guaranteed contact must handle every allowed choice, including this one. Observing overlap in several successful executions is weaker than proving overlap for all permitted response sets. The bound describes the worst allowed placement, not an average placement or a probability.

Two write quorums require a separate comparison from a write quorum and a read quorum. For a uniform write size W, guaranteed write-write overlap requires twice W to exceed N. A read size can be small when writes require many responses, but that says nothing by itself about how concurrent writers coordinate. With five members, W equal to 4 and R equal to 2 forces at least one write-read intersection and at least three write-write intersections. These facts still do not say which value a read should return or which writer may declare a final decision.

Majority quorums use the same strict-majority size for the relevant actions, which makes the set proof simple. They are not the only possible quorum design. Some protocols restrict the permitted combinations or use different requirements for different phases. An alternative design must prove the intersections needed by its own rules rather than borrowing a majority slogan. This course uses small fixed memberships so that every identity and overlap can be checked directly. Membership changes later require an explicit transition argument because the fixed universe of N identities is an assumption of this derivation.

Count messages and failures separately

A write needing W distinct responses can complete only when at least W required replicas are reachable and able to respond. It tolerates at most N−W unavailable required replicas. A read needing R has a corresponding N−R limit. A repeated reply from one replica cannot count as another member. Neither can an acknowledgment from an unconfigured machine simply be added to the count.

These are availability bounds for that quorum action, not a guarantee that every schedule terminates. Conflicting proposers, unavailable storage, or continued leadership changes can still prevent progress. Quorum intersection also assumes the same relevant membership, or a correct transition between memberships. Replacing the member list independently on each server can destroy the intersection that the proof depended on.

Separate reachable majorities from independent failures

For a quorum action, enough configured members must be able to exchange the required messages. A five-member majority system needs three responses. If two members stop responding, the other three may still complete that action. If three stop responding, the remaining two cannot. This subtraction is a necessary reachability threshold, not a promise about response time. A member with a healthy process but a full disk may be unable to provide the required durable reply. A member reachable in one direction may receive a request while its response cannot reach the requester.

A partition makes the perspective explicit. Divide five members into A, B, C on one side and D, E on the other. Only the first side has enough members for a majority, assuming its members can communicate as required and meet the protocol's other conditions. Now divide them into groups of two, two, and one. No group has a majority despite all five processes running. Uptime counts and quorum reachability answer different questions. Clients may also reach a server that cannot reach enough peers, so accepting the client's connection does not imply the server can complete a protected operation.

Adding a replica can increase the response requirement without increasing tolerated failures. Three members require two responses; four require three. Both can lose one member and still form a majority. This arithmetic does not mean a fourth copy has no possible value. It can affect placement or other operations, but it does not improve this specific majority threshold. When evaluating a proposed topology, calculate the required response set first and then remove each intended failure domain. Do not infer tolerance from the copy count alone.

For a separate placement case, put A, B, and C in region X and D and E in region Y. Five replicas still tolerate any two unavailable individual members for majority reachability. Losing region X removes three members and stops majority progress, while losing region Y removes only two. The two regional failures therefore have different consequences. Spreading five members across regions as two, two, and one allows a majority to remain after losing any one region, provided communication among the survivors still works. This calculation is not a measured reliability forecast and does not establish that regional failures are independent.

Leadership and storage conditions remain after the reachability check. Three reachable voters can keep splitting elections, reject an outdated candidate, or wait for durable storage. An algorithm can also need a stable communication period before one coordinator finishes its work. Thus enough reachable members makes a quorum possible, not inevitable on every schedule. The next lesson examines why unconditional progress is too strong under some timing assumptions. Keep the present calculation limited to identifying whether the required response set can exist at all, then ask which protocol conditions permit the action and which timing conditions let it finish.

Work through the model

Make the sets overlap

N=3 replicas, W=2 write acknowledgments, R=2 read responses. These fixed-membership examples choose the least-overlapping sets. A preset replaces all three values.

A

Write ✓

Read —

Not shared

B

Write ✓

Read ✓

Shared member

C

Write —

Read ✓

Not shared

Minimum overlap
2+2−3=1

If the subtraction is negative, use zero. Overlap guarantees contact with a write holder, not that a read protocol returns the right version.

At least 1 shared replicas. Writes can tolerate 1 unavailable replicas; reads can tolerate 1. Majority for this membership is 2. This is set arithmetic, not a complete consistency protocol.
Five membersFirst quorumSecond quorumShared evidence
Correct durable ruleA B CC D EC remembers prior decisions
Forgotten state at CA B CC D ESame identity, missing history
Changed membershipA B CD E FNo shared member
Only the first row supplies both intersection and remembered evidence. That still needs a protocol-specific proof.

Use the presets to test the worst permitted sets

The quorum control has three named presets rather than editable membership or delay controls. Each preset replaces N, W, and R together. It constructs the write set from the beginning of the displayed identity list and the read set from its end. This chooses the least possible overlap for those sizes. In Majority survives one crash, N is 3 and both sets have size 2. The displayed write set is A and B, and the read set is B and C. B is the forced shared identity, and each action can tolerate one unavailable required member.

In Disjoint sets are possible, N is 5, W is 2, and R is 3. The displayed write set is A and B; the read set is C, D, and E. No member carries both labels. The write action can tolerate three unavailable members if the other two are suitable responders, while the read action can tolerate two. Those thresholds do not rescue the absent intersection. A read through the selected set can miss every holder of the write. On paper, move C into the write set and observe that this particular choice overlaps, without changing the fact that disjoint choices remain permitted.

In Write all, read one, every member belongs to the write set and E alone forms the read set. The minimum intersection is one. A successful write cannot omit E under these assumptions, so the read set must contain a write participant. Write reachability now tolerates zero unavailable members; read reachability tolerates four. This is a tradeoff between the response requirements of different actions, not an implementation of a register. The control does not model versions, concurrent writes, failed writes, durable acknowledgments, or how a reader chooses a result from responses.

For a guided paper extension, choose six members with W equal to 4 and R equal to 3. List A, B, C, D as the write set. Only E and F remain outside it, so the read set must share at least one member. Then reduce R to 2 and select E and F. The guarantee disappears at equality. Next keep R equal to 3 but reduce W to 3. Again choose disjoint sets. These separate cases identify which threshold matters. They are not additional settings in the preset control, whose displayed membership never exceeds five.

Read the evidence table below the control as a comparison of assumptions. In its durable-rule row, a shared member retains relevant history. In its forgotten-state row, the same identity no longer supplies that history after recovery. In its changed-membership row, the apparently comparable quorums do not even share an identity. The first row still needs protocol rules explaining what a retained record forbids. Neither the equation nor a Shared member label means the reader has discovered a final value. The experiment proves only the displayed set relationship and the stated response-count thresholds.

The common member must carry the right evidence

Intersection guarantees a shared participant, not an automatically correct decision. The participant must remember a relevant accepted value or promise and obey rules about future answers. If it forgets after a restart or accepts incompatible decisions without restriction, the shared identity contributes no protection. This is why stable storage is part of a protocol’s safety argument.

Likewise, W+R>N alone is not a complete linearizable register algorithm. Reads need version selection rules, concurrent writes need an ordering protocol, and some algorithms need read repair or write-back before a read completes. Sloppy quorums can place temporary copies outside the normal member set, so apparently sufficient counts may not intersect as assumed. Use the inequality to prove a set relationship, then separately prove what information and behavior the relationship enforces.

Make the shared member enforce an obligation

Suppose A, B, and C decide a paper proposal using replies from A and B. A later attempt obtains replies from B and C. The common member B can protect the earlier result only if its earlier reply changed what it may do later. If B freely approves either value whenever asked, both quorums can approve incompatible results. Persistence alone is not enough either. B might faithfully remember approving x yet have no rule against approving y. The safety argument needs a durable record plus a future behavior restriction tied to that record.

For crash-recovery protocols, the order of recording and responding matters. If B sends its approval first and persists the corresponding restriction afterward, a crash between those events leaves the other participants counting a promise that B will forget. On restart, B can approve an incompatible attempt. To cover that failure, the protocol requires the relevant durable update before the response becomes valid evidence. This assumes that recovery uses the same stable replica identity and the promised storage survives the specified crash. Starting an empty replacement under B's old identity without safe state transfer does not satisfy the remembered-obligation assumption.

Read protocols need rules for partial operations as well as successful writes. Extend the earlier register counterexample to five replicas with three-response reads and writes. A writer stores version 9 at A and B, then stops short of its required quorum. One read contacts A, C, and D and returns 9; a later read contacts C, D, and E and returns 0. The read sets share two members, but neither shared member holds version 9. Increasing read-read overlap has not solved the regression. Once a read exposes 9, subsequent reads need a compatible explanation even though the original write never completed.

One family of register algorithms addresses this issue with ordered version tags and write-back. A reader gathers responses, selects the greatest suitable tag, and propagates that tagged value to a write quorum before returning. Later read quorums then intersect that propagation set. The complete algorithm must also define unique ordered tags for concurrent writers, persistence, and the handling of incomplete operations. Merely attaching local timestamps and choosing the largest does not establish those properties. This example explains why an extra protocol phase can matter; it is not a full register implementation or a capability of the quorum widget.

Sloppy quorums change another premise. A system may temporarily store data on substitute nodes when normal owners are unavailable. Counts of W and R then refer to responses that may come from different identity universes. Their sum can exceed the normal replica count without forcing the assumed contact. Repair and handoff need their own semantics, and a convergence promise is different from a linearizable read promise. As later chapters introduce Raft and Paxos, identify the exact record at a shared participant and the exact action it forbids. Quorum arithmetic locates where information could pass between attempts. The protocol must make that information sufficient to preserve the earlier decision.

Exercises

Is four better than three?

A system uses strict-majority writes. Compare three, four, and five replicas for tolerance of unavailable members.

Hint

Subtract each majority size from its membership size.

Worked answer
MembersMajorityUnavailable tolerated
321
431
532
This counts unavailable members, not arbitrary Byzantine behavior.

Three requires two and tolerates one unavailable member. Four requires three and also tolerates one. Five requires three and tolerates two. Additional replicas may serve other goals, but the majority availability threshold changes in these steps.

A read sees a new value once

In a three-replica store, an incomplete write reaches only A. A read of A and B returns that value; a later read of B and C returns the old value. Does intersecting read sets prevent this?

Hint

Their intersection is B, which never received the new value.

Worked answer
StepABCResult
Partial write100No write success
Read A+B100Returns 1
Later read B+C100Returns 0, forbidden regression
The incomplete write is not automatically absent from the history once a read exposes it.

No. The first read can expose the incomplete write, which then needs a position before that read in a linearizable history. The later read cannot go backward without another write. A correct register protocol needs more than intersection, such as a suitable version and write-back procedure. This example is not Raft’s read algorithm.

Sources and further reading

The explanations and worked answers above stand alone. These references provide the original algorithms, assumptions, and deeper proofs; they are not required downloads.

Lesson browserDistributed consensus, replication, and fault tolerance lessonsPrevious: Replication and the meaning of successNext: Consensus, safety, and the limits of progress