Discrete analogue computing with rotor-routers
arXiv:1007.2389 · doi:10.1063/1.3489886
Abstract
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.
arXiv commentTo appear in Chaos Special Focus Issue on Intrinsic and Designed Computation
References in corpus (9)
- Eulerian Walkers as a model of Self-Organised Criticality
- Chip-Firing and Rotor-Routing on Directed Graphs
- Strong Spherical Asymptotics for Rotor-Router Aggregation and the Divisible Sandpile
- Scaling Limits for Internal Aggregation Models with Multiple Sources
- Studying Self-Organized Criticality with Exactly Solved Models
- Dynamics of Eulerian walkers
- Fast simulation of large-scale growth models
- Critical Dynamics of Self-Organizing Eulerian Walkers
- Internal Diffusion-Limited Aggregation: Parallel Algorithms and Complexity