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

Introduction: The Synchronization Challenge in Peer-to-Peer Lockstep

Peer-to-peer lockstep is a synchronization model where each peer executes the same sequence of inputs, step by step, to produce identical simulation states without a central server. The core promise is simple: if every peer processes the same commands in the same order and with the same initial state, the simulation will be identical across all participants. In practice, this promise is notoriously difficult to keep. Network latency, packet loss, out-of-order delivery, and even subtle differences in floating-point arithmetic can cause the state graph to diverge, leading to desyncs that break the game or simulation. Designing a deterministic state graph is the architectural antidote to these issues. It provides a formal structure that governs how inputs are collected, sequenced, validated, and applied to the shared simulation. Without this graph, lockstep systems are fragile, requiring constant checks and resynchronization that degrade the user experience.

This guide is written for experienced developers and architects who are already familiar with the basics of lockstep synchronization. We assume you've encountered the fundamental problem: how to ensure that N peers, each with potentially different clocks and network conditions, arrive at the same simulation state after every turn. The answer lies in a carefully designed state graph that enforces determinism through input commitment, turn ordering, and state validation. We will not rehash the basics of peer-to-peer networking or the history of lockstep in RTS games. Instead, we focus on the design decisions that separate a robust lockstep system from one that falls apart under real-world conditions. By the end of this article, you will have a clear framework for designing a deterministic state graph that is resilient, efficient, and scalable to dozens of peers.

This overview reflects widely shared professional practices as of May 2026; verify critical details against current official guidance where applicable.

Core Concepts: Why Determinism Is Harder Than It Sounds

Determinism in a lockstep system means that given the same initial state and the same ordered sequence of inputs, every peer will compute the same final state. This seems straightforward, but achieving it requires discipline across every layer of the simulation. The primary challenge is that the simulation environment—hardware, operating system, compiler, and runtime—can introduce non-determinism. For instance, the order of floating-point operations can vary depending on compiler optimizations, leading to different rounding results. Similarly, multithreading can cause race conditions that alter state updates unless carefully controlled. The state graph must be designed to isolate these variables and enforce a strict, repeatable computation model.

Input Aggregation and Commitment

The first layer of determinism is input handling. In a typical lockstep system, each peer collects local inputs (key presses, mouse clicks, AI decisions) for a fixed time window, typically called a turn. At the end of the turn, all peers broadcast their inputs to each other. However, due to network jitter, peers may receive inputs at different times. To maintain determinism, every peer must apply the same set of inputs for the same turn. This requires a commitment scheme: peers must agree on which inputs are valid for a given turn before processing that turn. A common approach is to use a turn number and require that each peer sends its inputs for turn N before any peer begins processing turn N. The state graph defines the protocol for this commitment, often using a barrier or synchronization point.

State Representation and Checksums

Even with deterministic input ordering, the simulation state itself must be represented in a way that is immune to platform-specific variations. Using fixed-point arithmetic instead of floating-point is a common mitigation. Additionally, the state graph should include periodic checksum verification. After every M turns, each peer computes a checksum of its full simulation state and broadcasts it. If all checksums match, the system continues; if not, a resynchronization protocol is triggered. The state graph must account for these checksum points, defining how to roll back and reapply inputs if a mismatch occurs.

Turn-Based Progression vs. Time-Based Progression

Another design choice is whether the state graph advances in discrete turns or continuous time. Turn-based progression is simpler: each turn processes a fixed set of inputs, and all peers move to the next turn simultaneously. Time-based progression uses a virtual time that advances at a fixed rate, and inputs are timestamped. This model is more flexible but introduces additional complexity in ordering inputs with the same timestamp. The state graph for time-based progression must include a tie-breaking rule, such as peer ID ordering, to ensure determinism. Most lockstep systems for real-time games use turn-based progression because it aligns with network round trips and simplifies debugging.

In summary, the core concepts of determinism revolve around controlling input ordering, state representation, and progression model. The state graph is the formal specification of these controls. It must be designed with explicit rules for every operation that could introduce non-determinism. Teams often find that investing in a robust state graph early saves enormous debugging effort later, as desyncs become rare and, when they do occur, can be traced to the exact step where the graph was violated.

Comparing State Graph Topologies: Linear Chain, Ring Buffer, and DAG

The topology of the state graph determines how turns are connected and validated. Three common topologies are the linear chain, ring buffer, and directed acyclic graph (DAG). Each has trade-offs in complexity, memory footprint, and fault tolerance. Choosing the right one depends on your scale, latency tolerance, and need for historical rollback.

When to Avoid Each Topology

The linear chain is ideal for small projects but becomes unwieldy for sessions lasting hours, as the chain length grows into the millions. The ring buffer solves memory growth but introduces a hard limit on rollback depth. If your simulation requires rewinding more turns than the buffer size (e.g., for replay or debugging), you must maintain external snapshots. The DAG offers the most flexibility but adds significant engineering complexity. It is overkill for a typical multiplayer game with fewer than 32 peers. However, it shines in scenarios where peers have heterogeneous network speeds and you want to allow faster peers to progress without waiting for slower ones. In that case, the DAG must include a deterministic ordering rule for turns with multiple parents, such as topological sort by peer ID and timestamp.

