Discrete analogue computing with rotor-routers

Understand

Rotor-routing is a procedure for routing tokens through a network that can implement certain kinds of computation.

• These computations are inherently asynchronous (the order in which tokens are routed makes no difference) and distributed (information is spread throughout the system).
• It is also possible to efficiently check that a computation has been carried out correctly in less time than the computation itself required, provided one has a certificate that can itself be computed by the rotor-router network.
• Rotor-router networks can be viewed as both discrete analogues of continuous linear systems and deterministic analogues of stochastic processes.