Discrete analog computing with rotor-routers

DOI10.1063/1.3489886MaRDI QIDQ5251239zbMATH OpenOpenAlexWikidataFDO

Authors James Propp

Publication date 19 May 2015

Published in Chaos: An Interdisciplinary Journal of Nonlinear Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.2389

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Network design and communication in computer systems (68M10) Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

• Limit behavior of the multi-agent rotor-router system
• Deterministic random walks on finite graphs
• Deterministic random walks on finite graphs
• Algorithmic aspects of rotor-routing and the notion of linear equivalence
• Robustness of the rotor-router mechanism

Cites work

• Deterministic random walks on the integers
• Deterministic random walks on the two-dimensional grid
• Goldbug variations
• scientific article; zbMATH DE number 3934150 (Why is no real title available?)
• Internal diffusion limited aggregation
• Internal diffusion-limited aggregation: parallel algorithms and complexity
• Random walks, capacity and percolation on trees
• Simulating a Random Walk with Constant Error
• Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile
• The probabilistic abacus
• Why does the probabilistic abacus work?

Cited in

(3)

• A growth model based on the arithmetic \(Z\)-game
• Abelian networks. I: Foundations and examples
• Proportionate growth in patterns formed in the rotor-router model

This page was built for publication: Discrete analog computing with rotor-routers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5251239)