The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks - Archive ouverte HAL Access content directly
Journal Articles Distributed Computing Year : 2017

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

(1) , (2) , (1) , (3)
1
2
3

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
Fichier principal
Vignette du fichier
Klasing2017_Article_TheMulti-agentRotor-routerOnTh.pdf (692.72 Ko) Télécharger le fichier
Origin : Explicit agreement for this submission

Dates and versions

hal-01416011 , version 1 (01-12-2020)

Identifiers

Cite

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, 2017, 30 (2), pp.127-148. ⟨10.1007/s00446-016-0282-y⟩. ⟨hal-01416011⟩
258 View
53 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More