Search

We propose a general scheme to compute tree-based data structures on arbitrary networks. This scheme is self-stabilizing, silent, and despite its generality, also efficient. It is written in the locally shared memory model with composite atomicity assuming the distributed unfair daemon, the weakest scheduling assumption of the model. Its stabilization time is in at most 4 n maxCC rounds, where n maxCC is the maximum number of processes in any connected component of the network. We illustrate the versatility and efficiency of our approach by proposing several instantiations solving classical spanning tree problems such as DFS, BFS, shortest-path, or unconstrained spanning tree/forest constructions, as well as other fundamental problems like leader election or finding maximum-bottleneck-bandwidth paths. We also exhibit polynomial upper bounds on its stabilization time in steps and process moves, holding for a large class of instantiations. In several cases, the polynomial step and move complexities we obtain for those instantiations match the best known complexities of existing algorithms, despite the latter being dedicated to particular problems. Furthermore, a significant set of instantiations of our scheme requires only bounded memory space per process. This set includes, but is not limited to, DFS, BFS, and shortest-path spanning tree constructions. [ABSTRACT FROM AUTHOR]

We study the problem of exploration by a mobile entity (agent) of a class of dynamic networks, namely constantly connected dynamic graphs. This problem has already been studied in the case where the agent knows the dynamics of the graph and the underlying graph is a ring of n vertices (Ilcinkas and Wade 2018). In this paper, we consider the same problem and we suppose that the underlying graph is a cactus graph (a connected graph in which any two simple cycles have at most one vertex in common). We propose an algorithm that allows the agent to explore these dynamic graphs in at most O (n log n log log n) time units. We show that the lower bound of the algorithm is Ω (n log n (log log n) 2 ) time units (for infinitely many n). [ABSTRACT FROM AUTHOR]

We study the problem of exploration by a mobile entity (agent) of a class of highly dynamic networks, namely the carrier graphs (the C-graphs, modeling public transportation systems, among others). These are defined by a set of carriers following infinitely their prescribed route along the stations of the network. Flocchini, Mans, and Santoro [9] studied this problem in the case when the agent must always travel on the carriers and thus cannot wait on a station. They described the necessary and sufficient conditions for the problem to be solvable and proved that the optimal worst-case number of time units (and thus of moves) to explore a n -node C-graph of k carriers and maximal period p is in Θ (k p 2) in the general case. In this paper, we study the impact of the ability to wait at the stations. We exhibit the necessary and sufficient conditions for the problem to be solvable in this context, and we prove that waiting at the stations allows the agent to reduce the optimal worst-case number of moves by a multiplicative factor of at least Θ (p) , while the worst-case time complexity is reduced to Θ (n p). (In any connected carrier graph, we have n ≤ k p.) We also show some complementary optimal results in specific cases (same period for all carriers, highly connected C-graphs). Finally this new ability allows the agent to completely map the C-graph, in addition to just exploring it. [ABSTRACT FROM AUTHOR]

In this paper, we study the T-interval-connected dynamic graphs from the point of view of the time necessary and sufficient for their exploration by a mobile entity (agent). A dynamic graph (more precisely, an evolving graph) is T-interval-connected (T ≥ 1) if, for every window of T consecutive time steps, there exists a connected spanning subgraph that is stable (always present) during this period. This property of connection stability over time was introduced by Kuhn, Lynch and Oshman (Kuhn et al. 14) (STOC 2010). We focus on the case when the underlying graph is a ring of size n, and we show that the worst-case time complexity for the exploration problem is 2n − T − Θ(1) time units if the agent knows the dynamics of the graph, and n+nmax{1,T−1}(δ−1)±Θ(δ) time units otherwise, where δ is the maximum time between two successive appearances of an edge. [ABSTRACT FROM AUTHOR]

