Designing a Deterministic State Graph for Peer-to-Peer Lockstep

When your multiplayer simulation must produce identical results across every peer with no central authority, lockstep synchronization is the hammer. But the nail is the state graph: a directed structure that encodes every legal transition the simulation can take. If that graph isn't deterministic — meaning the same input always leads to the same output, regardless of platform, compiler, or timing — your peers will silently diverge, and the game will desync into chaos. This guide is for engineers who have already shipped a real-time networked project and are now trying to fix the last 1% of desync bugs, or are designing a new lockstep system from scratch. We will walk through the exact graph design, the tools that help, the traps that hurt, and the trade-offs you face when latency or bandwidth constraints force you to bend the rules.

Why Deterministic State Graphs Matter for Lockstep

Lockstep works because every peer runs the same simulation forward from the same initial state, consuming the same sequence of inputs. If any peer produces a different internal state after processing input N, the entire game is broken. The state graph is the formal map of all possible simulation states and the deterministic transitions between them. Without a well-defined graph, you cannot guarantee that two peers executing the same commands will end up in the same place.

What goes wrong without it? Teams often start with a loose simulation where entities update in arbitrary order, floating-point math gives slightly different results on different CPUs, and hash maps iterate in non-deterministic order. The result is a desync that only appears after minutes of gameplay, deep in a replay that is nearly impossible to debug. We have seen projects where a single non-deterministic random number generator (RNG) seed caused a cascade of failures: one peer's unit dodged left, another's dodged right, and within seconds the entire battle was unrecoverable.

The state graph forces you to enumerate every possible state variable and every transition rule. It makes hidden assumptions visible. For example, if your simulation uses a physics engine that resolves collisions in a non-deterministic order, the graph will not be acyclic in practice — it will have cycles of feedback that depend on frame timing. By designing the graph first, you catch these issues before writing a single line of networking code.

Core Mechanism: Directed Acyclic Graph of Transitions

At its heart, a deterministic state graph is a directed acyclic graph (DAG) where each node is a snapshot of the simulation state (positions, health, cooldowns, seeds) and each edge is a deterministic function that maps one state to the next given an input. The graph is acyclic because time only moves forward; you never transition to a past state. In practice, you often implement this as a linear sequence of frames, but the DAG model helps when you have branching due to speculative execution or rollback.

Why It Works: Causality and Reproducibility

The magic of lockstep is that every peer walks the same path through the state graph. Because the graph is deterministic, the path is entirely determined by the initial state and the input sequence. This means replays are trivial: just re-apply the same inputs from the same start. Debugging becomes a matter of comparing two peers' paths and finding the first divergence. The graph gives you a clean abstraction: if you can serialize the current node (state snapshot) and the list of edges (inputs), you can reconstruct everything.

Prerequisites and Context to Settle First

Before you design the graph, you need to lock down three things: numeric representation, random number generation, and iteration order. These are the three horsemen of lockstep desync.

Fixed-Point or Deterministic Floating-Point

IEEE 754 floating-point is not deterministic across platforms — different CPUs, compilers, and optimization levels can produce different results for the same operation. The standard solution is fixed-point arithmetic (using integers scaled by a constant factor) or a software floating-point library that guarantees identical results. For many games, 32-bit fixed-point with 16 fractional bits is enough for positions, while angles might need 32-bit integers representing degrees in a custom unit. If you must use floats, disable FMA (fused multiply-add) and set the rounding mode explicitly on all peers.

Reproducible Random Number Generation

Every random number in the simulation must come from a deterministic RNG that is seeded identically on all peers at startup, and advanced by the same number of calls in the same order. Use a simple, well-tested generator like xorshift128+ or PCG. Never use system-provided rand() or hardware random sources. The RNG state must be part of the state graph node — serialize it with the rest of the simulation state.

Deterministic Container Iteration

