04 - Real-Time State Sync: Deterministic Rollback & Reconciliation

The enemy who reappears: why every client sees a different world

You shoot, the enemy drops, then reappears standing two meters further on. It is not a rendering bug: it is the network. Every client sees the world with a different delay, and the server, which decides how things stand, reports it a few tens of milliseconds late. Four techniques hide this gap, and here you build them one at a time with an executed model: client-side prediction with reconciliation, rollback, the interpolation of the other players and the delta compression of snapshots. Which one to use depends on a single question: how much of the game can be simulated identically on every machine?

The networking picture (authoritative server, tick, latency) is in the article on the anatomy of the game backend. The listings here are deterministic simulations with a fixed seed and a fake clock, run with Node.js 24: they demonstrate the mechanics, they do not measure a real game.

Three families of netcode, and when each one holds up

Lockstep advances everyone only when everyone has delivered the inputs for the turn: perfect consistency, but everyone's latency becomes that of the slowest (Glenn Fiedler writes this about RTS games, where the commands of each turn run identically on all machines). Rollback, as described by the GGPO repository, uses input prediction and speculative execution to give the illusion of a zero-latency network. The authoritative server with prediction model leaves the decision to the server and uses the same techniques to hide the wait: it is the one described by Gabriel Gambetta in four articles whose mechanics this one retraces.

In the table the cost column matters, because that is where the families differ. Rollback does not ask you to trust the network but it asks you to run a simulation that is bit-for-bit identical on every machine and fast enough to be redone several times within a frame; the authoritative server asks you for one server per match but gives you anti-cheat almost for free, as the article on anti-cheat explains.

Prediction and reconciliation: execute now, correct later

Without prediction, the player presses "forward" and waits a full network round trip before moving: with an RTT of 100 ms the character responds with a tenth of a second of delay, and the game feels made of rubber. Prediction executes the input immediately, locally; the server does the same with its delay and sends the state back together with the number of the last input it processed. That sequence number is the whole trick: the client knows which inputs the server has already seen (which it can discard) and which not (which it must reapply on top of the received state).

The listing simulates a line with 3 ticks of latency in each direction. The player holds "forward" for ten ticks and the server ignores input number 4 (the player is stunned: the client does not know). The listing runs the scenario twice: a reconciliation with replay (server state plus the inputs still in flight) and a naive one that replaces the position with the server's and nothing else.

// Prediction + reconciliation on a line. Latency: 3 ticks each way.
interface Input { readonly seq: number; readonly move: number }
interface ServerMsg { readonly x: number; readonly lastSeq: number }
const LATENCY = 3;
const STUNNED_SEQ = 4; // the server ignores this input (the player is stunned), the client does not know

function run(replay: boolean) {
  let clientX = 0, serverX = 0, lastSeq = 0;
  let pending: Input[] = [];
  const toServer: { at: number; input: Input }[] = [];
  const toClient: { at: number; msg: ServerMsg }[] = [];
  const shown: number[] = [];
  for (let t = 0; t < 16; t++) {
    if (t < 10) {                                   // the player holds "forward" for 10 ticks
      const input = { seq: t + 1, move: 1 };
      clientX += input.move; pending = [...pending, input];
      toServer.push({ at: t + LATENCY, input });
    }
    for (const m of toServer.filter(m => m.at === t)) {   // the server processes the inputs that arrived
      if (m.input.seq !== STUNNED_SEQ) serverX += m.input.move;
      lastSeq = m.input.seq;
      toClient.push({ at: t + LATENCY, msg: { x: serverX, lastSeq } });
    }
    for (const m of toClient.filter(m => m.at === t)) {   // the client receives the authoritative state
      pending = pending.filter(i => i.seq > m.msg.lastSeq);
      clientX = replay ? pending.reduce((x, i) => x + i.move, m.msg.x) : m.msg.x;
    }
    shown.push(clientX);
  }
  const jumps = shown.slice(1).map((x, i) => x - shown[i]);
  return { shown, maxBack: Math.max(0, ...jumps.map(j => -j)), final: shown[shown.length - 1], serverX };
}

