Turn an abstract failure trace into a controlled fault schedule
Map counterexample actions to implementation barriers and durable observations, then reproduce the relevant crash or message schedule without confusing timing luck with evidence.
On this page
The question for today
What you’ll understand
- Identify the first violating action and the essential order in a counterexample.
- Map a crash window to implementation events with an independent effect oracle.
- Explain what reproducing or failing to reproduce an abstract witness establishes.
A counterexample is more useful when its mechanism becomes a reproducible implementation test. The abstract trace identifies a necessary ordering, such as an effect committing before a crash while the deduplication record has not yet committed. Translate that ordering into explicit barriers and observations rather than guessing a sleep duration. The resulting test can expose a real defect, or reveal that an implementation guarantee excludes the abstract behavior and should be reflected in the model.
Extract the mechanism rather than copying every trace detail
Find the first state that violates the checked property, then trace which earlier actions made that state possible. Preserve relevant identifiers, durable writes, ownership epochs, message dependencies, and failure assumptions. Remove irrelevant work only when the smaller trace still exhibits the same violation. Record both the original witness and the reduced schedule so reviewers can see which facts were retained and which were merely incidental search choices.
Separate abstract events from implementation hooks. An action called Commit might correspond to a database transaction, a receiver's durable acknowledgement, or several local operations depending on the model. Establish which concrete event witnesses completion of the promised effect. Logging that a function started is not proof that its durable effect completed. Likewise a client timeout does not prove absence of that effect. An independent oracle should inspect the state whose contract is being tested, rather than relying only on the worker's own success counter or the same log record whose loss is under investigation.
Make the failure window deterministic where possible
Suppose a worker commits an external effect and only later records that request r is complete. If the two facts are not atomically coupled or protected by receiver-side idempotency, a crash between them can leave the effect durable but the retry guard absent. Introduce a test barrier after the effect's verified commit and before the deduplication record's commit, terminate the worker, restore it from the allowed persisted state, and retry the same identifier. Verify both the execution trace and the external effect count. A process kill tests different assumptions from a storage-loss event or a network partition.
A model may intentionally overapproximate failures. If the implementation commits the effect and deduplication fact in one actual atomic consistency domain, the proposed intermediate state may be impossible. In that case, supply evidence for the atomic boundary and refine the model instead of forcing an impossible injection. When effects cross independent systems, a local transaction alone may not couple them; a receiver's stable idempotency contract or another explicit protocol can change the analysis. A compensation action has its own failure and observability semantics and does not automatically restore an at-most-once effect property.
Use the reproduced trace to improve both code and specification
If the implementation reproduces the violation, keep a regression that asserts the independent contract outcome under the controlled schedule. A fix must close the mechanism and survive the same restart or retry semantics, not merely alter a log message or make the race less likely. If the test does not reproduce the abstract witness, determine whether the hook missed the intended boundary, the oracle was incomplete, or an implementation guarantee excluded the behavior. Absence in a few random runs is not a proof of impossibility. Deterministic simulation can explore many controlled schedules while retaining its own environment-model limits.
The reliability instrument shows an availability fact that cannot settle this effect-safety question. Reset, set n=3 and k=1, predict two available replicas and majority threshold two, then Play or Step. Separately Reset, set n=3 and k=0, predict three available and threshold two, then Play or Step. Both settings have a majority, but the model contains no effect commit, deduplication record, or crash-recovery protocol. A reachable majority does not rule out duplicate effects at another boundary; use the counterexample's actual state and oracle to test that property.
Work it through
A single crash can duplicate one logical effect
Request r has no durable deduplication record and durable effect count zero. ExecuteEffect commits one effect; Crash loses only volatile worker state; Recover restores the worker but finds no deduplication record; RetryExecute commits another effect for r. The effect store survives the crash. Count transitions and identify the first safety violation.
ExecuteEffect changes the durable effect count from zero to one. The safety bound still holds, but the deduplication record remains absent because its separate commit has not happened.
Crash and Recover are the second and third transitions. They preserve the external count at one and leave the recovered worker without durable evidence that r already took effect.
RetryExecute is the fourth transition and raises the count to two. The bound N_effect(r)≤1 first fails here. Reproducing the trace needs one crash after verified effect commit and before the missing deduplication commit, followed by a retry of the same identity.
Four transitions and one crash suffice in this model. A correct fix must justify how retries cannot repeat the durable effect under these persistence assumptions.
The living notebook
Explore the model
Interactive lab · reliability
Availability alone cannot prove effect uniqueness
Reset, set n=3 and k=1, predict available=2 and majority=2, then Play or Step. Separately Reset, set n=3 and k=0, predict available=3 and majority=2, then Play or Step. This fixed-state majority instrument has no durable effects, request identities, deduplication, or crash schedule. Its availability readout cannot verify the worked counterexample's safety property.
- Available replicas
- 4 of 5
- Majority needed
- 3
- Majority available?
- Yes
A replica count and a majority threshold, without a consensus protocol. Playback highlights fixed replica states. Having a majority alone does not establish linearizability, durability or failure independence. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forFault tests need the contract's actual commit boundary and an independent outcome oracle.
Pause & reason
Check your understanding
Your turn
Try it yourself
A test plans to crash after an increment commits but before its deduplication record is durable. Its hook fires when the effect RPC is sent, without commit evidence. Explain why this does not enforce the ordering. If two durable increments of three units are later observed for one logical identifier, calculate the excess and assess the at-most-once property.
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Separate RPC initiation from durable completion, then compare one intended increment with two observed increments.
Compare with the solution
An RPC send does not establish CommitEffect≺Crash: it can precede or fail to reach the commit. Add a justified commit observation and a barrier before deduplication durability. Two increments of three produce six units rather than the intended three, an excess of three and two effects for one identifier. That independently observed count violates at-most-once even if the run missed the intended injection window; reconstruct the actual trace.
Keep the idea
Take it with you
- A useful counterexample identifies the necessary event order and first violated property.
- Controlled barriers and independent durable-state oracles are stronger than guessed sleeps.
- Reproduced failures guide fixes; missed reproductions require diagnosis rather than a universal pass claim.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.