Essentialky if you model your world/simulation as objects and events/messages, and you can isolate input (user input, possibly clock ticks) - and you can order external inputs in a (distributed/consistent) log (a la apache kafka) - then you can have a simulation that runs in parallel and lock-step across many clients.
Sounds like the kind of thing you want to implement in a functional language, to have strong guarantees of determinism.
Have some threads waiting on input (controls, network), dispatch to pure functions running the simulation, stream render commands to a rendering component. You can even consider the RNG as one of the input streams to keep the core pure.
I'm not into game programming but this got me interested in implementing a toy RTS!
It can be done but it's quite expensive to engineer such a solution, both in time spent theorizing and in runtime performance consequences. There are many small gameplay features that are trivial with mutability and a data-oriented model, but require a major spec change if functional style is applied. The parts that are easy to do functionally are relatively trivial in comparison.
The happy medium for gameplay simulations is to write straight-line imperative code and minimize your use of subroutines and indirection - you want "static" synchronization that loops over data in big batches where execution flow reads easily. When it's kept simple like this, major desynchronization challenges come down to compilation behaviors and interactions with other modules(render, network, etc). The main loop gets big as a result, but factoring it out only makes it harder to follow, because the complexity is coming from the high number of sync points, not duplicated code.
This is the exact architecture I'm using to create a 2d mmorpg engine. It's been a long running project of mine, off and on for 3 years. When I began I had this architecture at the in/out network layer, command input in, world state changes out, but the internals on the server were a god danmed mess. The project is back on and I'm striving for that pure core fn(worldState, input) -> worldState.
Functional languages can't help you when architectures, standard libraries and compilers implement floating point slightly differently. Cross-system determinism is a totally different property than referential transparency.
The title reminds me of one of my all time favorite simple hacks.
This was from an RTS game circa 2000, can't remember which. They were p2p broadcast lockstep as the above, and UDP based. Since the bandwidth is so trivial (boils down to what 10 fingers and a mouse can do), they'd just repeat the last N messages in every packet as brute force forward error correction. Lose a packet? Just wait for the next one.
Delta encoding is the more general technique you're describing. It's used by most latency-sensitive networked games today, first made popular in Quake 3 I believe. The general idea is to keep resending all changes in state since the most recent ACK.
http://www.gamasutra.com/view/feature/131503/1500_archers_on...