Study guides · Intermediate

Quorum intersection and fault tolerance

Enumerate five-member read/write sets and separate overlap arithmetic from version selection, durability, partitions and membership changes.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Separate set intersection from a value guarantee
  2. Calculate overlap for concrete subsets
  3. Show an old first response despite intersection
  4. Count available members under crashes and partitions
  5. Treat membership changes as a separate protocol
  6. Define what the executable model verifies
  7. Distinguish repair from the current read contract
  8. Solve the equality and first-response exercises
  9. Ask Logeia about this articleCheck your understanding

Separate set intersection from a value guarantee

Replicate one key across A, B, C, D and E. A write waits for W responses and a read for R. When R+W>N, subsets drawn from the same fixed N members intersect. For N=5 and R=W=3, they share at least one member. That is a set property. Which version it returns, what an acknowledgment durably means and how concurrent writes are ordered require additional protocol rules. Read replication and consistency first.

Draw actual read and write sets and separate the conclusion supplied by intersection from those requiring more machinery. Naming a quorum does not make arbitrary reads return the latest value. Consensus protocols such as Raft combine overlapping majorities with term, log, vote and commitment rules. A count calculation does not replace those conditions. The goal is to use intersection accurately while recognizing the remaining obligations for a complete consistency contract.

Calculate overlap for concrete subsets

For write set {A,B,C} and read set {C,D,E}, C is shared. Disjoint three-member sets would require six members, impossible within five. The minimum overlap is R+W-N, one here. With R=2 and W=3, sets {A,B,C} and {D,E} are disjoint. Equality R+W=N therefore does not guarantee overlap; the strict inequality matters.

Write-write overlap uses the separate condition 2W>N. Two three-member write sets also intersect in five members, but a shared node could accept both concurrent writes unless the protocol restricts its behavior. A once-per-term voting rule illustrates how node behavior adds meaning to overlap. Storage acknowledgments and election votes can use similar set mathematics while representing different actions. Explain the operation at the shared node instead of transferring a vote guarantee directly into a value-selection guarantee.

NRWMinimum read/write overlap
5331 member
5230 members
5151 member

Show an old first response despite intersection

Suppose version two, new, is durably stored at A, B and C and all three acknowledgments complete the write. D and E still hold version one, old. A later read contacts D, A and E, but D replies first. The sets intersect at A, yet returning the first response returns old. Sending to three nodes is not the same as implementing a three-response read rule. Specify collection and version selection explicitly.

In a single-write model, collecting all three responses and selecting a comparable newest version finds A's version two. Concurrent writers generating the same local version number or partially completed writes introduce further obligations. Version assignment, failed-write visibility and repair must be designed. Largest wall-clock timestamp also depends on clock assumptions. A max expression over responses is not a complete implementation or proof of linearizability. The example isolates one missing rule without pretending that supplying it solves every distributed register problem.

Count available members under crashes and partitions

With five fixed members and a three-response requirement, any two stopped nodes leave enough members if the remaining three are reachable. Three stopped nodes leave too few. Alive is not equivalent to mutually reachable or reachable from a caller. In a partition {A,B,C} versus {D,E}, only the first side forms a three-member set under this simple majority policy. Admitting independent minority writes requires a different consistency contract.

Allowing replacement nodes outside the original replica set can invalidate the fixed-set premise. When reading systems such as Dynamo, check canonical replica membership and the handling of substitutes, rather than applying the original overlap inequality to a sloppy quorum by name alone. A readable set also does not establish durable presence of every required version. State failure model, membership and acknowledgment meaning together. Set availability is one component of the answer, not a complete guarantee of recovered data.

Treat membership changes as a separate protocol

Old members {A,B,C,D,E} and new members {F,G,H,I,J} can each form a local majority while sharing none. Satisfying R+W>5 within each configuration does not connect their histories during migration. A membership-change protocol defines how old and new configurations overlap logically and when the old one stops authorizing work. Joint-majority procedures have additional rules; changing N in a formula is not their implementation.

Distinguish replication membership from sharding. N may mean the replica set responsible for one key, not every server in the system. Nodes responsible only for another shard cannot supply the required overlap for this key. On a large placement diagram, first circle the target key and its responsible members. The rebalancing guide then changes placement without conflating it with the consensus rules needed to coordinate authoritative ownership and replicated history.

Define what the executable model verifies

The companion experiment enumerates all three-member subsets and asserts their minimum overlap. It also checks remaining-member counts, a three-two partition and an old-first-response counterexample. This is a deterministic set and version model, not network fault injection against a Raft implementation. Passing combinations do not demonstrate persistence or election safety. The assertions define the evidence boundary.

Evaluating a real store additionally requires acknowledgment durability, restart state, lost write responses, concurrent writes and reconfiguration histories. Distinguish stopped processes from disconnected communication and judge reads against the required consistency model. Quorum arithmetic organizes those prerequisites. Applications may deliberately choose a weaker contract for availability or latency, but should describe permitted outcomes instead of using latest as an undefined promise. A clear weaker guarantee is more useful than an unsupported strong one.

Distinguish repair from the current read contract

When a read finds old and new replicas, read repair can update older copies for future reads. Planned repair does not authorize returning the first stale value as current. Value selection for this request and subsequent replica maintenance are different operations. Lost repair acknowledgments also need a stated completion meaning. Repair cannot retrospectively make an already returned stale response satisfy a stronger contract.

Likewise, three acknowledgments with two durable saves and one memory-only receipt do not supply the same restart premise as three durable saves. Inspect the meaning of each response, not just W's numeric label. A complete history aligns fixed membership, comparable versions, persistence, response collection and selection before checking the additional steps required by the selected protocol. This explains why a one-line inequality is useful but insufficient for an operational guarantee. It also helps classify a failed experiment: missing overlap, weak acknowledgment, incomplete collection and incorrect selection call for different corrections, even when a user observed the same old value.

A restart can remove a memory-only acknowledged version even though the node remains a member. Membership and retained value are separate facts.

Solve the equality and first-response exercises

For N=5, R=2 and W=3, overlap is not guaranteed: {A,B,C} and {D,E} are disjoint. Raising R to three guarantees intersection but still requires durable acknowledgments and correct value selection. With R=1 and W=5, overlap exists but one unreachable member prevents completing writes under that policy. Changing counts alters both the available histories and the conditions for progress.

After version two reaches A, B and C, read D, A and E with D first. The simple-model answer is to honor three-response collection and version comparison rather than return old immediately. That still is not a proof of every concurrent linearizable history. The learning outcome is separating membership, persistence, collection and selection. Continue to distributed transactions to study a different boundary: coordinating commitment across multiple resources.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Understand the systems behind the web · STEP 18

Choose a learning path