In practice, many systems start with a linear chain and later migrate to a ring buffer when memory becomes an issue. The DAG is rarely the first choice due to its complexity. A composite approach is also possible: use a ring buffer for the most recent turns and periodically archive a linear chain of snapshots for long-term verification. The decision matrix should consider: number of peers, expected session length, rollback requirements, and network latency distribution. For a typical real-time strategy game with 8 players and 30-minute sessions, a ring buffer of 1024 turns (about 17 minutes at 1 turn per second) with periodic snapshotting is a robust choice.

Step-by-Step Guide to Designing Your State Graph

Designing a deterministic state graph requires a systematic approach. The following steps provide a framework that can be adapted to your specific simulation. We'll assume a turn-based progression with a linear chain topology for clarity, but the principles apply to other topologies with appropriate modifications.

Step 1: Define the Turn Structure

Each turn should be a data structure containing: turn number, list of inputs (each input includes peer ID, command, and timestamp within the turn window), and a checksum of the expected state after applying the inputs. The turn structure must be serializable and identical across all peers. Use a language-agnostic format like Protocol Buffers or a flat binary schema. Avoid using floating-point numbers in the turn data; use integers or fixed-point representations instead.

Step 2: Establish Input Commitment Protocol

Peers must agree on which inputs belong to which turn. A common protocol is the "optimistic input broadcast": each peer broadcasts its inputs for turn N as soon as it finishes collecting them. All peers wait until they have received inputs from all peers for turn N before processing turn N. To handle lost packets, use a reliable transport (e.g., TCP or a custom ACK scheme). The state graph should include a timeout mechanism: if a peer does not receive all inputs within a threshold, it requests a retransmission. If the threshold is exceeded, the peer may drop the late peer or pause the simulation.

Step 3: Implement Turn Processing with Deterministic Update Function

The update function that applies inputs to the state must be deterministic. This means: no random number generation without a seeded, deterministic PRNG; no use of system clock or other non-deterministic sources; and all computations using fixed-point arithmetic or deterministic floating-point (e.g., with strict rounding modes). The function should be pure: given the same state and inputs, it must produce the same new state. Test this by running the update function on the same inputs on different platforms (e.g., Windows, Linux, macOS) and verifying identical outputs.

Step 4: Add Checksum Points

Insert checksum points at regular intervals, say every 60 turns. After processing a checksum turn, each peer computes a hash (e.g., SHA-256) of the full simulation state and broadcasts it to all peers. If all hashes match, the system is deterministic. If not, the peers must roll back to the last known good state (the previous checksum point) and reapply inputs with additional logging to identify the divergence source. The state graph should store the checksum and the state snapshot at each checksum point for efficient rollback.

Step 5: Handle Desync Recovery

Design a recovery protocol. When a desync is detected, all peers pause, exchange the last good state, and then replay the turns from that point with verbose logging. The state graph should allow for "replay mode" where each turn's inputs are stored in a log. Once the cause is identified (e.g., a floating-point error on one platform), the fix is applied to the update function, and the simulation resumes from the last good state. This highlights the importance of keeping the state graph append-only: historical turns must never be modified, only replayed.

By following these steps, you establish a solid foundation. The key is to iterate: start with a minimal graph and add complexity only when needed. Many teams make the mistake of over-engineering the graph upfront, which leads to bugs in the protocol itself. Instead, implement the simplest version that works, stress-test it with simulated network conditions, and then evolve.

Real-World Scenarios: Case Studies in State Graph Design

To ground the theory, let's examine three anonymized scenarios that illustrate common challenges and solutions. These examples are composites based on experiences reported in developer forums and engineering blogs.

Scenario 1: The 8-Player RTS Game with Occasional Desyncs

A team building a competitive real-time strategy game for 8 players implemented a linear chain state graph with turn-based progression and TCP for reliable input delivery. They encountered desyncs about once every 20 games. Debugging revealed that the desyncs were caused by a subtle race condition in the input collection: on some peers, the turn timer fired before all local inputs for that turn were captured, leading to a missing input. The fix was to add a local input queue with a strict cutoff: no inputs accepted after the turn's deadline. The state graph was updated to include a flag indicating whether the local input set was complete, and the commitment protocol was tightened to require explicit acknowledgment from each peer. After the fix, desyncs dropped to near zero. This scenario highlights the importance of edge cases in input handling, especially when the turn duration is short (e.g., 100 ms).

Scenario 2: The 64-Peer Blockchain-Inspired Simulation

A research project simulating a distributed ledger used a DAG-based state graph to allow peers to propose turns (blocks) without waiting for global consensus. The challenge was ordering turns with multiple parents. They used a deterministic topological sort that prioritized turns with lower peer IDs and earlier timestamps, but this led to a bias where peers with lower IDs always had their turns processed first. To fix this, they introduced a round-robin ordering that shuffled priority every epoch. The state graph also required a conflict resolution mechanism for turns that attempted to modify the same state variable simultaneously. They implemented a "first-in-time" rule based on the turn's creation time, but since clocks were not perfectly synchronized, they had to add a grace period and tie-breaking by peer ID. This scenario illustrates the complexity of DAG topologies and the need for careful fairness mechanisms.

