research28 min studyLesson 979 in Engineering

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

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.

P:∀r∈R: Ndurable effect(r)≤1P:\quad \forall r\in\mathcal R:\ N_{\rm durable\ effect}(r)\leq1
This example's safety property bounds durable state-changing effects per stable logical request identifier. Counts are nonnegative integers and the effect boundary must be defined independently of response receipt. Other services may require different or additional properties.↔ Scroll wide equations horizontally.

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.

CommitEffect⁡(r)≺Crash⁡,DedupDurable⁡(r,scrash)=false\operatorname{CommitEffect}(r)\prec\operatorname{Crash},\qquad \operatorname{DedupDurable}(r,s_{\rm crash})=\mathrm{false}
The effect has verifiably committed before the injected crash, while r's deduplication fact is absent in the pre-crash durable state. This states the targeted window without requiring a later deduplication commit to occur. The order is causally established, not inferred from unsynchronized timestamps.↔ Scroll wide equations horizontally.

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.

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.

  1. 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.

  2. 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.

  3. 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.

The result

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.

Explore the model

Interactive lab

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.

Availability alone cannot prove effect uniquenessA 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. Current readings: Available replicas: 4 of 5; Majority needed: 3; Majority available?: Yes. All parameters are adjustable with the labeled controls below.Majority available · need 3 of 5Playback highlights fixed statesR1 · upR2 · upR3 · upR4 · upR5 · downCyan mark: majority threshold
AvailableUnavailableMajority threshold
Available replicas
4 of 5
Majority needed
3
Majority available?
Yes
t = 0 s

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.

Check your understanding

A crash-injection test never reproduces an abstract counterexample in ten random runs. What follows?

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.

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.