Abstract: A mobile robot represented by a point moving in the plane has to explore an unknown flat terrain with impassable obstacles. Both the terrain and the obstacles are modeled as arbitrary polygons. We consider two scenarios: the unlimited vision, when the robot situated at a point p of the terrain explores (sees) all points q of the terrain for which the segment pq belongs to the terrain, and the limited vision, when we require additionally that the distance between p and q is at most 1. All points of the terrain (except obstacles) have to be explored and the performance of an exploration algorithm, called its complexity, is measured by the length of the trajectory of the robot. For unlimited vision we show an exploration algorithm with complexity , where P is the total perimeter of the terrain (including perimeters of obstacles), D is the diameter of the convex hull of the terrain, and k is the number of obstacles. We do not assume knowledge of these parameters. We also prove a matching lower bound showing that the above complexity is optimal, even if the terrain is known to the robot. For limited vision we show exploration algorithms with complexity , where A is the area of the terrain (excluding obstacles). Our algorithms work either for arbitrary terrains (if one of the parameters A or k is known) or for c-fat terrains, where c is any constant (unknown to the robot) and no additional knowledge is assumed. (A terrain with obstacles is c-fat if , where R is the radius of the smallest disc containing and r is the radius of the largest disc contained in .) We also prove a matching lower bound on the complexity of exploration for limited vision, even if the terrain is known to the robot. [Copyright &y& Elsevier]

We consider the problem of exploring an anonymous unoriented ring by a team of k identical, oblivious, asynchronous mobile robots that can view the environment but cannot communicate. This weak scenario is standard when the spatial universe in which the robots operate is the two-dimensional plane, but (with one exception) has not been investigated before for networks. Our results imply that, although these weak capabilities of robots render the problem considerably more difficult, ring exploration by a small team of robots is still possible. We first show that, when k and n are not co-prime, the problem is not solvable in general, e.g., if k divides n there are initial placements of the robots for which gathering is impossible. We then prove that the problem is always solvable provided that n and k are co-prime, for k≥17, by giving an exploration algorithm that always terminates, starting from arbitrary initial configurations. Finally, we consider the minimum number ρ( n) of robots that can explore a ring of size n. As a consequence of our positive result we show that ρ( n) is O(log n). We additionally prove that Ω(log n) robots are necessary for infinitely many n. [ABSTRACT FROM AUTHOR]

We prove that, for the black hole search problem in networks of arbitrary but known topology, the pebble model of agent interaction is computationally as powerful as the whiteboard model; furthermore the complexity is exactly the same. More precisely, we prove that a team of two asynchronous agents, each endowed with a single identical pebble (that can be placed only on nodes, and with no more than one pebble per node), can locate the black hole in an arbitrary network of known topology; this can be done with Θ( nlog n) moves, where n is the number of nodes, even when the links are not FIFO. These results are obtained with a novel algorithmic technique, ping-pong, for agents using pebbles. [ABSTRACT FROM AUTHOR]

Abstract: Two mobile agents (robots) have to meet in an a priori unknown bounded terrain modeled as a polygon, possibly with polygonal obstacles. Robots are modeled as points, and each of them is equipped with a compass. Compasses of robots may be incoherent. Robots construct their routes, but the actual walk of each robot is decided by the adversary that may, e.g., speed up or slow down the robot. We consider several scenarios, depending on three factors: (1) obstacles in the terrain are present, or not, (2) compasses of both robots agree, or not, (3) robots have or do not have a map of the terrain with their positions marked. The cost of a rendezvous algorithm is the worst-case sum of lengths of the robots’ trajectories until they meet. For each scenario, we design a deterministic rendezvous algorithm and analyze its cost. We also prove lower bounds on the cost of any deterministic rendezvous algorithm in each case. For all scenarios these bounds are tight. [Copyright &y& Elsevier]

We consider the problem of exploring an anonymous undirected graph using an oblivious robot. The studied exploration strategies are designed so that the next edge in the robot's walk is chosen using only local information, and so that some local equity (fairness) criterion is satisfied for the adjacent undirected edges. Such strategies can be seen as an attempt to derandomize random walks, and are natural counterparts for undirected graphs of the rotor-router model for symmetric directed graphs. The first of the studied strategies, known as Oldest-First, always chooses the neighboring edge for which the most time has elapsed since its last traversal. Unlike in the case of symmetric directed graphs, we show that such a strategy in some cases leads to exponential cover time. We then consider another strategy called Least-Used-First which always uses adjacent edges which have been traversed the smallest number of times. We show that any Least-Used-First exploration covers a graph G = ( V, E) of diameter D within time O( D| E|), and in the long run traverses all edges of G with the same frequency. [ABSTRACT FROM AUTHOR]

Abstract: We study the amount of knowledge about a communication network that must be given to its nodes in order to efficiently disseminate information. Our approach is quantitative: we investigate the minimum total number of bits of information (minimum size of advice) that has to be available to nodes, regardless of the type of information provided. We compare the size of advice needed to perform broadcast and wakeup (the latter is a broadcast in which nodes can transmit only after getting the source information), both using a linear number of messages (which is optimal). We show that the minimum size of advice permitting the wakeup with a linear number of messages in an n-node network, is , while the broadcast with a linear number of messages can be achieved with advice of size . We also show that the latter size of advice is almost optimal: no advice of size can permit to broadcast with a linear number of messages. Thus an efficient wakeup requires strictly more information about the network than an efficient broadcast. [Copyright &y& Elsevier]

