The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Article Dans Une Revue Distributed Computing Année : 2017

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

Résumé

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
Origine : Accord explicite pour ce dépôt

Dates et versions

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

Identifiants

Citer

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⟩

Relations

273 Consultations
57 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More