TY - JOUR

T1 - Robustness of the Rotor–Router Mechanism

AU - Bampas, Evangelos

AU - Gąsieniec, Leszek

AU - Hanusse, Nicolas

AU - Ilcinkas, David

AU - Klasing, Ralf

AU - Kosowski, Adrian

AU - Radzik, Tomasz

N1 - Funding Information:
Parts of this work appear in preliminary form in the Proceedings of the 23rd International Symposium on Distributed Computing, LNCS vol. 5805, pp. 423–435, Springer, 2009 and in the Proceedings of the 13th International Conference on Principles of Distributed Systems, LNCS vol. 5923, pp. 345–358, Springer, 2009. 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 (ANR-10-IDEX-03-02).
Publisher Copyright:
© 2016, Springer Science+Business Media New York.

PY - 2017/7/1

Y1 - 2017/7/1

N2 - The rotor–router model, also called the Propp machine, was first considered as a deterministic 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 eventually forms 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 2 mD, 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 worst-case complexity of the lock-in problem is Θ(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 new Eulerian cycle is established within O(km) steps.

AB - The rotor–router model, also called the Propp machine, was first considered as a deterministic 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 eventually forms 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 2 mD, 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 worst-case complexity of the lock-in problem is Θ(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 new Eulerian cycle is established within O(km) steps.

KW - Dynamic graphs

KW - Graph exploration

KW - Network faults

KW - Propp machine

KW - Rotor–router mechanism

UR - http://www.scopus.com/inward/record.url?scp=84976388749&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84976388749&partnerID=8YFLogxK

U2 - 10.1007/s00453-016-0179-y

DO - 10.1007/s00453-016-0179-y

M3 - Article

AN - SCOPUS:84976388749

SN - 0178-4617

VL - 78

SP - 869

EP - 895

JO - Algorithmica

JF - Algorithmica

IS - 3

ER -