Abstract: In an effort to understand the algorithmic limitations of computing by a swarm of robots, the research has focused on the minimal capabilities that allow a problem to be solved. The weakest of the commonly used models is Asynch where the autonomous mobile robots, endowed with visibility sensors (but otherwise unable to communicate), operate in Look-Compute-Move cycles performed asynchronously for each robot. The robots are often assumed (or required to be) oblivious: they keep no memory of observations and computations made in previous cycles. We consider the setting when the robots are dispersed in an anonymous and unlabeled graph, and they must perform the very basic task of exploration: within finite time every node must be visited by at least one robot and the robots must enter a quiescent state. The complexity measure of a solution is the number of robots used to perform the task. We study the case when the graph is an arbitrary tree and establish some unexpected results. We first prove that, in general, exploration cannot be done efficiently. More precisely we prove that there are -node trees where robots are necessary; this holds even if the maximum degree is . On the other hand, we show that if the maximum degree is , it is possible to explore with only robots. The proof of the result is constructive. We also prove that the size of the team used in our solution is asymptotically optimal: there are trees of degree , whose exploration requires robots. Our final result shows that the difficulty in tree exploration comes in fact from the symmetries of the tree. Indeed, we show that, in order to explore trees that do not have any non-trivial automorphisms, 4 robots are always sufficient and often necessary. [Copyright &y& Elsevier]

Abstract: We study deterministic broadcasting in radio networks in the recently introduced framework of network algorithms with advice. We concentrate on the problem of trade-offs between the number of bits of information (size of advice) available to nodes and the time in which broadcasting can be accomplished. In particular, we ask what is the minimum number of bits of information that must be available to nodes of the network, in order to broadcast very fast. For networks in which constant time broadcast is possible under a complete knowledge of the network we give a tight answer to the above question: bits of advice are sufficient but bits are not, in order to achieve constant broadcasting time in all these networks. This is in sharp contrast with geometric radio networks of constant broadcasting time: we show that in these networks a constant number of bits suffices to broadcast in constant time. For arbitrary radio networks we present a broadcasting algorithm whose time is inverse-proportional to the size of the advice. [Copyright &y& Elsevier]

Blin et al. (Theor Comput Sci 399(1–2):12–37, 2008) proposed a distributed protocol enabling the smallest possible number of searchers to clear any unknown graph in a decentralized manner. However, the strategy that is actually performed lacks of an important property, namely the monotonicity. This paper deals with the smallest number of searchers that are necessary and sufficient to monotonously clear any unknown graph in a decentralized manner. The clearing of the graph is required to be connected, i.e., the clear part of the graph must remain permanently connected, and monotone, i.e., the clear part of the graph only grows. We prove that a distributed protocol clearing any unknown n-node graph in a monotone connected way, in a decentralized setting, can achieve but cannot beat competitive ratio of $${\Theta(\frac{n}{\log n})}$$ , compared with the centralized minimum number of searchers. Moreover, our lower bound holds even in a synchronous setting, while our constructive upper bound holds even in an asynchronous setting. [ABSTRACT FROM AUTHOR]

Abstract: We study the amount of knowledge about the network that is required in order to efficiently solve a task concerning this network. The impact of available information on the efficiency of solving network problems, such as communication or exploration, has been investigated before but assumptions concerned availability of particular items of information about the network, such as the size, the diameter, or a map of the network. In contrast, our approach is quantitative: we investigate the minimum number of bits of information (bits of advice) that has to be given to an algorithm in order to perform a task with given efficiency. We illustrate this quantitative approach to available knowledge by the task of tree exploration. A mobile entity (robot) has to traverse all edges of an unknown tree, using as few edge traversals as possible. The quality of an exploration algorithm is measured by its competitive ratio, i.e., by comparing its cost (number of edge traversals) to the length of the shortest path containing all edges of the tree. Depth-First-Search has competitive ratio 2 and, in the absence of any information about the tree, no algorithm can beat this value. We determine the minimum number of bits of advice that has to be given to an exploration algorithm in order to achieve competitive ratio strictly smaller than 2. Our main result establishes an exact threshold number of bits of advice that turns out to be roughly , where D is the diameter of the tree. More precisely, for any constant c, we construct an exploration algorithm with competitive ratio smaller than 2, using at most bits of advice, and we show that every algorithm using bits of advice, for any function g unbounded from above, has competitive ratio at least 2. [Copyright &y& Elsevier]

