Experiments and implementations · Intermediate

Check quorum sets and stale responses

Enumerate five-member subsets and version states to distinguish intersection, availability, insufficient storage acknowledgments and stale-first selection.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Enumerate every three-member subset
  2. Separate unavailable members from partition sides
  3. Construct two different missing-rule examples
  4. Map assertions to the reported result
  5. Repair one missing premise at a time
  6. Solve the smaller-read-set exercise
  7. Ask Logeia about this articleCheck your understanding

Enumerate every three-member subset

Build every three-member subset of fixed members A through E, using N=5 and R=W=3. Read the quorum guide first. This is a deterministic Python model of sets and stored versions, not a running network or fault-injected Raft cluster. First verify intersection, then identify the additional rules needed for response order and value selection.

There are ten subsets and one hundred read/write pairs. Assertions require every pair to overlap and minimum overlap to equal one. This is stronger than examining only one convenient pair. If you change N, verify that R and W actually select valid subsets. An empty collection making all return true is not a safety result for a quorum that cannot exist. The input domain belongs beside the asserted property.

Separate unavailable members from partition sides

Save quorum.py and run it with Python 3.12 or later, using only the standard library. The available sets are all members, ABC and AB. ABC has enough members for both thresholds; AB does not. Reachability is supplied as input rather than measured from a network. A live but unreachable node is not usable in the caller's responding set.

In a three-two partition, ABC can form three while DE cannot. No policy authorizes minority writes here. Adding substitute nodes changes fixed membership and requires a different analysis. There is no randomness, sleep or server startup; identical input produces identical results. This isolates the set calculation from the additional evidence required to characterize real process failure and communication behavior.

Construct two different missing-rule examples

First place new only at B and C while A, D and E retain old. Reading A, D and E intersects the intended set ABC at A, but durable W=3 for version two was not satisfied. Old output does not refute a correctly acknowledged three-member write; the example intentionally violates the acknowledgment premise. Separate intended targets from members actually confirming the required version.

Then update A too, so version two exists at A, B and C. Read in order D, A, E. The maximum collected version is new, while the first reply is old. This second example satisfies storage membership but exposes incorrect first-response selection. Name the missing assumption in each case rather than calling both a generic quorum failure. Tuple comparison models simple version numbers here, not a complete ordering protocol for concurrent writers.

python
from itertools import combinations
nodes=set('ABCDE');R=W=3
reads=[set(x) for x in combinations(sorted(nodes),R)]
writes=[set(x) for x in combinations(sorted(nodes),W)]
assert all(r&w for r in reads for w in writes)
assert min(len(r&w) for r in reads for w in writes)==1
for alive in [set('ABCDE'),set('ABC'),set('AB')]:
    can_read=len(alive)>=R;can_write=len(alive)>=W
    print('alive',''.join(sorted(alive)),'read',can_read,'write',can_write)
assert len(set('ABC'))>=W and len(set('DE'))<W
versions={'A':(1,'old'),'B':(2,'new'),'C':(2,'new'),'D':(1,'old'),'E':(1,'old')}
write_set=set('ABC');read_order=['A','D','E']
assert set(read_order)&write_set=={'A'}
first=versions[read_order[0]]
newest=max(versions[n] for n in read_order)
assert first==newest==(1,'old')
print('intersection exists, but write of version 2 was acknowledged by B,C only')
# This deliberately violates durable W=3 acknowledgment for version 2.
# A second counterexample keeps W=3 but chooses the first returned stale value.
versions['A']=(2,'new');read_order=['D','A','E']
assert max(versions[n] for n in read_order)==(2,'new')
assert versions[read_order[0]]==(1,'old')
print('durable W=3, read quorum intersects; first response is still old')

Map assertions to the reported result

A passing run reports read/write possible with five and three available members, and impossible with two. It checks all set pairs and exact versions in both examples. The published input has executed successfully. There is no timing or network measurement. Dictionary contents are supplied state, not proof of durability after restart.

Annotate which node returns which version. Updating A restores the storage premise, while changing reply order distinguishes first response from maximum version. A real implementation still needs collection deadlines, failed-write visibility, version assignment and repair rules. The compact model does not erase those obligations. Its useful result is locating exactly which premise supports each assertion and which state change invalidates a proposed inference.

Repair one missing premise at a time

First repair the storage example by putting new at A, bringing version-two holders to three. That change alone does not repair returning D's first old response. Next change collection and selection so the full response set yields new in this single-update model. Saving both intermediate dictionaries explains why two independent rules were needed. Repairing everything at once and showing only a final success would hide that distinction.

Changing R to two gives another independent failure: a DE read can miss new even when ABC all durably hold it. Organize checks into membership intersection, stored versions, response collection and returned value. The current model includes no concurrent writes, node restart or membership transition, so their safety remains outside execution coverage. This does not weaken the asserted set property; it identifies which additional histories a real protocol must handle. A useful follow-up begins with a predicted counterexample, changes one condition and records which assertion should fail. If an assertion fails for a different reason, inspect the input domain before claiming a consistency defect. For example, an impossible R produces no valid read sets and cannot be interpreted as an ordinary available read configuration. The small model is valuable when it helps formulate these exact questions, not when its successful exit is expanded into a blanket certification of quorum storage.

Use each failed assertion to identify the changed premise before revising the protocol. A count error, a missing stored version and a response-selection error should remain separate diagnoses. Their identical visible old result does not make them the same fault.

Solve the smaller-read-set exercise

Set R=2 and W=3. Write ABC and read DE are disjoint, so the original all assertion should fail. That failure correctly detects a changed guarantee. Do not delete the assertion merely to make the changed input pass; state the new contract. With W=5 and R=1, intersection returns but one unavailable member blocks writes.

Does replacing first-response return with maximum version prove linearizability? It fixes this simple example, not every concurrent history, failed write or membership change. Name what was and was not checked. No database or process needs cleanup. When moving toward a real implementation, ask how each state supplied to this model will be established and observed in the actual system.

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