A deterministic simulation testing harness, and a Raft implementation built to be broken by it.

A test suite that has never found a bug is indistinguishable from a test suite that cannot find one. So the first thing to measure is not whether the code passes. It is how much searching it takes to find a bug you put there yourself.

Virtual clock, virtual network, virtual disk, seeded fault injection, and two independent oracles - Raft's safety properties and a linearizability checker over the client-visible history. Every run is a pure function of its seed, so a failure comes back as an integer you can replay, shrink, and fix against.

The Raft is not a demo target. It is a real implementation with persistence, elections, log reconciliation and client sessions, and the harness found a genuine bug in it on the first campaign.

Apple M2 Pro, macOS, CPython 3.13. Five nodes, three clients, 6s of virtual time per run, nemesis firing every 80-400ms.

The last two coverage rows matter more than the zero. A campaign that injects nothing passes every seed, and a run that spends its life partitioned passes by doing nothing at all. One run in 2,000 completed no operations; that is reported rather than rounded away.

Twelve defects, each one a mistake that has been made in a real Raft, planted one at a time. The number that matters is not the tick in the column - it is how many seeds it took, because that is the difference between a bug a pre-commit hook catches and one only a nightly run will.

Reproduce with python3 scripts/mutation_report.py. Raw output in results/mutation_report.txt.

Three things are worth reading off that table.

The two invisible ones. kv_no_dedup and local_read are caught only by the linearizability checker, and never by any Raft invariant. Both leave the replicated log perfectly correct - one just contains the command twice, the other never touches the log. Checking the protocol's own properties would report a clean bill of health on both.

The two expensive ones. figure8 and unpersisted_vote need several hundred seeds. Figure 8 of the Raft paper is a five-node interleaving that a uniform random walk reaches rarely, and unpersisted_vote needs a crash inside a 4ms fsync window. These are the bugs that ship.

commit_no_clamp is caught by an exception, not a check. That is reported as crash rather than folded into the invariant column. "It threw" is a symptom; the invariants give a diagnosis, and conflating the two flatters the harness.

Both are in BUGS.md with seeds and configurations. The first is the interesting one.

Seed 1 of the very first campaign reported two nodes applying different commands at the same log index. The cause was one expression in the follower's AppendEntries path:

self.commit_index = min(leader_commit, len(self.log) - 1)   # wrong
self.commit_index = min(leader_commit, prev + len(entries)) # right

Figure 2 of the paper says to clamp to the index of the last new entry, not to the end of the log. The two differ exactly when a follower is holding a divergent tail from an earlier term. To trigger it you need that tail, a partition heal, and a heartbeat carrying no entries arriving before the reconciling ones. Nine of the first sixty seeds found it. No hand-written unit test in this repository would have, because writing that setup down requires already knowing the bug.

The second bug was in the harness itself, and it is the one I would want to be asked about: single_slot survived 400 seeds, and instrumenting the disk showed why - five torn writes in sixty runs. Crashes drawn uniformly over a six-second run essentially never land inside a 4ms fsync window, so a fault that existed in the model was, in practice, unreachable. A fault in the model is not the same as a fault the campaign will reach, and the only way to tell them apart is to plant a bug that needs it.

flowchart LR
  S["seed"] --> R["xorshift64* stream"]
  R --> C["virtual clock<br/>+ event queue"]
  R --> N["network faults<br/>drop / dup / slow / partition"]
  R --> D["disk faults<br/>tear / partial flush"]
  R --> X["nemesis<br/>crash / restart / isolate"]
  C --> K["5 Raft nodes<br/>3 closed-loop clients"]
  N --> K
  D --> K
  X --> K
  K --> I["Raft safety sweep<br/>every 100ms"]
  K --> H["client history"]
  H --> L["linearizability<br/>Wing-Gong per key"]
  I --> V["verdict + reproducing seed"]
  L --> V

python3 -m venv .venv && .venv/bin/pip install -e '.[dev]'

.venv/bin/python -m pytest -q

.venv/bin/python bench/campaign.py --seeds 2000

.venv/bin/python scripts/mutation_report.py --budget 2000

Reproduce a single failure and shrink it:

.venv/bin/python bench/campaign.py --seeds 20 --mutant stale_vote --shrink