Abstract: We consider the problem of periodic graph exploration by a finite automaton in which an automaton with a constant number of states has to explore all unknown anonymous graphs of arbitrary size and arbitrary maximum degree. In anonymous graphs, nodes are not labeled but edges are labeled in a local manner (called local orientation) so that the automaton is able to distinguish them. Precisely, the edges incident to a node are given port numbers from to , where is the degree of . Periodic graph exploration means visiting every node infinitely often. We are interested in the length of the period, i.e., the maximum number of edge traversals between two consecutive visits of any node by the automaton in the same state and entering the node by the same port. This problem is unsolvable if local orientations are set arbitrarily. Given this impossibility result, we address the following problem: what is the minimum function such that there exists an algorithm for setting the local orientation, and a finite automaton using it, such that the automaton explores all graphs of size within the period ? The best result so far is the upper bound , by Dobrev et al. [S. Dobrev, J. Jansson, K. Sadakane, W.-K. Sung, Finding short right-hand-on-the-wall walks in graphs, in: 12th Colloquium on Structural Information and Communication Complexity, SIROCCO, in: LNCS, vol. 3499, 2005, pp. 127–139], using an automaton with no memory (i.e. only one state). In this paper we prove a better upper bound . Our automaton uses three states but performs periodic exploration independently of its starting position and initial state. [Copyright &y& Elsevier]

Abstract: A mobile agent (robot), modeled as a finite automaton, has to visit all nodes of a regular graph. How does the memory size of the agent (the number of states of the automaton) influence its exploration capability? In particular, does every increase of the memory size enable an agent to explore more graphs? We give a partial answer to this problem by showing that a strict gain of the exploration power can be obtained by a polynomial increase of the number of states. We also show that, for automata with few states, the increase of memory by even one state results in the capability of exploring more graphs. [Copyright &y& Elsevier]

The behavior of rational selfish agents has been classically studied in the framework of strategic games in which each player has a set of possible actions, players choose actions simultaneously and the payoff for each player is determined by the matrix of the game. However, in many applications, players choose actions asynchronously, and simultaneity of this process is not guaranteed: it is possible that a player learns the action of another player before making its choice. Delays of choices are controled by the adversary and each player can only secure the worst-case payoff over the adversary's decisions. In this paper we consider such asynchronous versions of arbitrary two-person strategic games and we study how the presence of the asynchronous adversary influences the behavior of the players, assumed to be selfish but rational. We concentrate on deterministic (pure) strategies, and in particular, on the existence and characteristics of pure Nash equilibria in such games. It turns out that the rational behavior of players changes significantly if the decision process is asynchronous. We show that pure Nash equilibria often exist in the asynchronous version of the game even if there were no such equilibria in the synchronous game. We also show that a mere threat of asynchrony in the game may make social optimum a rational choice while it was not rational in the synchronous game. [ABSTRACT FROM AUTHOR]

Abstract: A finite automaton, simply referred to as a robot, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the graph or of its size. Its task is to traverse all the edges of the graph. We first show that, for any K-state robot and any , there exists a planar graph of maximum degree d with at most nodes that the robot cannot explore. This bound improves all previous bounds in the literature. More interestingly, we show that, in order to explore all graphs of diameter D and maximum degree d, a robot needs memory bits, even if we restrict the exploration to planar graphs. This latter bound is tight. Indeed, a simple DFS up to depth enables a robot to explore any graph of diameter D and maximum degree d using a memory of size bits. We thus prove that the worst case space complexity of graph exploration is bits. [Copyright &y& Elsevier]

Given a boolean predicate on labeled networks (e.g., the network is acyclic, or the network is properly colored, etc.), deciding in a distributed manner whether a given labeled network satisfies that predicate typically consists, in the standard setting, of every node inspecting its close neighborhood, and outputting a boolean verdict, such that the network satisfies the predicate if and only if all nodes output true. In this paper, we investigate a more general notion of distributed decision in which every node is allowed to output a constant number b ≥ 1 of bits, which are gathered by a central authority emitting a global boolean verdict based on these outputs, such that the network satisfies the predicate if and only if this global verdict equals true. We analyze the power and limitations of this extended notion of distributed decision. [ABSTRACT FROM AUTHOR]

