Relativistic replication

Mikola Lysenko

University of Wisconsin-Madison

twitter @mikolalysenko | github @mikolalysenko | blog: 0fps.net

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 (?)

Bandwidth

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

Lag

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

Pros:

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

Cons:

  • 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

Lag-free/Lock-step

Dead-reckoning with no correction

Dead-reckoning with corrections

Dead-reckoning with severe lag

Dead reckoning


Pros:

  • No network lag on local input

Cons:

  • 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

Lock-step

Dead reckoning

Adaptive

Time dilation

Implementing local perception filters

  • Persistence

  • Determinism

  • Decoupled rendering

Local perception filters


Pros:

  • Responsive local inputs

  • Correct ordering of events



Cons:

  • 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"

Demo

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