const a = run(true), b = run(false);
console.log("with replay   :", a.shown.join(" "), `| max jump back ${a.maxBack}, final ${a.final}, server ${a.serverX}`);
console.log("without replay:", b.shown.join(" "), `| max jump back ${b.maxBack}, final ${b.final}, server ${b.serverX}`);

// Output:
// with replay   : 1 2 3 4 5 6 7 8 9 9 9 9 9 9 9 9 | max jump back 0, final 9, server 9
// without replay: 1 2 3 4 5 6 1 2 3 3 4 5 6 7 8 9 | max jump back 5, final 9, server 9

With replay the player sees 1, 2, ... 9 advance without ever going back: at tick 9 the correction arrives that concerns the stunned input and the client removes one unit from the position it had predicted (10 becomes 9), a small correction proportional to the error. Without replay, as soon as the first server state arrives (which is one RTT old) the position jumps from 6 to 1: a leap back of five units, equal to the six network ticks. The line that makes the difference is the reduce over the pending inputs, which puts back on top of the server state what the server has not seen yet. Prediction has a boundary: it works for what the client can simulate on its own (its own movement) and not for outcomes that depend on the others, such as damage, which wait for the server.

Rollback: predicting the others too, and redoing when you are wrong

Prediction concerns the local player. Rollback applies the same idea to the inputs of the others: you do not wait for their input (it would add delay), you guess it (usually by repeating the last one), you simulate ahead, and when the real input arrives and differs from the guess you go back to a saved frame and resimulate up to the present. At 60 frames per second, a latency of 200 ms is worth 12 frames to redo in the worst case.

The listing has two players on a line, with a remote input that arrives 4 frames late and a collision rule deliberately dependent on order. The step function is deterministic and uses only integers. The program compares the final state with that of a reference that knows the true inputs from the start, and also shows the wrong variant found in many implementations: restarting from the state after the wrong frame, that is applying the last step twice.

// Rollback with two players and a remote input delayed by 4 frames. Integer state: no floats.
interface State { readonly p1: number; readonly p2: number }
interface Frame { readonly local: number; readonly remote: number }   // input in {-1,0,1}
const DELAY = 4, FRAMES = 120;