A group of mobile robots (beachcombers) have to search collectively every point of a given domain. At any given moment, each robot can be in walking mode or in searching mode. It is assumed that each robot's maximum allowed searching speed is strictly smaller than its maximum allowed walking speed. A point of the domain is searched if at least one of the robots visits it in searching mode. The Beachcombers' Problem consists in developing efficient schedules (algorithms) for the robots which collectively search all the points of the given domain as fast as possible. We consider searching schedules in the following one-dimensional geometric domains: the cycle of a known circumference L , the finite straight line segment of a known length L , and the semi-infinite line [ 0 , + ∞). We first consider the online Beachcombers' Problem (i.e. the scenario when the robots do not know in advance the length of the segment to be searched), where the robots are initially collocated at the origin of a semi-infinite line. It is sought to design a schedule A with maximum speed S , defined as S = inf ℓ ⁡ ℓ t A (ℓ) , where t A (ℓ) denotes the time when the search of the segment [ 0 , ℓ ] is completed under A. We consider a discrete and a continuous version of the problem, depending on whether the infimum is taken over ℓ ∈ N ⁎ or ℓ ≥ 1. We prove that the LeapFrog algorithm, which was proposed in Czyzowicz et al. (2015) [12] , is in fact optimal in the discrete case. This settles in the affirmative a conjecture from that paper. We also show how to extend this result to the more general continuous online setting. For the offline version of the Beachcombers' Problem (i.e. the scenario when the robots know in advance the length of the segment to be searched), we consider the t-source Beachcombers' Problem (i.e. all robots start from a fixed number t ≥ 1 of starting positions) on the cycle and on the finite segment. For the t-source Beachcombers' Problem on the cycle, we show that the structure of the optimal solutions is identical to the structure of the optimal solutions to the 2 t -source Beachcombers' Problem on a finite segment. In consequence, by using results from Czyzowicz et al. (2014) [13] , we prove that the 1-source Beachcombers' Problem on the cycle is NP-hard, and we derive approximation algorithms for the problem. For the t-source variant of the Beachcombers' Problem on the cycle and on the finite segment, we also derive efficient approximation algorithms. One important contribution of our work is that, in all variants of the offline Beachcombers' Problem that we discuss, we allow the robots to change direction of movement and search points of the domain on both sides of their respective starting positions. This represents a significant generalization compared to the model considered in Czyzowicz et al. (2014) [13] , in which each robot had a fixed direction of movement that was specified as part of the solution to the problem. We manage to prove that changes of direction do not help the robots achieve optimality. [ABSTRACT FROM AUTHOR]

Many articles deal with the problem of maintaining a rooted shortest-path tree. However, after some edge deletions, some nodes can be disconnected from the connected component V r of some distinguished node r. In this case, an additional objective is to ensure the detection of the disconnection by the nodes that no longer belong to V r. We present a detailed analysis of a silent self-stabilizing algorithm. We prove that it solves this more demanding task in anonymous weighted networks with the following additional strong properties: it runs without any knowledge on the network and under the unfair daemon, that is without any assumption on the asynchronous model. Moreover, it terminates in less than 2 n + D rounds for a network of n nodes and hop-diameter D. • A self-stabilizing algorithm maintaining shortest paths is proposed. • The algorithm also detects disconnected components. • Our algorithm is silent and works properly under the unfair distributed daemon. • We prove a linear upper bound on the number of rounds of the algorithm. • A lower bound on the number of steps of the algorithm is provided. [ABSTRACT FROM AUTHOR]

In order to achieve routing in a graph, nodes need to store routing information. In the case of shortest path routing, for a given destination, every node has to store an advice that is an outgoing link toward a neighbor. If this neighbor does not belong to a shortest path then the advice is considered as an error and the node giving this advice will be qualified a liar . This article focuses on the impact of graph dynamics on the advice set for a given destination. More precisely we show that, for a weighted graph G of diameter D with n nodes and m edges, the expected number of errors after M edge deletions is bounded by O ( n ⋅ M ⋅ D / m ) . We also show that this bound is tight when M = O ( n ) . Moreover, for M ′ node deletions, the expected number of errors is O ( M ′ ⋅ D ) . Finally we show that after a single edge addition the expected number of liars can be Θ ( n ) for some families of graphs. [ABSTRACT FROM AUTHOR]

