Relativistic replication

Mikola Lysenko

University of Wisconsin-Madison

twitter @mikolalysenko | github @mikolalysenko | blog:

Realtime multiplayer games on the web

The technology is already here!

  • WebSockets
  • WebRTC
  • WebGL
  • WebAudio
  • Game pad API
  • node.js

But why is almost no one writing them?

Online multiplayer games are hard to implement

Graphics + Distributed Systems = Hard problems

Multiplayer games as distributed replicas

Multiple machines, one shared state

Issues in distributed systems

New problems:

  • Byzantine failures

New resources:

  • Bandwidth
  • Latency (RTTs)

Byzantine failures (aka cheating)

Players are intelligent and malicious agents

Easy solution

Use client-server, one master replica

Cynical Bonus: Scarcity + Control = $$$

Better solution

Peer-to-peer RAFT/PAXOS (?)


Simple estimate for games:

B = k n2

  • B = consumed bandwidth
  • k = input rate
  • n = number of players

Easy solution:

Assume n small (don't make an MMO!)

Better solution

Region of interest management, throttling


Consequence of physics

Easy solution:

Don't make a realtime multiplayer game

Better solution:

Tradeoffs, subject of this talk!

Replication and consistency

Consistency models determine replication algorithms

Strong consistency:

  • Easier to reason about, less non-determinism
  • Requires more coordination, latency

Weak consistency

  • Harder to reason about, bugs
  • Less coordination, lower latency

Lock-step synchronization

Enforce strict linearizability

All players barrier synchronize each tick

Lock-step synchronization


  • Strongest possible model of consistency
  • All players see same sequence of events


  • Input lag >= slowest RTT in network
  • Not robust to failures (eg desync bugs, players drop)

Dead reckoning

Eventual consistency

  • Apply inputs immediately

  • Predict remote events

  • Correct errors


Dead-reckoning with no correction

Dead-reckoning with corrections

Dead-reckoning with severe lag

Dead reckoning


  • No network lag on local input


  • Prediction doesn't always work
  • Correction expensive
  • Visual glitches

Local perception filters

Causal consistency

  • Process input in causal order

  • Local player = sooner

  • Remote player = earlier

P. Sharkey, M. Ryan, D. Roberts. (1998) "A local perception filter for virtual environments" VR Symp.

Commutative (good)

Non-commutative (bad)

Non-commutative (ugly)

Causality in space-time

Physically inspired model of causality

  • No object travels faster than c
  • All objects are points
  • Interactions occur instantly at discrete points
  • Space is flat

See my blog for details

Causal order

Cauchy surfaces

A "snapshot" of the world

Spatial analog of vector clocks

  • Hypersurface in space-time

  • Unique intersection property


Dead reckoning


Time dilation

Implementing local perception filters

  • Persistence

  • Determinism

  • Decoupled rendering

Local perception filters


  • Responsive local inputs

  • Correct ordering of events


  • Can't remove all lag

  • Game must obey relativity

Cheating the system

Players can defer actions by artificial lag

Gives advantage by increasing reaction time

But other players will still see consistent view of events...

What does this look like?

Bullet time

J. Smed, H. Niinisalo, H. Hakonen. (2004) "Realizing bullet time effects in multiplayer games with local perception filters"


Thanks for listening!

Blog posts:

No-interaction theorem

Multibody physics doesn't really work with special relativity

Lorentz invariance or Newton's 3rd law: Pick 1

System is either acausal or unstable