Hash maps (unordered_map in C++, HashMap in Rust) iterate in an undefined order by default. This is a common source of desync. Use sorted containers (map, BTreeMap) or iterate over a separate sorted key list. If you must use hash maps for performance, maintain a parallel array of keys and iterate that in a fixed order. The state graph must define exactly which entities are updated in which sequence.

Core Workflow: Building the State Graph Step by Step

Here is a practical sequence for encoding your simulation as a deterministic state graph.

Step 1: Identify All State Variables

List every piece of data that changes during simulation: entity positions, velocities, health, ammo, cooldown timers, RNG state, animation state, and any global variables like time of day. Group them into a single struct or class that represents one node in the graph. This is your "world state" snapshot.

Step 2: Define Inputs as Explicit Edges

Every input from players — move commands, attack orders, menu selections — must be captured as a small, serializable struct. The input is the edge that moves the graph from one node to the next. Inputs must be timestamped and ordered deterministically. In lockstep, all peers process the same input sequence in the same order.

Step 3: Write the Transition Function

The transition function takes a current state and an input, and produces the next state. This function must be pure: no side effects, no global state, no system calls, no non-deterministic library functions. It must produce identical output given identical input, regardless of the platform. Test this function with a suite of known input/state pairs and compare hashes across all target platforms.

Step 4: Encode the Graph as a Sequence of Snapshots or Deltas

In the simplest implementation, you store every state node (full snapshot) for the last N frames. This consumes memory but makes rollback easy. For bandwidth-constrained scenarios, you can store only the initial state and the list of inputs, and recompute the graph on the fly — this is how replays work. For hybrid approaches, see the variations section.

Step 5: Add a Checksum at Each Node

After computing the next state, hash the entire state snapshot (e.g., using SHA-256 or a fast non-cryptographic hash like xxHash). Peers exchange these checksums after each frame. If they mismatch, you know exactly which frame desynced and can trigger a resync or drop the session.

Tools, Setup, and Environment Realities

Choosing the right tooling for your state graph implementation depends on your performance requirements and team expertise.

C++ with SIMD for High-Performance Simulations

If you are building a real-time strategy game with thousands of units, C++ offers the most control. Use fixed-point arithmetic in 64-bit integers, and consider SIMD intrinsics for parallelizing entity updates. The downside: you must be extremely careful about compiler optimizations. Compile with -ffp-contract=off and -fno-finite-math-only. Use a deterministic allocator (e.g., a linear allocator) to avoid heap order dependencies.

Rust with ECS for Safety and Determinism

Rust's ownership model and lack of undefined behavior make it easier to write deterministic code. The Entity Component System (ECS) pattern, using libraries like Bevy or specs, naturally enforces a fixed iteration order if you avoid parallel iteration over components. Rust's standard HashMap is non-deterministic, but you can use indexmap or BTreeMap. The compiler's optimization level affects floating-point, so use fixed-point integers to be safe.

