Deterministic lockstep

Deep dive

How it works

Parts:

• Input scheduler — stamps each local command with tick T + D and sends it reliably to every peer.
• Input table — per tick, one input per player; empty no-ops count.
• Deterministic simulation — pure function of (state, inputs of tick t); no clocks, no local randomness.
• Desync detector — state hash exchanged every N ticks.

1. Time advances in fixed simulation ticks; commands are grouped into turns (one or more ticks).
2. A local command issued during tick T is scheduled for tick T + D (input delay D) and sent to all peers (or a relay), reliably and redundantly.
3. Before simulating tick t, a peer needs the input of every player for t (an empty "no-op" input counts and must be sent too). If any is missing, it stalls.
4. Simulate tick t with inputs ordered by player id. Never use wall-clock time, local randomness or unsynchronized state.
5. Every N ticks hash the game state and exchange hashes; a mismatch is a desync. Dump state on both sides to find the first differing field.
6. Adapt D: measure RTT and frame time per peer; raise D when peers stall, lower it when the buffer runs deep.

tick:     100   101   102   103   104
local A:  cmd issued at 100 -> scheduled for 103 (D = 3) -> sent now
peer B:   receives A@103 at ~101.5 -> has all inputs for 103 before it gets there -> no stall

Code

use std::collections::BTreeMap;

#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
pub struct Input { pub cmd: u8, pub x: i16, pub y: i16 } // cmd 0 = no-op, still sent

/// Q16.16 fixed point: identical results on every CPU and compiler.
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
pub struct Fx(pub i32);
impl Fx {
    pub const ONE: Fx = Fx(1 << 16);
    pub fn mul(self, o: Fx) -> Fx { Fx(((self.0 as i64 * o.0 as i64) >> 16) as i32) }
    pub fn add(self, o: Fx) -> Fx { Fx(self.0.wrapping_add(o.0)) }
}

pub trait Sim { fn step(&mut self, inputs: &[Input]); fn hash(&self) -> u64; }

pub struct Lockstep<const P: usize> {
    pub tick: u32,          // next tick to simulate
    delay: u32,             // input delay in ticks
    me: usize,
    pending: BTreeMap<u32, [Option<Input>; P]>,
}

impl<const P: usize> Lockstep<P> {
    pub fn new(me: usize, delay: u32) -> Self {
        let mut pending = BTreeMap::new();
        // Ticks before `delay` have no real input: seed them with no-ops for everyone.
        for t in 0..delay { pending.insert(t, [Some(Input::default()); P]); }
        Lockstep { tick: 0, delay, me, pending }
    }

    /// Schedule a local input; returns (tick, input) to send to every peer (redundantly).
    pub fn local_input(&mut self, inp: Input) -> (u32, Input) {
        let t = self.tick + self.delay;
        self.pending.entry(t).or_insert([None; P])[self.me] = Some(inp);
        (t, inp)
    }

    pub fn remote_input(&mut self, player: usize, t: u32, inp: Input) {
        if t < self.tick { return; } // duplicate of an already simulated tick
        let slot = &mut self.pending.entry(t).or_insert([None; P])[player];
        debug_assert!(slot.is_none() || *slot == Some(inp), "peer changed a sent input");
        *slot = Some(inp);
    }

    /// Advance as far as complete input sets allow. Returns state hashes to exchange.
    pub fn advance<S: Sim>(&mut self, sim: &mut S, hash_every: u32) -> Vec<(u32, u64)> {
        let mut hashes = Vec::new();
        while let Some(set) = self.pending.get(&self.tick) {
            if set.iter().any(|i| i.is_none()) { break; } // stall: someone's input is missing
            let inputs: [Input; P] = set.map(|i| i.unwrap()); // ordered by player id
            sim.step(&inputs);
            self.pending.remove(&self.tick);
            self.tick += 1;
            if self.tick % hash_every == 0 { hashes.push((self.tick, sim.hash())); }
        }
        hashes
    }
}

/// Example sim: units move toward targets in fixed point; Vec order is deterministic.
pub struct World { pub units: Vec<(Fx, Fx, Fx, Fx)> } // x, y, target x, target y
impl Sim for World {
    fn step(&mut self, inputs: &[Input]) {
        for (p, i) in inputs.iter().enumerate() {
            if i.cmd == 1 {
                let u = &mut self.units[p];
                u.2 = Fx((i.x as i32) << 16);
                u.3 = Fx((i.y as i32) << 16);
            }
        }
        let k = Fx(Self::RATE);
        for u in &mut self.units {
            u.0 = u.0.add(Fx(u.2 .0 - u.0 .0).mul(k)); // move 1/8 of the way per tick
            u.1 = u.1.add(Fx(u.3 .0 - u.1 .0).mul(k));
        }
    }
    fn hash(&self) -> u64 { // FNV-1a over the canonical state
        let mut h = 0xcbf2_9ce4_8422_2325u64;
        for u in &self.units {
            for v in [u.0 .0, u.1 .0, u.2 .0, u.3 .0] {
                for b in v.to_le_bytes() { h = (h ^ b as u64).wrapping_mul(0x100_0000_01b3); }
            }
        }
        h
    }
}
impl World { const RATE: i32 = 1 << 13; }

