Skip to Main content Skip to Navigation
Journal articles

The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks

Abstract : The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, an agent is initially placed at one of the nodes of the graph. Each node maintains a cyclic ordering of its outgoing arcs, and during successive visits of the agent, propagates it along arcs chosen according to this ordering in round-robin fashion. The behavior of the rotor-router is fully deterministic but its performance characteristics (cover time, return time) closely resemble the expected values of the corresponding parameters of the random walk. In this work Research partially supported by the ANR Project DISPLEXITY (ANR-11-BS02-014). This study has been carried out in the frame of the Investments for the future Programme IdEx Bordeaux-CPU
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-01416011
Contributor : Adrian Kosowski <>
Submitted on : Tuesday, December 1, 2020 - 5:17:32 PM
Last modification on : Tuesday, December 1, 2020 - 5:37:46 PM

File

Klasing2017_Article_TheMulti-a...
Explicit agreement for this submission

Identifiers

Relations

Citation

Ralf Klasing, Adrian Kosowski, Dominik Pająk, Thomas Sauerwald. The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks. Distributed Computing, Springer Verlag, 2017, 30 (2), pp.127-148. ⟨10.1007/s00446-016-0282-y⟩. ⟨hal-01416011⟩

Share

Metrics

Record views

634

Files downloads

5