A failure at 6,000ms with 5 nodes, 3 clients, 400 operations and 30 faults tells you something is wrong, not what. The shrinker holds the seed fixed and bisects the configuration, keeping a reduction only if the failure category and the name of the failing check are unchanged:

seed 1 still fails at:
  duration      3265
  clients       1
  keys          1
  status        invariant: leader completeness: entry 6 committed in term 2
                is missing from leader n1 in term 4
  tried         19 configurations
  reduced       duration 6000 -> 3265, clients 3 -> 1, keys 2 -> 1,
                duplicate_rate -> 0.0, drop_rate -> 0.0
  shrink took   0.5s

Because everything derives from the seed there is no recorded schedule to delta-debug — changing a knob changes where the randomness gets consumed. So a reduced configuration that still fails may be failing for a different reason. The category check catches most of that and does not eliminate it, which is why the output says "a minimal failing configuration" rather than "the same bug, smaller".

Determinism is a claim about this process, and it is checked as one. The failure mode is set iteration over strings, which is hash-ordered and salted per process. tests/test_determinism.py runs the same seed in two subprocesses under different PYTHONHASHSEED values and compares digests. That is the only way to catch it from outside.

Uniform fault timing does not find durability bugs. Measured, not assumed: five torn writes in sixty runs. The harness now aims crashes at fsync windows with a small fixed probability. Anything else needing a narrow window - a bug reachable only during a specific 2ms of log reconciliation, say - has no such aiming and would show up here as "not caught", which would be a statement about the nemesis and not about the code.

The linearizability checker is exponential and knows it. It takes a step budget and returns UNDECIDED, never OK, when it runs out. Zero of the 2,000 campaign runs hit the budget, but that is a property of three clients and two keys; raising concurrency will hit it, and those runs are not passes.

Nothing here lies. Nodes crash, drop, delay, duplicate, reorder and lose unsynced writes. They do not send inconsistent messages to different peers. That is a different failure model and a different protocol.

No clock skew. Every node reads the same virtual clock. Raft's safety does not depend on synchronised clocks so this costs less than it looks like, but a lease-based read path could not be tested here without adding drift — which is precisely why local_read is caught as a stale read and not as a lease violation.

No snapshots, no membership changes, no real I/O. Restart replays the whole log. Snapshot installation and joint consensus are both well-known sources of bugs and none of them are reachable here. The disk is a dictionary: this finds bugs in reasoning about durability, not in your write syscall handling.

lying_fsync exists and is off. Storage that acknowledges writes it has not committed breaks correct implementations too, because durable persistence is a premise of Raft's safety argument rather than a conclusion of it. It is in the repo so the boundary of what the model can blame the code for is something you can point at.

dst/core.py              seeded RNG, virtual clock, event queue
dst/net.py               partitions, one-way cuts, drop, duplicate, slow links
dst/disk.py              buffer/in-flight/durable split, torn writes, async fsync
dst/faults.py            nemesis, including crashes aimed at fsync windows
dst/history.py           client operation history and run digest
dst/linearizability.py   Wing-Gong search, per key, with an honest budget
dst/shrink.py            configuration bisection at a fixed seed
dst/runner.py            single run, campaign, determinism check
kvraft/raft.py           Raft: elections, replication, Figure 8 rule
kvraft/kv.py             state machine and client session table
kvraft/persist.py        alternating-slot checksummed state file
kvraft/codec.py          length-prefixed encoding, CRC framing
kvraft/invariants.py     Raft's five safety properties
kvraft/mutants.py        the twelve planted defects
kvraft/cluster.py        wiring, closed-loop clients, retry semantics
scripts/mutation_report.py  seeds-to-first-catch table
bench/campaign.py        campaign runner and reporting

• snapshots and log compaction, with the install path as its own mutant class;
• membership changes via joint consensus;
• clock skew, so lease-based reads become testable as leases rather than as stale reads;
• a Byzantine fault model, which is a different protocol — see hotstuff-bft;
• pointing the harness at the C++ storage engines through a subprocess adapter, which trades the virtual disk for a real one and most of the determinism with it.

Each changes what the harness can claim. They are listed rather than implied.

MIT.