We study the problem of the amount of information (advice) about a graph that must be given to its nodes in order to achieve fast distributed computations. The required size of the advice enables to measure the information sensitivity of a network problem. A problem is information sensitive if little advice is enough to solve the problem rapidly (i.e., much faster than in the absence of any advice), whereas it is information insensitive if it requires giving a lot of information to the nodes in order to ensure fast computation of the solution. In this paper, we study the information sensitivity of distributed graph coloring. [ABSTRACT FROM AUTHOR]

Abstract A pair of agents (robots) are moving in a graph with the goal of meeting at the same node or while traversing the same edge. An asynchronous adversary knows the prescribed walks of the two agents and is in complete control of the speed of each agent during its walk. We provide a complete characterization of pairs of walks that enforce rendezvous against an asynchronous adversary after traversing a given number of edges. The characterization is efficient in that it can be checked in polynomial time. We argue that the certificate of rendezvous enforcement that is produced by the checking algorithm contains a wealth of information on why rendezvous is enforced. [ABSTRACT FROM AUTHOR]

Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on the line. The search is completed when both robots arrive at the target point. The target is discovered at the moment when either robot arrives at its position. The robot knowing the placement of the target may communicate it to the other robot. We look for the algorithm with the shortest possible search time (i.e. the worst-case time at which both robots meet at the target) measured as a function of the target distance from the origin (i.e. the time required to travel directly from the starting point to the target at unit velocity). We consider two standard models of communication between the robots, namely wireless communication and communication by meeting. In the case of communication by meeting, a robot learns about the target while sharing the same location with a robot possessing this knowledge. We propose here an optimal search strategy for two robots including the respective lower bound argument, for the full spectrum of their maximal speeds. This extends the main result of Chrobak et al. (in: Italiano, Margaria-Steffen, Pokorný, Quisquater, Wattenhofer (eds) Current trends in theory and practice of computer science, SOFSEM, 2015) referring to the exact complexity of the problem for the case when the speed of the slower robot is at least one third of the faster one. In the wireless communication model, a message sent by one robot is instantly received by the other robot, regardless of their current positions on the line. For this model, we design a strategy which is optimal whenever the faster robot is at most 17+4≈8.123 times faster than the slower one. We also prove that otherwise the wireless communication offers no advantage over communication by meeting. [ABSTRACT FROM AUTHOR]

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 $$\pi _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 $$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 $${\mathcal {P}}$$ intending to lock-in the agent in an Euler tour as quickly as possible and its adversary $${\mathcal {A}}$$ with the counter objective. We consider all cases of who decides the initial cyclic orders and the initial values $$\pi _v$$ . We show, for example, that if $${\mathcal {A}}$$ provides its own port numbering after the initial setup of pointers by $${\mathcal {P}}$$ , the worst-case complexity of the lock-in problem is $${\varTheta }(m\cdot \min \{\log m,D\})$$ . We also investigate the robustness of the rotor-router graph exploration in presence of faults in the pointers $$\pi _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 $$\mathcal {O}(km)$$ steps. [ABSTRACT FROM AUTHOR]

Abstract: We consider the problem of periodic graph exploration in which a mobile entity with constant memory, an agent, has to visit all nodes of an input simple, connected, undirected graph in a periodic manner. Graphs are assumed to be anonymous, that is, nodes are unlabeled. While visiting a node, the agent may distinguish between the edges incident to it; for each node , the endpoints of the edges incident to are uniquely identified by different integer labels called port numbers. We are interested in algorithms for assigning the port numbers together with traversal algorithms for agents using these port numbers to obtain short traversal periods. Periodic graph exploration is unsolvable if the port numbers are set arbitrarily; see Budach (1978) . However, surprisingly small periods can be achieved by carefully assigning the port numbers. Dobrev et al. (2005) described an algorithm for assigning port numbers and an oblivious agent (i.e., an agent with no memory) using it, such that the agent explores any graph with  nodes within the period . When the agent has access to a constant number of memory bits, the optimal length of the period was proved in Gąsieniec et al. (2008)  to be no more than (using a different assignment of the port numbers and a different traversal algorithm). In this paper, we improve both these bounds. More precisely, we show how to achieve a period length of at most for oblivious agents and a period length of at most for agents with constant memory. To obtain our results, we introduce a new, fast graph decomposition technique called a three-layer partition that may also be useful for solving other graph problems in the future. Finally, we present the first non-trivial lower bound, , on the period length for the oblivious case. [Copyright &y& Elsevier]