Afficher la notice abrégée

Euler Tour Lock-in Problem in the Rotor-Router Model

hal.structure.identifierSchool of of Electrical and Computer Engineering [Athens] [School of E.C.E]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorBAMPAS, Evangelos
hal.structure.identifierDepartment of Computer Science [Liverpool]
dc.contributor.authorGASIENIEC, Leszek
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorHANUSSE, Nicolas
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorILCINKAS, David
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.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierDepartment of Algorithms and Systems Modelling [ETI GUT] [Gdansk University of Technology]
dc.contributor.authorKOSOWSKI, Adrian
dc.date.accessioned2024-04-15T09:51:24Z
dc.date.available2024-04-15T09:51:24Z
dc.date.issued2009-09
dc.date.conference2009-09
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198427
dc.description.abstractEnThe rotor-router model, also called the Propp machine, was first considered as a deterministic alternative to the random walk. It is known that the route in an undirected graph G=(V,E), where |V|=n and |E|=m, adopted by an agent controlled by the rotor-router mechanism forms eventually an Euler tour based on arcs obtained via replacing each edge in G by two arcs with opposite direction. The process of ushering the agent to an Euler tour is referred to as the lock-in problem. In recent work [Yan03] Yanovski et al. proved that independently of the initial configuration of the rotor-router mechanism in G the agent locks-in in time bounded by 2m diam, where diam is the diameter of G. This upper bound can be matched asymptotically in lollipop graphs. In this paper we examine the dependence of the lock-in time on the initial configuration of the rotor-router mechanism. The case study is performed in the form of a game between a player pl intending to lock-in the agent in an Euler tour as quickly as possible and its adversary ad with the counter objective. First, we observe that in certain (easy) cases the lock-in can be achieved in time O(m). On the other hand we show that if adversary ad is solely responsible for the assignment of ports and pointers, the lock-in time Omega(m diam) can be enforced in any graph with m edges and diameter diam. Furthermore, we show that if ad provides its own port numbering after the initial setup of pointers by pl, the complexity of the lock-in problem is bounded by O(m min{log m,diam}). We also propose a class of graphs in which the lock-in requires time Omega(m log m). In the remaining two cases we show that the lock-in requires time Omega(m diam) in graphs with the worst-case topology. In addition, however, we present non-trivial classes of graphs with a large diameter in which the lock-in time is O(m).
dc.description.sponsorshipAlgorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
dc.language.isoen
dc.publisherSpringer Berlin / Heidelberg
dc.source.titleProceedings of the 23rd International Symposium on Distributed Computing
dc.title.enEuler Tour Lock-in Problem in the Rotor-Router Model
dc.typeCommunication dans un congrès
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.page421--433
bordeaux.volume5805
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleDISC 2009
bordeaux.countryES
bordeaux.title.proceedingProceedings of the 23rd International Symposium on Distributed Computing
bordeaux.peerReviewedoui
hal.identifierhal-00402749
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00402749v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=Proceedings%20of%20the%2023rd%20International%20Symposium%20on%20Distributed%20Computing&rft.date=2009-09&rft.volume=5805&rft.spage=421--433&rft.epage=421--433&rft.au=BAMPAS,%20Evangelos&GASIENIEC,%20Leszek&HANUSSE,%20Nicolas&ILCINKAS,%20David&KLASING,%20Ralf&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée