Concepts and theorems · Intermediate

Quorums: distinguish intersecting responses from a consistency guarantee

Calculate intersecting replica sets and explain why overlap alone does not prove a linearizable read.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Start with a fixed replica set
  2. Compute an intersection
  3. Overlap is only one protocol ingredient
  4. Distinguish storage quorums from consensus
  5. Enumerate intersecting sets
  6. Separate node counts from failure domains
  7. Ask Logeia about this articleCheck your understanding

Start with a fixed replica set

A quorum is a participation condition for advancing an operation. Begin with a fixed set of N replicas. Suppose a write waits for responses from W replicas and a read waits for R. If R + W exceeds N, a read set and a write set drawn from that same population must intersect. The arithmetic concerns sets, not the interpretation of their contents. It has not yet explained which version a responder holds, how concurrent writes are ordered, or which failures a completed response survives.

Intersection connects the participants that accepted one operation with those consulted by another. It is more than a convenient arithmetic threshold for failure-free runs. However, the meaning of an acknowledgement matters: receiving a value in volatile memory differs from persisting it before replying. If a node forgets acknowledged information after a crash, a set intersection alone does not recover that information. State both the participant sets and the storage condition represented by each counted reply before deriving a system-level guarantee.

Compute an intersection

Let N = 5 and W = R = 3. A write acknowledged by A, B and C intersects a later read answered by C, D and E at C. If R were two instead, D and E could answer without overlapping the write set. Majorities intersect, but a partition that cannot reach three members cannot complete an operation requiring that majority. Quorum arithmetic therefore does not promise progress on both sides of a split. Specify the operation, shared membership and completion boundary before comparing numbers from two configurations.

Intersection does not imply that every response is new. After version seven is written to A, B, and C, a read from C, D, and E could receive version seven only from C and version six from D and E. Choosing the most common value would then return the older version. This illustrates why a protocol needs an explicit version-selection rule instead of a vote over raw values. The example establishes a limitation of the threshold calculation, not a complete algorithm for implementing a linearizable register.

Overlap is only one protocol ingredient

Finding a newer version at the intersection requires a protocol for retaining versions and selecting among responses. Concurrent writes, delayed older messages and partially completed writes complicate the story. Version ordering, recovery, read repair and membership changes all matter. R + W > N alone does not prove linearizability. In particular, a sloppy quorum can place data on alternative reachable nodes rather than the same fixed replica population. Borrowing the strict-intersection formula without checking those placement rules can produce an invalid consistency argument even when the numerical thresholds appear sufficient.

Selecting the largest version still leaves incomplete operations to handle. A writer might update only one replica before failing to reach its acknowledgement threshold, yet a later read could encounter that version. Some protocols use a read repair or write-back phase to preserve the required ordering of later observations. Analyze executions containing incomplete writes as well as successful ones. A proof cannot assume away the failure cases for which the distributed protocol was introduced. Versioning, storage, recovery, and read phases must fit the claimed consistency model.

Distinguish storage quorums from consensus

Consensus algorithms such as Raft also rely on majority intersection, together with term, voting and log rules. The shared word majority does not make their guarantees identical to a quorum-based storage interface. Operational reasoning must include reachable participants, deadlines and failure domains, not just a count of failed machines. Three replicas on one power supply are not three independent fault domains. State the required consistency and availability outcomes, then check both thresholds and protocol behaviour. The useful question is what this entire design guarantees under its assumptions, rather than which isolated number is largest.

Membership changes require another argument. An old group of five and a largely different new group of five can each form a three-node majority without the two selected sets intersecting. A safe reconfiguration protocol must connect decisions across configurations; the fixed-population formula is insufficient. Geographic placement also matters. It can separate failure domains while increasing the latency of the paths whose replies are awaited. Design participation thresholds together with configuration transitions, storage semantics, and physical placement rather than treating the replica count as an isolated availability setting.

Enumerate intersecting sets

There are ten ways to choose three participants from A, B, C, D, and E. Every pair of those three-member sets intersects: two disjoint sets would require six different members, exceeding the population of five. A two-member read set can be disjoint from a three-member write set, for example {D,E} and {A,B,C}. Equality R+W=N therefore does not force intersection; the strict inequality matters. Enumerating the small set combinations is a useful arithmetic check. It does not enumerate value versions, acknowledgement durability, incomplete writes, or the client’s selection protocol. Report such a test as verification of the set calculation, not as an end-to-end consistency proof for a storage system.

Separate node counts from failure domains

A five-member configuration that waits for three responses can meet its numeric threshold while three members remain reachable. If three depend on one power supply or network device, one infrastructure failure can remove that threshold. Even with three reachable members, a request can miss its deadline when their responses arrive too late. Record numeric fault tolerance, correlated failures, reachability, and response deadlines separately. Reducing the read threshold can shorten waiting but also changes which acknowledged write sets a read must intersect. Evaluate a configuration change against the required guarantee and actual protocol, not only against an attractive latency measurement. Node counts are one part of the reliability model, not a complete description of it.

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

Learn this in order

Understand the systems behind the web · STEP 17

Choose a learning path