Managed Languages (C#, Java, Python) — Proceed with Caution

Garbage collection introduces non-determinism through allocation timing and object layout. If you must use a managed language, allocate all objects upfront in a pool, avoid any runtime allocation during simulation, and disable the JIT's floating-point optimizations. Unity's DOTS (Data-Oriented Tech Stack) with Burst compiler can produce deterministic code if you use the math library's deterministic functions. But in our experience, even with these precautions, managed runtimes introduce subtle desyncs that are hard to reproduce.

Testing Infrastructure

You need a test harness that runs the same input sequence on multiple machines (or containers) and compares state hashes after every frame. Automate this in CI. Use a small, synthetic input sequence that exercises all state transitions. Run the test on each target platform (Windows, Linux, macOS, consoles) before every release. We also recommend fuzzing: feed random inputs from a fixed seed and verify that all peers stay in sync for thousands of frames.

Variations for Different Constraints

Not every project can afford to store full state snapshots every frame or wait for network round trips. Here are three common variations of the state graph approach.

Full State Snapshots (High Memory, Low CPU)

Store a complete copy of the simulation state every N frames (e.g., every 10 frames). This allows fast rollback: to rewind 10 frames, you just load the snapshot and replay the inputs. Memory grows linearly with the number of saved snapshots. Use this for turn-based games or simulations with moderate entity counts.

Incremental Deltas (Low Memory, High CPU)

Instead of storing full snapshots, store only the changes (deltas) between frames. To reconstruct a past state, you must apply deltas backward from the current state or forward from the last full snapshot. This reduces memory but increases CPU cost during rollback. It works well for games with infrequent state changes, like card games or board games.

Hybrid Checkpointing (Balanced)

Store full snapshots at regular intervals (checkpoints) and keep incremental deltas between them. For rollback, find the nearest checkpoint, load it, and replay forward. This is the most common approach in commercial RTS games. The checkpoint interval is a tuning parameter: too frequent wastes memory, too infrequent makes rollback slow. A good starting point is a checkpoint every 30 frames (half a second at 60 FPS).

Pitfalls, Debugging, and What to Check When It Fails

Even with a well-designed state graph, desyncs happen. Here are the most common causes and how to track them down.

Floating-Point Divergence

Despite using fixed-point, you might inadvertently use floating-point in a library (e.g., a physics engine). Check every third-party library for non-deterministic behavior. Replace sin/cos with lookup tables or fixed-point approximations. Test on ARM vs. x86 — they often differ in floating-point results.

Non-Deterministic Hash Map Iteration

Even with BTreeMap, if you iterate over a map that you modify during iteration, the order can change. Use immutable data structures or copy the keys to a vector before iterating. We have seen a desync caused by a single entity spawning during iteration, shifting the order of remaining entities.

Rollback Logic Errors

When you roll back to a previous state, you must also roll back the RNG state and any external systems (like audio or input queues). A common mistake is to roll back the simulation state but leave the RNG advanced, causing different random numbers on the replay. Always save and restore the entire state graph node, including RNG.

Network Jitter and Input Misordering

Lockstep requires that all peers process inputs in the same order. If the network delivers inputs out of order, you must reorder them deterministically. Use a reliable, ordered transport (TCP or a custom protocol with sequence numbers). If you use UDP, implement a jitter buffer that waits for missing inputs before advancing the simulation.

Debugging a Desync

When a desync is detected (checksum mismatch), freeze all peers and dump the entire state graph from the last checkpoint to the desync frame. Compare the states field by field. Write a diff tool that highlights the first differing variable. Often the difference is tiny — a single bit in a position coordinate. Once you find it, trace back through the transition function to see which input or calculation caused it. Add that specific case to your test suite.

Common Mistakes FAQ

Q: My desync only happens on one player's machine. Where do I start? Check compiler flags and hardware. That specific machine might have a different CPU that uses FMA, or a different version of a system library. Run the same binary on identical hardware to isolate the issue.

Q: Can I use floating-point for cosmetic effects that don't affect gameplay? No — even cosmetic effects can influence gameplay if they trigger callbacks or change RNG consumption. Keep everything deterministic, or separate cosmetic layers entirely (client-side only, not included in the state graph).

Q: How often should I checksum? Every frame is ideal for debugging, but it adds CPU overhead. For production, checksum every 10–30 frames and log the checksums for later analysis. If a desync is detected, you can request full state dumps from all peers.

Next Steps After Stabilizing Your Graph

Once your state graph is deterministic and your lockstep system is running without desyncs, consider these improvements: 1) Add speculative execution — run the simulation ahead while waiting for inputs, then roll back if the actual input differs. 2) Implement a delta-encoding layer to reduce bandwidth by sending only the changes in state, rather than full inputs. 3) Build a replay system that stores only the initial state and input sequence, allowing spectators to join mid-game by downloading the checkpoint and replaying from there. 4) Profile the transition function and identify hot spots; consider offloading them to a dedicated thread or SIMD. 5) Write a formal specification for your state graph, including all edge cases, so that future team members can maintain determinism.