Input events don't need network linearization. Instead, every input event "happens" on an explicit frame. Each network-broadcast input-event message looks like "during frame N, player P {was/wasn't} holding down button B." Nodes can receive and apply such messages in any arbitrary order, and the result will be correct. It's the frame-counter in each message, not the order each message was received, that determines how history will be rewound and altered.

Keep in mind, every node is running the same deterministic simulation. As long as nodes achieve eventual consistency in their "input movie" somehow (a gossip protocol, say), then every node will end up on the same VM state. You don't need a leader to declare what the consensus state is; presuming trustworthy peers(!), there is a single "objectively-correct" consensus state that every node will converge upon once all nodes have all messages.

Every time an input-event message is received from the network, the receiving node just rewinds to frame N, and recomputes it (and all frames after it) with an input-movie where player P {is/isn't} holding button B. (And then, only if that explicit message wasn't already what was predicted during run-ahead.)

Note that this is also exactly what happens when the local node produces an input-event message — that's what run-ahead is!

That's kind of fascinating. Would you suggest some reading on this? Question: if I send to other 3 players (via gossip say) the event "in frame N, I clicked the B button that causes monster to die" but my network lags and in the mean time they do other events where someone else kills the monster and they see the monster dying from another player event. After a few ms my events gets to them, their state is rewind with the monster dying because of me instead of the other player. In other words, this causes players to see the monster dying twice.

> In other words, this causes players to see the monster dying twice.

The frames that are replayed aren't visibly replayed. They're re-computed, but the visible effect is more of a "lurch" from one world-state to another one. In this case, the monster has been dead for a second or two already, but suddenly each player's score counter would jump around to show that it's actually player P who did it, and gained the points for it. Except for player P themselves, who experiences no change.

It's very similar in experiential effect to the effect when an inherently-networked client-server game does client-side prediction, and then the server sends the canonical state which disagrees from the client's predicted state, and the client has to lurch into the server's canonical state. People's avatars pop into different positions; in an FPS, you might suddenly be dead "out of nowhere"; in a racing game, you might suddenly be spiralling out of the way because your path turned out to collide with that of another car that wasn't originally there; etc.

Inherently-networked games sometimes have interpolation ("lerp"-ing) code to smooth out this lurch between client-side predicted positions and canonical server-side state — usually, if the only thing that's incorrect is positioning, the client will try to generate a few interpolated frames of movement that takes objects from their incorrectly-predicted positions to their server-prescribed positions; and then it'll play those frames in fast-forward, so that they've all been played out well before the server sends its next update.

But this only works when the server isn't communicating every single frame (otherwise there's no time to replay the lerp); and it basically only works for positioning changes — if someone does manage to cause a discrete alteration to the game-state (like changing who killed an enemy), that will still usually cause a sudden "lurch" into the new game-state in these engines. The interpolation-frame generator code just gives up.

(Though, for especially-important things like who won a match, inherently-networked games just do a hard consensus-sync of all players — usually during a screen transition — before actually showing a results screen. People get quite cross when their results lurch!)

And, of course, games that weren't inherently-networked, but which are instead being networked "on the emulation layer", have no logic for lerping, and cannot, unless lerping logic is hand-written by some kind soul for each emulated game's engine. Possible if you're hand-crafting an emulator designed to play a single game; quite unlikely if you're just building a general system emulator — especially if, as with most authors of general-system emulators, your goal is faithful reproduction of the behavior of the original system.

> Would you suggest some reading on this?

No idea if there is any reading on how emulators do this, tbh. (I'm self-taught on this subject, from working with open-source emulator codebases.) But any modern textbook on [inherently-]networked client-server game-engine development should talk about client-side run-ahead prediction and interpolation-frame generation.

I believe there's some book which deep-dives into the network architecture of Doom, or Quake, or Unreal Tournament, or one of those early networked games, and uses it to explain the history/invention of these client-side prediction features. I can't seem to Google it for the life of me, though. Can anyone here assist?

Ok, but what about de-sync?

> the receiving node just rewinds to frame N, and recomputes it (and all frames after it)

What about situation where frame N is a “long” time ago (for some definition of “long”)? There must be some sort of threshold after which the game state cannot be changed even if an input was received.

There usually is, though it's arbitrary — basically an implementation detail of the emulator which was tuned based on in-practice behavior observation. Input-event messages that haven't been integrated into the canonical state after a "long time" must be dropped/undone by those who did integrate them, including by the player who originally generated them. In effect, an implicit "anti-event" is generated saying the opposite of the original input-event message, and applied to history by all players who applied the original message.

How do players tell if their event managed to become part of the consensus state? Depends on the networking protocol. In a gossip protocol, messages get sent to peers individually, and ACKed by those peers. In an elected-leader client-server protocol, as long as the server peer ACKs the message as "in the queue", it's canonical. In an IRC-like spanning-tree message-relay system†... something complicated involving vector clocks containing message IDs.

† I don't think I've ever seen an emulator choose a hierarchical message-relay architecture. It makes good robustness+efficiency trade-offs, but it's just far too complex to work with compared to the alternatives. It's more the domain of MMOs, that need to be concerned with many nodes colocated in one site speaking to many nodes colocated at other sites.