Robustness of the Rotor–Router Mechanism
International audience The rotor-router model, also called the Propp machine, was first considered as a deter-ministic alternative to the random walk. The edges adjacent to each node v (or equivalently, the exit ports at v) are arranged in a fixed cyclic order, which does not change during the explo...
Published in: | Algorithmica |
---|---|
Main Authors: | , , , , , , |
Other Authors: | , , , , , , , , , , , , |
Format: | Article in Journal/Newspaper |
Language: | English |
Published: |
HAL CCSD
2017
|
Subjects: | |
Online Access: | https://inria.hal.science/hal-01416012 https://inria.hal.science/hal-01416012/document https://inria.hal.science/hal-01416012/file/rotorjv.pdf https://doi.org/10.1007/s00453-016-0179-y |
id |
ftanrparis:oai:HAL:hal-01416012v1 |
---|---|
record_format |
openpolar |
institution |
Open Polar |
collection |
Portail HAL-ANR (Agence Nationale de la Recherche) |
op_collection_id |
ftanrparis |
language |
English |
topic |
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] |
spellingShingle |
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] Bampas, Evangelos Gąsieniec, Leszek Hanusse, Nicolas Ilcinkas, David Klasing, Ralf Kosowski, Adrian Radzik, Tomasz Robustness of the Rotor–Router Mechanism |
topic_facet |
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] |
description |
International audience The rotor-router model, also called the Propp machine, was first considered as a deter-ministic alternative to the random walk. The edges adjacent to each node v (or equivalently, the exit ports at v) are arranged in a fixed cyclic order, which does not change during the exploration. Each node v maintains a port pointer π(v) which indicates the exit port to be adopted by an agent on the conclusion of the next visit to this node (the "next exit port"). The rotor-router mechanism guarantees that after each consecutive visit at the same node, the pointer at this node is moved to the next port in the cyclic order. It is known that, in an undirected graph G with m edges, the route 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 [Yanovski et al., Algorithmica 37(3), 165–186 (2003)], it was proved that, independently of the initial configuration of the rotor-router mechanism in G, the agent locks-in in time bounded by 2mD, where D is the diameter of G. In this paper we examine the dependence of the lock-in time on the initial configuration of the rotor-router mechanism. Our analysis is performed in the form of a game between a player P intending to lock-in the agent in an Euler tour as quickly as possible and its adversary A with the counter objective. We consider all cases of who decides the initial cyclic orders and the initial values π(v). We show, for example, that if A provides its own port numbering after the initial setup of pointers by P, the complexity of the lock-in problem is O(m·min{log m, D}). We also investigate the robustness of the rotor-router graph exploration in presence of faults in the pointers π(v) or dynamic changes in the graph. We show, for example, that after the exploration establishes an Eulerian cycle, if k edges are added to the graph, then a ... |
author2 |
Laboratoire d'informatique Fondamentale de Marseille (LIF) Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS) Department of Computer Science Liverpool University of Liverpool Laboratoire Bordelais de Recherche en Informatique (LaBRI) Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS) Networks, Graphs and Algorithms (GANG) Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)) Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria) King‘s College London ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011) ANR-10-IDEX-0003,IDEX BORDEAUX,Initiative d'excellence de l'Université de Bordeaux(2010) |
format |
Article in Journal/Newspaper |
author |
Bampas, Evangelos Gąsieniec, Leszek Hanusse, Nicolas Ilcinkas, David Klasing, Ralf Kosowski, Adrian Radzik, Tomasz |
author_facet |
Bampas, Evangelos Gąsieniec, Leszek Hanusse, Nicolas Ilcinkas, David Klasing, Ralf Kosowski, Adrian Radzik, Tomasz |
author_sort |
Bampas, Evangelos |
title |
Robustness of the Rotor–Router Mechanism |
title_short |
Robustness of the Rotor–Router Mechanism |
title_full |
Robustness of the Rotor–Router Mechanism |
title_fullStr |
Robustness of the Rotor–Router Mechanism |
title_full_unstemmed |
Robustness of the Rotor–Router Mechanism |
title_sort |
robustness of the rotor–router mechanism |
publisher |
HAL CCSD |
publishDate |
2017 |
url |
https://inria.hal.science/hal-01416012 https://inria.hal.science/hal-01416012/document https://inria.hal.science/hal-01416012/file/rotorjv.pdf https://doi.org/10.1007/s00453-016-0179-y |
genre |
The Pointers |
genre_facet |
The Pointers |
op_source |
ISSN: 0178-4617 EISSN: 1432-0541 Algorithmica https://inria.hal.science/hal-01416012 Algorithmica, 2017, 78 (3), pp.869-895. ⟨10.1007/s00453-016-0179-y⟩ |
op_relation |
info:eu-repo/semantics/altIdentifier/doi/10.1007/s00453-016-0179-y hal-01416012 https://inria.hal.science/hal-01416012 https://inria.hal.science/hal-01416012/document https://inria.hal.science/hal-01416012/file/rotorjv.pdf doi:10.1007/s00453-016-0179-y |
op_rights |
info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.1007/s00453-016-0179-y |
container_title |
Algorithmica |
container_volume |
78 |
container_issue |
3 |
container_start_page |
869 |
op_container_end_page |
895 |
_version_ |
1810483438437793792 |
spelling |
ftanrparis:oai:HAL:hal-01416012v1 2024-09-15T18:39:03+00:00 Robustness of the Rotor–Router Mechanism Bampas, Evangelos Gąsieniec, Leszek Hanusse, Nicolas Ilcinkas, David Klasing, Ralf Kosowski, Adrian Radzik, Tomasz Laboratoire d'informatique Fondamentale de Marseille (LIF) Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS) Department of Computer Science Liverpool University of Liverpool Laboratoire Bordelais de Recherche en Informatique (LaBRI) Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS) Networks, Graphs and Algorithms (GANG) Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)) Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria) King‘s College London ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011) ANR-10-IDEX-0003,IDEX BORDEAUX,Initiative d'excellence de l'Université de Bordeaux(2010) 2017-07 https://inria.hal.science/hal-01416012 https://inria.hal.science/hal-01416012/document https://inria.hal.science/hal-01416012/file/rotorjv.pdf https://doi.org/10.1007/s00453-016-0179-y en eng HAL CCSD Springer Verlag info:eu-repo/semantics/altIdentifier/doi/10.1007/s00453-016-0179-y hal-01416012 https://inria.hal.science/hal-01416012 https://inria.hal.science/hal-01416012/document https://inria.hal.science/hal-01416012/file/rotorjv.pdf doi:10.1007/s00453-016-0179-y info:eu-repo/semantics/OpenAccess ISSN: 0178-4617 EISSN: 1432-0541 Algorithmica https://inria.hal.science/hal-01416012 Algorithmica, 2017, 78 (3), pp.869-895. ⟨10.1007/s00453-016-0179-y⟩ [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] info:eu-repo/semantics/article Journal articles 2017 ftanrparis https://doi.org/10.1007/s00453-016-0179-y 2024-07-12T11:32:49Z International audience The rotor-router model, also called the Propp machine, was first considered as a deter-ministic alternative to the random walk. The edges adjacent to each node v (or equivalently, the exit ports at v) are arranged in a fixed cyclic order, which does not change during the exploration. Each node v maintains a port pointer π(v) which indicates the exit port to be adopted by an agent on the conclusion of the next visit to this node (the "next exit port"). The rotor-router mechanism guarantees that after each consecutive visit at the same node, the pointer at this node is moved to the next port in the cyclic order. It is known that, in an undirected graph G with m edges, the route 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 [Yanovski et al., Algorithmica 37(3), 165–186 (2003)], it was proved that, independently of the initial configuration of the rotor-router mechanism in G, the agent locks-in in time bounded by 2mD, where D is the diameter of G. In this paper we examine the dependence of the lock-in time on the initial configuration of the rotor-router mechanism. Our analysis is performed in the form of a game between a player P intending to lock-in the agent in an Euler tour as quickly as possible and its adversary A with the counter objective. We consider all cases of who decides the initial cyclic orders and the initial values π(v). We show, for example, that if A provides its own port numbering after the initial setup of pointers by P, the complexity of the lock-in problem is O(m·min{log m, D}). We also investigate the robustness of the rotor-router graph exploration in presence of faults in the pointers π(v) or dynamic changes in the graph. We show, for example, that after the exploration establishes an Eulerian cycle, if k edges are added to the graph, then a ... Article in Journal/Newspaper The Pointers Portail HAL-ANR (Agence Nationale de la Recherche) Algorithmica 78 3 869 895 |