Deterministic Simulation Testing(WIP)

[seonWKim]

Deterministic Simulation Testing (DST) Proposal

What is DST?

Deterministic Simulation Testing (DST) is a technique for testing distributed systems by simulating chaotic interactions — network delays, message reordering, process crashes — over extended periods of simulated time. The system randomly explores a vast state space, but every choice flows from a single RNG seed, meaning any failure can be perfectly replayed.

Why DST for EastGuard?

Our SWIM protocol implementation has several sources of non-determinism that make bugs hard to reproduce:

• Timer-driven logic: SwimActor relies on tokio::time::interval and tokio::spawn + time::sleep for protocol ticks, ACK timeouts, and suspect timeouts. The exact interleaving of these timers is unpredictable.
• Random peer selection: StdRng::from_entropy() makes probe targets non-reproducible across runs.
• UDP transport: TransportLayer binds a real UdpSocket, so tests require actual network I/O with all its timing variability.

DST addresses this by giving us:

• Reproducibility: A single seed reproduces the exact execution path — network delays, peer selection order, timeout interleaving. Heisenbugs become reproducible on any machine.
• Failure injection: We can simulate packet loss, reordering, and node crashes to verify that SWIM correctly detects failures, refutes false suspicions, and converges membership state.
• Early detection: Complex issues like gossip not propagating or incorrect incarnation handling surface during seed-fuzzing, not in production.

How to Introduce DST

Step 1: Make SwimActor a pure state machine

Decouple protocol logic from the async runtime, following tikv/raft-rs's pattern:

impl SwimActor {
    pub fn tick(&mut self) { /* protocol round */ }
    pub fn step(&mut self, event: InboundEvent) { /* handle packet/timeout */ }
    pub fn drain_outbox(&mut self) -> Vec<OutboundPacket> { std::mem::take(&mut self.outbox) }
}

The actor owns no channels, spawns no tasks, and calls no async functions. A thin driver (run_swim) handles I/O in production.

Step 2: Control all sources of non-determinism

Source	Current	DST-ready
Execution	Multi-threaded Tokio runtime	Single-threaded runtime with start_paused = true
Entropy	StdRng::from_entropy()	StdRng::seed_from_u64(seed) injected at construction
Time	std::time::Instant, real sleeps	tokio::time::Instant with paused time; time only advances on explicit tokio::time::advance()
I/O	Real UdpSocket in TransportLayer	In-memory network simulator behind a trait
HashMap ordering	Randomized default hasher	Seeded RandomState or BTreeMap for deterministic iteration

Step 3: Build an in-memory network simulator

Replace TransportLayer with a simulator that models packet delivery:

struct SimNetwork {
    rng: StdRng,
    in_flight: Vec<(SimPacket, Duration)>, // packet + simulated delay
    drop_rate: f64,
}

The simulator decides per-packet whether to deliver, delay, reorder, or drop — all seeded from the same RNG.

Step 4: Verification

• Run tests with the same seed. Compare TRACE-level logs byte-for-byte — they must be identical.
• Fuzz with random seeds in CI (e.g., 1000 seeds per PR) to explore the state space.
• Assert invariants after every step: membership convergence, no alive node falsely marked dead, refutation always succeeds within one round.

References

• Turso DST — Deterministic Simulation Testing
• Turso Simulator README
• tikv/raft-rs — Pure state machine Raft