Scenario 3: The 2-Player Cooperative Simulation with Floating-Point Divergence

A two-player cooperative physics simulation used a ring buffer state graph with fixed-point arithmetic for most computations, but the physics engine internally used floating-point for collision detection. After several minutes of gameplay, the states diverged. The root cause was that the physics engine's collision resolution order depended on the order of objects in a hash map, which varied between peers due to different memory layouts. The fix was to sort the collision pairs deterministically (e.g., by object ID) before processing. The state graph was updated to include a preprocessing step that sorted all dynamic collections before each turn's update. This case shows that determinism must extend to every library and algorithm used in the simulation, not just the top-level game logic.

These scenarios underscore recurring lessons: test with real network conditions, log all inputs for forensic analysis, and be prepared to enforce determinism at the lowest level of the simulation stack. The state graph is only as strong as its weakest link.

Common Questions and Pitfalls

Even with a well-designed state graph, developers encounter recurring questions and pitfalls. Addressing these proactively can save weeks of debugging.

How do I handle peer disconnection and reconnection?

When a peer disconnects, the remaining peers must either pause the simulation or continue without it. If they continue, the state graph must be updated to exclude the disconnected peer's inputs. A common approach is to replace missing inputs with a "null" command that has no effect. When the peer reconnects, it must receive the full state history (or a snapshot) from the current time and then start sending inputs again. The state graph should support a "join" event that initializes the new peer's state to the current agreed state. This requires that the graph stores the state at regular intervals (snapshots) and that the peer can download the necessary turns.

What about floating-point determinism across different CPUs?

Floating-point operations are not guaranteed to be identical across different CPU architectures (e.g., x86 vs. ARM) or even across different compiler optimization levels. The safest approach is to avoid floating-point entirely in the simulation state and use fixed-point arithmetic (e.g., using integers scaled by a factor). If you must use floating-point, set the floating-point mode to strict (e.g., /fp:precise in MSVC, -frounding-math in GCC) and use the same compiler and flags across all peers. However, even then, subtle differences can arise. Many teams enforce fixed-point for all state variables and only use floating-point for rendering, which is not part of the deterministic simulation.

How do I prevent state explosion with a linear chain?

State explosion occurs when the chain of turns grows indefinitely, consuming memory. The solution is to periodically prune the chain by saving a snapshot of the state at a certain turn and then discarding all turns before that snapshot. The snapshot becomes a new root. The state graph should support this by allowing a new base turn that includes the full state. All future turns are appended relative to this base. This is essentially a checkpointing mechanism. The trade-off is that you lose the ability to replay from before the snapshot, but if you keep a separate log of inputs for debugging, you can still reconstruct earlier states if needed.

Can I use the state graph for spectator mode?

Yes. A spectator simply receives the turn data and processes them in the same way as a player, but without sending inputs. The state graph for a spectator is identical to that of a player, except that the input commitment step is skipped. The spectator must still wait for all player inputs before processing a turn. If you want to reduce latency for spectators, you can allow them to process turns slightly behind the players, but this requires careful handling of turn boundaries.

By addressing these questions upfront, you can design the state graph to be more robust. Each pitfall represents a design decision that should be documented and tested. The state graph is not just a data structure; it is a contract that every peer must follow exactly.

Conclusion: Key Takeaways for Your Lockstep System

Designing a deterministic state graph for peer-to-peer lockstep is a challenging but rewarding endeavor. The core insight is that determinism is not automatic; it must be engineered into every component of the system. The state graph provides the formal structure that enforces input ordering, state representation, and progression rules. We have covered the core concepts of input commitment, checksum verification, and turn-based progression, and compared three topologies: linear chain, ring buffer, and DAG. The step-by-step guide offers a practical path from defining the turn structure to implementing desync recovery. The real-world scenarios illustrate common pitfalls and solutions, while the FAQ addresses persistent questions about disconnection, floating-point, state explosion, and spectator mode.

The most important takeaway is to start simple. Implement a linear chain with fixed-point arithmetic, rigorous input commitment, and periodic checksums. Stress-test thoroughly with simulated network conditions and on different hardware. Only then consider more complex topologies or optimization. Many teams have wasted months on a DAG-based system when a simple ring buffer would have sufficed. Also, remember that the state graph is a living document: as your simulation evolves, the graph may need adjustments. Log everything, and build tools to replay and compare states. This forensic capability is invaluable for debugging desyncs.

Finally, share your state graph specification with all team members. It should be a clear, written document that defines exactly what constitutes a valid turn, how inputs are collected, and how the state is updated. This prevents misunderstandings that lead to non-deterministic behavior. With a well-designed state graph, your lockstep system can achieve the holy grail of peer-to-peer synchronization: identical states across all peers, every time.