Mostrar el registro sencillo del ítem

The Multi-Agent Rotor-Router on the Ring: A Deterministic Alternative to Parallel Random Walks

hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorKLASING, Ralf
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierCombinatoire et Algorithmique
dc.contributor.authorKOSOWSKI, Adrian
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorPAJAK, Dominik
hal.structure.identifierMax-Planck-Institut für Informatik [MPII]
dc.contributor.authorSAUERWALD, Thomas
dc.date.accessioned2024-04-15T09:58:02Z
dc.date.available2024-04-15T09:58:02Z
dc.date.issued2013-07-22
dc.date.conference2013-07-22
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198966
dc.description.abstractEnThe \emph{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 we study the scenario in which multiple, indistinguishable agents are deployed in parallel in the nodes of the graph, and move around the graph in synchronous rounds, interacting with a single rotor-router system. This setting was introduced by Yanovski~\etal\ (2003). We propose new techniques which allow us to compare this model theoretically with the intensively studied scenario of parallel independent random walks in a graph. Our main results concern the $n$-node ring, and suggest a strong similarity between the performance characteristics of both models. We show that the rotor-router with $k$ agents achieves on the ring a cover time of between $\Theta (n^2 / k^2)$ and $\Theta (n^2 / \log k)$, depending on the initial locations of the agents, and both these bounds are tight. The corresponding expected values of cover time for $k$ random walks are proved to be $\Theta (n^2 / (k^2/\log^2 k))$ and $\Theta (n^2 / \log k)$. We then show that after the rotor-router system has stabilized, all nodes of the ring are always visited every $\Theta (n / k)$ steps, regardless of initialization. This corresponds asymptotically to the expected time between visits in the case of $k$ random walks. All our results hold up to a polynomially large number of agents ($1 \leq k < n^{1/11}$).
dc.description.sponsorshipCalculabilité et complexité en distribué - ANR-11-BS02-0014
dc.language.isoen
dc.publisherACM
dc.title.enThe Multi-Agent Rotor-Router on the Ring: A Deterministic Alternative to Parallel Random Walks
dc.typeCommunication dans un congrès
dc.identifier.doi10.1145/2484239.2484260
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.page365-374
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titlePODC 2013 - ACM Symposium on Principles of Distributed Computing
bordeaux.countryCA
bordeaux.conference.cityMontreal
bordeaux.peerReviewedoui
hal.identifierhal-00735113
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00735113v1
bordeaux.COinSctx_ver=Z39.88-2004&amp;rft_val_fmt=info:ofi/fmt:kev:mtx:journal&amp;rft.date=2013-07-22&amp;rft.spage=365-374&amp;rft.epage=365-374&amp;rft.au=KLASING,%20Ralf&amp;KOSOWSKI,%20Adrian&amp;PAJAK,%20Dominik&amp;SAUERWALD,%20Thomas&amp;rft.genre=unknown


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem