Discrete analog computing with rotor-routers.
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 analogs of continuous linear systems and deterministic analogs of stochastic processes.
Propp
James
J
Mathematical Sciences, UMass Lowell, One University Avenue, Lowell, Massachusetts 01854, USA.