function mulberry32(a: number) {
  return () => { a = (a + 0x6d2b79f5) | 0; let t = Math.imul(a ^ (a >>> 15), 1 | a);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
}
// Deterministic step function; order matters (a push if the two overlap)
const step = (s: State, f: Frame): State => {
  const p1 = s.p1 + f.local, p2 = s.p2 + f.remote;
  return { p1, p2: p1 === p2 ? p2 + 1 : p2 };
};

const rnd = mulberry32(5);
const localInputs = Array.from({ length: FRAMES }, () => Math.floor(rnd() * 3) - 1);
const remoteInputs = Array.from({ length: FRAMES }, () => Math.floor(rnd() * 3) - 1);

// Reference: all the true inputs from the start
let ref: State = { p1: 0, p2: 3 };
for (let f = 0; f < FRAMES; f++) ref = step(ref, { local: localInputs[f], remote: remoteInputs[f] });

function play(restoreBeforeFrame: boolean) {
  const known: number[] = [];                        // confirmed remote inputs
  const used: Frame[] = [];                          // inputs actually used in each frame
  const before: State[] = [];                        // state BEFORE each frame
  let state: State = { p1: 0, p2: 3 }, rollbacks = 0, resimulated = 0;

  const confirm = (k: number, f: number) => {        // the remote input of frame k arrives, we are at frame f
    known[k] = remoteInputs[k];
    if (used[k].remote === known[k]) return;         // correct prediction: nothing to do
    rollbacks++;
    used[k] = { ...used[k], remote: known[k] };
    let s = restoreBeforeFrame ? before[k] : (before[k + 1] ?? state);   // the wrong variant restarts from the state after the frame with the old input
    for (let g = restoreBeforeFrame ? k : k + 1; g <= f; g++) {
      before[g] = s; s = step(s, used[g]); resimulated++;
    }
    state = s;
  };

  for (let f = 0; f < FRAMES; f++) {
    const predicted = known.length ? known[known.length - 1] : 0;      // repeat the last known input
    const frame = { local: localInputs[f], remote: predicted };
    before[f] = state; used[f] = frame; state = step(state, frame);
    if (f - DELAY >= 0) confirm(f - DELAY, f);
  }
  for (let k = FRAMES - DELAY; k < FRAMES; k++) confirm(k, FRAMES - 1);   // last inputs arriving after the match ends
  return { state, rollbacks, resimulated };
}

for (const [name, ok] of [["rollback from the state before the frame", true], ["wrong variant (state after the frame)", false]] as const) {
  const r = play(ok);
  const differs = JSON.stringify(r.state) !== JSON.stringify(ref);
  console.log(`${name}: ${r.rollbacks} rollbacks, ${r.resimulated} frames resimulated, final state ${JSON.stringify(r.state)}, differs from reference: ${differs}`);
}
console.log("reference (true inputs):", JSON.stringify(ref));

// Output:
// rollback from the state before the frame: 80 rollbacks, 392 frames resimulated, final state {"p1":-5,"p2":3}, differs from reference: false
// wrong variant (state after the frame): 80 rollbacks, 312 frames resimulated, final state {"p1":-5,"p2":0}, differs from reference: true
// reference (true inputs): {"p1":-5,"p2":3}

The correct version restores the state before the wrong frame (before[k]), resimulates 392 frames in 80 rollbacks, and ends in a state identical to the reference. The variant that restarts from the state after the frame ends with p2 at 0 instead of 3: the kind of error that shows up only after minutes of play. Two caveats on the model. The generator changes the remote input almost every frame, so 80 rollbacks over 120 frames is an extreme case: real players hold the same key for a long time and the "repeat the last one" prediction guesses right far more often. And each rollback costs on average 392/80 = 4.9 extra frames of computation: if your simulation does not fit comfortably in a fraction of a frame's budget, rollback is not the way.

The requirement that holds everything up is determinism: the same inputs in the same order must produce the same state on every machine, which rules out unseeded random generators, dependencies on the clock and floating point that is not identical across architectures. With floating point it is hard to achieve, and it must be decided at the start of the project: it is not an option you switch on at the end.

Interpolation: the others are drawn in the past

For remote players prediction cannot work, because you do not know their inputs. You do the opposite: you draw them a little in the past, interpolating between two snapshots that have already arrived, so the movement is smooth even if packets arrive at 50 ms intervals. The price is that you see them late by an amount you choose, and the choice has a minimum: interpolation needs two snapshots that bracket the instant of drawing, so the delay must cover one interval between snapshots, the variability of the network and, if you want to tolerate losses, another interval for each lost packet.

The listing tests the rule. An entity moves at 100 units per second and reverses direction halfway; the server sends 20 snapshots per second (one every 50 ms), the network has between 40 and 70 ms of delay and 10% of the packets are lost. It compares drawing the last received snapshot with interpolation at three different delays.

// Entity interpolation: snapshots at 20 Hz, network with variable delay and 10% loss.
const SNAP_MS = 50, DURATION = 2000;
function mulberry32(a: number) {
  return () => { a = (a + 0x6d2b79f5) | 0; let t = Math.imul(a ^ (a >>> 15), 1 | a);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
}
const rnd = mulberry32(9);
// True position: 100 units/s forward, then reversal at t = 1000 ms
const truth = (t: number) => (t <= 1000 ? 0.1 * t : 100 - 0.1 * (t - 1000));

interface Snap { readonly sentAt: number; readonly arrivesAt: number; readonly x: number }
const snaps: Snap[] = [];
for (let t = 0; t <= DURATION; t += SNAP_MS) {
  if (rnd() < 0.10) continue;                                    // lost packet
  snaps.push({ sentAt: t, arrivesAt: t + 40 + rnd() * 30, x: truth(t) });   // 40-70 ms of network
}

function render(useInterpolation: boolean, DELAY_MS = 0) {
  let prev: number | null = null, maxJump = 0, ageSum = 0, frames = 0, holes = 0;
  for (let now = 300; now < DURATION; now += 1000 / 60) {
    const got = snaps.filter(s => s.arrivesAt <= now);           // what has arrived so far
    let x: number, age: number;
    if (!useInterpolation) {
      const last = got[got.length - 1]; x = last.x; age = now - last.sentAt;
    } else {
      const rt = now - DELAY_MS;                                  // draw in the past
      const before = [...got].reverse().find(s => s.sentAt <= rt);
      const after = got.find(s => s.sentAt >= rt);
      if (!before || !after) { holes++; continue; }
      const t = after.sentAt === before.sentAt ? 0 : (rt - before.sentAt) / (after.sentAt - before.sentAt);
      x = before.x + (after.x - before.x) * t; age = DELAY_MS;
    }
    if (prev !== null) maxJump = Math.max(maxJump, Math.abs(x - prev));
    prev = x; ageSum += age; frames++;
  }
  return { maxJump, meanAge: ageSum / frames, holes, frames };
}
const cases: [string, boolean, number][] = [["latest snapshot", false, 0], ["interpolation, delay 100 ms", true, 100],
  ["interpolation, delay 150 ms", true, 150], ["interpolation, delay 250 ms", true, 250]];
for (const [name, flag, d] of cases) {
  const r = render(flag, d);
  console.log(`${name.padEnd(29)} max jump ${r.maxJump.toFixed(2)}, mean age ${r.meanAge.toFixed(0)} ms, frames without a pair ${r.holes}/${r.frames + r.holes}`);
}
console.log("lost snapshots:", Math.round(DURATION / SNAP_MS) + 1 - snaps.length, "out of", Math.round(DURATION / SNAP_MS) + 1);

// Output:
// latest snapshot               max jump 10.00, mean age 82 ms, frames without a pair 0/102
// interpolation, delay 100 ms   max jump 6.67, mean age 100 ms, frames without a pair 24/102
// interpolation, delay 150 ms   max jump 1.67, mean age 150 ms, frames without a pair 0/102
// interpolation, delay 250 ms   max jump 1.67, mean age 250 ms, frames without a pair 0/102
// lost snapshots: 2 out of 41

Drawing the latest snapshot gives the freshest data (82 ms) but moves the entity in jumps of 10 units. Interpolation at 100 ms is the intuitive choice and the wrong one: in 24 frames out of 102 one of the two snapshots is missing (the next one has not yet arrived, because 50 ms of interval plus 70 of network make 120 ms) and the drawing freezes. At 150 ms everything is smooth, with a maximum jump of 1.67 units (100 units/s over 60 frames), equal to the movement of one frame; at 250 ms it is just as smooth but needlessly delays by another 100. Glenn Fiedler puts it in numbers for snapshots at 10 per second: the minimum delay is 100 ms, 150 ms with jitter, 250 or 350 to protect against one or two consecutive lost packets.

Delta compression: send only what the client does not already have

With 64 entities and 60 snapshots per second, sending the whole world in every packet is wasteful: almost nothing has changed. Delta compression sends only the differences from a snapshot that the server knows the client has. The detail that makes it robust is the word "knows": the baseline is the last snapshot confirmed by the client, not the last one sent. That way a lost packet breaks nothing: the next packet is computed against the same old baseline and is enough on its own.

In the listing about 10% of the entities change every tick, 20% of the packets are lost and the acknowledgements come back after 2 ticks. The program checks on every received packet that the state rebuilt by the client is identical to the server's. The sizes are the length of the JSON: they are not an optimized network format, they only give the proportion.

// Delta compression against the last snapshot CONFIRMED by the client. Lost packets: 20%.
interface Ent { readonly id: number; readonly x: number; readonly hp: number }
type World = ReadonlyMap<number, Ent>;
function mulberry32(a: number) {
  return () => { a = (a + 0x6d2b79f5) | 0; let t = Math.imul(a ^ (a >>> 15), 1 | a);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
}
const rnd = mulberry32(21);
const same = (a: World, b: World) => a.size === b.size && [...a].every(([i, e]) => JSON.stringify(b.get(i)) === JSON.stringify(e));

let world: World = new Map(Array.from({ length: 64 }, (_, id) => [id, { id, x: id * 10, hp: 100 }]));
const history = new Map<number, World>([[0, world]]);      // server snapshot per tick
let ackedByServer = 0;                                    // what the server knows has arrived
const acks: { at: number; tick: number }[] = [];
let fullBytes = 0, deltaBytes = 0, packets = 0, wrong = 0, maxBaselineAge = 0;

for (let tick = 1; tick <= 300; tick++) {
  world = new Map([...world].map(([id, e]) => [id, rnd() < 0.1 ? { ...e, x: e.x + 1, hp: e.hp - (rnd() < 0.3 ? 1 : 0) } : e]));
  history.set(tick, world);
  for (const a of acks.filter(a => a.at === tick)) ackedByServer = Math.max(ackedByServer, a.tick);

  const base = history.get(ackedByServer)!;               // the delta is computed against what the client surely has
  const changed = [...world.values()].filter(e => JSON.stringify(base.get(e.id)) !== JSON.stringify(e));
  const packet = { baseline: ackedByServer, tick, changed };
  deltaBytes += JSON.stringify(packet).length; fullBytes += JSON.stringify({ tick, all: [...world.values()] }).length; packets++;
  maxBaselineAge = Math.max(maxBaselineAge, tick - ackedByServer);

  if (rnd() < 0.2) continue;                              // lost packet: the client sees nothing
  const next = new Map(history.get(packet.baseline)!);    // the client starts from the baseline it already has
  for (const e of packet.changed) next.set(e.id, e);
  if (!same(next, world)) wrong++;
  acks.push({ at: tick + 2, tick });                      // the acknowledgement comes back after 2 ticks
}
console.log(`packets: ${packets}, wrongly reconstructed state: ${wrong}`);
console.log(`mean bytes per packet: full ${(fullBytes / packets).toFixed(0)}, delta ${(deltaBytes / packets).toFixed(0)} (${((deltaBytes / fullBytes) * 100).toFixed(0)}% of full, measured as JSON length)`);
console.log(`oldest baseline used: ${maxBaselineAge} ticks earlier`);

// Output:
// packets: 300, wrongly reconstructed state: 0
// mean bytes per packet: full 1671, delta 380 (23% of full, measured as JSON length)
// oldest baseline used: 5 ticks earlier

Over 300 packets the reconstructed state is always correct, and the delta weighs 23% of the full packet (380 bytes against 1671). The oldest baseline used is 5 ticks away: it is the price of late acknowledgements and lost packets, and it signals that the server must keep the latest snapshots of each client (here history) until they are certainly superseded. The saving depends entirely on how much the world changes: in a scene where everyone moves on every tick, the delta vanishes, and it is better to switch to more compact encodings for each field.

Compensating lag for shots: the server goes back in time

Prediction and interpolation produce a consequence that Gambetta names precisely: you see yourself in the present and the others in the past. When you shoot a moving target, you are aiming where it was before. Lag compensation solves the problem on the server: the client sends the exact instant of the shot and the aim, and the server, which keeps the recent history of the world, rebuilds the scene as it was for that player at that moment and evaluates the shot there. The cost falls on whoever has just taken cover: they can be hit a few instants after being safe on their own screen. It is a declared compromise: in favor of the shooter, because missing a perfect shot is perceived as worse.

Practical rules to avoid mistakes

• Fixed simulation step: the logic advances in constant ticks, never by the "frame delta".
• Sequence number on every input: without it, reconciliation does not know what to reapply.
• Bounded history: keep only the frames rollback may need (maximum accepted latency divided by frame duration).
• Confirmed baseline for deltas, with the history of snapshots on the server.
• A counter of corrections: how often and by how much the client is corrected is the direct measure of netcode quality.

The five rules share a theme: each technique trades memory and computation for perceived latency, and works as long as both sides agree on what is "past" (a sequence number, a tick, a baseline). The last one is usually the one that is missing: without measuring corrections, netcode that degrades on the real network is noticed by the players and not by the charts. The tools to collect them are in the article on game backend observability.

What you can do now

You can choose between lockstep, rollback and authoritative server based on how much simulation you can make deterministic. You can implement prediction with replay-based reconciliation, and tell it apart from the leap back of naive correction. You can size the interpolation delay from the snapshot interval and the jitter, and you can build a delta that survives packet loss. The next step is protecting this scheme from those who lie to the server: the anti-cheat architecture.