Skip to content

Software Quality

Deterministic simulation testing

A deterministic simulation testing (DST) harness replaces every non-deterministic input with a controlled equivalent driven by a single seed. The OS scheduler, the network, the clock and the random number generator all come from the harness, and the system under test runs unmodified on top. The simulator can then explore far more schedules and fault patterns than a real deployment encounters; every failure is reproducible by re-running the same seed.

The word simulation here means determinism for replay, not physical fidelity. The scenario simulation used to test autonomous systems is a distinct technique that shares the name: it models sensors and dynamics to explore a driving space, and reproducibility is a convenience there rather than the point.

What it catches

  • Race conditions and ordering bugs at depths example tests cannot reach. The canonical case is the DynamoDB bug that needed a 35-step interleaving to reproduce; TLA+ catches it at the spec, DST catches it on the implementation.
  • Fault-recovery bugs. The simulator injects partitions, kills nodes and drops packets in rare combinations every run.
  • Time-dependent bugs. Leap seconds, clock skew, time-warp during election — the time-and-date bug class. The virtual clock makes these reachable.
  • Resource-exhaustion bugs. Slow disks, full disks, OOM. The simulated environment can pin these on demand.
  • Liveness bugs. Progress invariants ("every accepted request is eventually applied") fail observably under simulated delay.
  • Regression detection. CI re-runs a corpus of past failing seeds, so a fixed bug never returns silently.

By itself DST catches neither bugs in the simulator nor bugs in code that escapes the simulation (the seL4 lesson: simulated I/O that misrepresents the real OS hides the bugs the real OS surfaces). A clean abstraction boundary limits what escapes; running the real system alongside the simulator surfaces divergence between the two.

Tools

DST in industry

  • FoundationDB's Flow simulator — single-threaded scheduler, virtual time, deterministic network. The simulator is FoundationDB's primary correctness tool (Zhou et al. 2021)1.
  • TigerBeetle simulator — single-binary cluster simulation; every commit runs millions of seeded simulations. TigerBeetle is written in Zig, whose allocator-passing convention puts every allocator into the simulated state, which is what makes bit-exact replay tractable.
  • Antithesis — commercial DST as a service; runs the system under test in a hypervisor that virtualizes time and faults; sells the seeded reproducer for any failing run.

Open-source DST frameworks and libraries

  • madsim (Rust) — async-runtime simulator built for Tokio-shaped code; used by RisingWave.
  • shuttle and loom (Rust) — explore in-process interleavings systematically (shuttle by PCT-style randomization, loom by bounded interleaving enumeration) rather than by random whole-system seeds, which makes them systematic concurrency testing applied to Rust rather than DST proper; one harness often hosts both.
  • moonshot, mailbox, fastsim (Erlang/Elixir) — niche simulators in the BEAM ecosystem.
  • Jepsen (Kingsbury) — not DST, but the closest open-source alternative: black-box concurrency testing against real distributed systems, and the largest public record of distributed-system bug discoveries.

Building blocks

  • Property-based testing frameworks (Hypothesis, fast-check, proptest) — most DST harnesses run on top of a PBT generator that produces schedules and faults.
  • Seeded RNGs and virtual clocks — the primitives every DST harness rests on, and small enough to implement by hand.

When to use, when not

Use:

  • Distributed systems with non-trivial coordination — consensus, replication, leader election, gossip.
  • Stateful concurrent in-process code where rare interleavings hide bugs: lock-free data structures, schedulers, work-stealing queues.
  • Systems where bug replayability is the dominant cost.
  • Long-running soak tests, where millions of simulated hours give a favorable cost per bug found.

Don't:

  • For pure logic with no concurrency. Property-based testing carries less ceremony.
  • When the abstraction boundary is fuzzy. A DST harness that doesn't fully control I/O or time produces flaky-by-design results.
  • As a substitute for formal methods on the protocol. DST tests the implementation; FM tests the spec. Compose them.

Evidence

FoundationDB reported running 5 to 10 million simulation runs a night on its test cluster, each simulating a whole cluster for between five minutes and an hour or two of virtual time. Years of that put the project's cumulative testing at an estimated equivalent of trillions of real-world CPU-hours (Wilson 2014)2.

The bugs FoundationDB reported finding outside the simulated boundary — a power-safety bug in ZooKeeper, and an apt install that never called fsync, leaving the configuration files missing or corrupt after a power cut — came from power-cycling real hardware rather than from the simulator (Wilson 2014)2.

No controlled study measures DST's fault-detection rate; the evidence is a single industrial record, not a comparative result.

Classification

  • Quality dimensions: Reliability, Functionality.
  • Area: Distributed systems, consensus protocols, replicated databases, concurrent and lock-free data structures.
  • Guarantee: Empirical, but replayable — the seed turns any failing run into a deterministic reproducer.

Referenced by

References

  1. Zhou, Jingyu, Meng Xu, Alexander Shraer, et al. 2021. "FoundationDB: A Distributed Unbundled Transactional Key Value Store." Proceedings of the 2021 International Conference on Management of Data (SIGMOD '21), 2653–66. https://doi.org/10.1145/3448016.3457559. ↩

  2. Wilson, Will. 2014. Testing Distributed Systems w/ Deterministic Simulation. https://www.youtube.com/watch?v=4fFDFbi3toc. ↩↩