Complexity and constants

• Bandwidth per peer: players × inputs per second × input size. 8 players × 10 turns/s × 8 bytes ≈ 5 kbit/s, whether there are 10 or 10 000 units.
• CPU: every peer simulates everything; the slowest machine caps the tick rate (Factorio and StarCraft II slow the game for everyone when one peer can't keep up).
• Felt latency: D ticks + frame time; at 20 ticks/s and D = 3 that is 150 ms, masked with immediate local acknowledgment (sound, animation) of the command.
• State hash every 1-5 s: cost of hashing the state (MBs at GB/s, order of ms); hash a subset per tick if that is too slow.

Efficiency

Cost: bandwidth per peer is players × turns/s × input size, e.g. 8 × 10 × 8 B ≈ 5 kbit/s regardless of unit count; CPU is the full simulation on every peer, so the slowest machine sets the tick rate. A state hash costs order of ms for MBs of state. Bound: slowest peer's CPU and one-way latency.

Levers:

• Group several ticks into one turn — fewer packets (Bettner and Terrano, GDC 2001) — high tick rates on slow links.
• Adapt the input delay D from measured RTT and frame time — avoids both stalls and wasted responsiveness — variable networks.
• Hash a subset of state per tick instead of everything every N ticks — spreads the cost (order of) — large worlds.
• Relay server collecting inputs per turn — one upstream flow per peer, drops late inputs — NAT-heavy or many peers.
• Bit-exact fixed-point math (deterministic-fixed-point-math) — removes cross-CPU drift — heterogeneous hardware.

Naive → standard → state of the art:

• Send full state each tick · O(units) bandwidth
• Lockstep with input delay D and hashed state checks · O(players × input) bandwidth, D ticks of delay
• Lockstep plus speculative prediction and rollback (rollback-netcode) · no input delay, O(r) re-simulated frames per misprediction

Implementation notes

• Floats: IEEE 754 +, −, ×, ÷ and sqrt are correctly rounded and deterministic for the same precision. Problems come from x87 80-bit intermediates (32-bit x86), FMA contraction (-ffp-contract=off, no mul_add), -ffast-math, SIMD paths that reorder sums, and libm transcendentals (sin, exp, pow) that differ by platform. Fixed point or a bundled software math library avoids all of it.
• Collections: Rust HashMap iteration is randomized per process; use BTreeMap, Vec, or a fixed-seed hasher with insertion-ordered maps. Same for Go maps and Python sets of objects.
• RNG: one seeded PRNG per match inside the simulation state; never rand::thread_rng().
• Transport: inputs must arrive, so send each input in every packet until acked (reliable UDP); a client-server relay in the middle simplifies NAT traversal and drops cheaters' late inputs.
• Joining late / reconnecting: send a serialized snapshot plus the input log since it; keep serialization canonical.
• Desync debugging: log per-tick hashes of subsystems (units, pathing, RNG state); bisect to the first differing tick and field.

Pitfalls

• One non-deterministic source (uninitialized padding hashed, pointer addresses used as sort keys, multithreaded simulation without fixed reduction order) desyncs games minutes later.
• Different builds on different peers (compiler flags, CPU-specific code paths like AVX vs SSE) produce different floats; ship identical binaries and check build hashes at handshake.
• UI code reading the simulation is fine; UI code writing to it outside the input path breaks determinism.
• Turn length fixed for the worst case wastes responsiveness; adapt D from measured latency.
• Pausing and speed changes must themselves be inputs.

Variants and alternatives

In production

• Games: Age of Empires (I, II), StarCraft and StarCraft II, Warcraft III, Supreme Commander, Factorio, Command & Conquer series; replays in most of these are input logs.
• Databases: Calvin replicates transaction inputs instead of effects after fixing a global order, and executes them in parallel on all replicas; FaunaDB is built on it (Jepsen analysis).
• Finance: LMAX rebuilds its business-logic processor by replaying the journaled input event stream on top of a nightly snapshot (restart under a minute).
• Replicated services: the state machine approach (Schneider, 1990) is the general form; Aeron Cluster runs deterministic services on a Raft-replicated log.

Implementations

Sources

• Bettner, Terrano, 1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond, GDC, 2001. article
• Fiedler, Deterministic Lockstep and Floating Point Determinism, gafferongames.com, 2014 and 2010. post · post
• Factorio developers, Friday Facts posts on multiplayer and desyncs, factorio.com. blog
• Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys, 1990. paper
• Thomson, Diamond, Weng, Ren, Shao, Abadi, Calvin: Fast Distributed Transactions for Partitioned Database Systems, SIGMOD 2012. paper
• Fowler, The LMAX Architecture, martinfowler.com, 2011. article