Y. Dieudonné, A. Pelc, Deterministic network exploration by anonymous silent agents with local traffic reports, ACM Transactions on Algorithms 11 (2014), article 10.
Y. Dieudonné, A. Pelc, Deterministic network exploration by anonymous silent agents with local traffic reports, ACM Transactions on Algorithms 11 (2014), article 10.
Preliminary version appeared in:
Proc. 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), July 2012, Warwick,UK, LNCS 7392, 500-512.
Abstract:
A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, possibly at different times, have to explore the network: every node must be visited by at least one agent and all agents must eventually stop. Agents are anonymous (identical), execute the same deterministic algorithm and move in synchronous rounds along links of the network. They are silent: they cannot send any messages to other agents or mark visited nodes in any way. In the absence of any additional information, exploration with termination of an arbitrary network in {this model, devoid of any means of communication between agents, is impossible}. Our aim is to solve the exploration problem giving to agents very restricted local traffic reports. Specifically, an agent that is at a node v in a given round, is provided with three bits of information, answering the following questions: Am I alone at v? Did any agent enter v in this round? Did any agent exit v in this round? We show that this small information permits to solve the exploration problem in arbitrary networks. More precisely, we give a deterministic terminating exploration algorithm working in arbitrary networks for all initial configurations that are not perfectly symmetric, i.e., in which there are agents with different views of the network. The algorithm works in time polynomial in the (unknown) size of the network. A deterministic terminating exploration algorithm working for all initial configurations in arbitrary networks does not exist.
Y. Dieudonné, A. Pelc, D. Peleg, Gathering despite mischief, ACM Transactions on Algorithms 11 (2014), article 1.
Preliminary version appeared in:
Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), January 2012, Kyoto, Japan, 527-540.
Abstract:
A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, have to meet at the same node. Agents move in synchronous rounds. Each agent has a different label. Up to f of the agents are Byzantine. We consider two levels of Byzantine behavior. A strongly Byzantine agent can choose an arbitrary port when it moves and it can convey arbitrary information to other agents, while a weakly Byzantine agent can do the same, except changing its label. What is the minimum number of good agents that guarantees deterministic gathering of all of them, with termination? We solve exactly this Byzantine gathering problem in arbitrary networks for weakly Byzantine agents, and give approximate solutions for strongly Byzantine agents, both when the size of the network is known and when it is unknown. It turns out that both the strength versus weakness of Byzantine behavior and the knowledge of network size significantly impact the results. For weakly Byzantine agents we show that any number of good agents permit to solve the problem for networks of known size. If the size is unknown, then this minimum number is f+2. More precisely, we show a deterministic polynomial algorithm that gathers all good agents in an arbitrary network, provided that there are at least f+2 of them. We also provide a matching lower bound: we prove that if the number of good agents is at most f+1, then they are not able to gather deterministically with termination in some networks. For strongly Byzantine agents we give a lower bound of f+1, even when the graph is known: we show that f good agents cannot gather deterministically in the presence of f Byzantine agents even in a ring of known size. On the positive side we give deterministic gathering algorithms for at least 2f+1 good agents when the size of the network is known, and for at least 4f+2 good agents when it is unknown.
J. Czyzowicz, A. Kosowski, A. Pelc, Time vs. space trade-offs for rendezvous in trees, Distributed Computing 27 (2014), 95-109.
Preliminary version appeared in:
Proc. 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2012), June 2012, Pittsburgh, USA, 1-10.
Abstract:
Two identical (anonymous) mobile agents start from arbitrary nodes of an unknown tree and have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. We consider deterministic algorithms for this rendezvous task. The main result of this paper is a tight trade-off between the optimal time of completing rendezvous and the size of memory of the agents. For agents with k memory bits, we show that optimal rendezvous time is Theta(n+n^2/k) in n-node trees. More precisely, if k is at most c\log n, for some constant c, we design agents accomplishing rendezvous in arbitrary trees of unknown size n in time O(n+n^2/k), starting with arbitrary delay. We also show that no pair of agents can accomplish rendezvous in time o(n+n^2/k), even in the class of lines of known length and even with simultaneous start. Finally, we prove that at least logarithmic memory is necessary for rendezvous, even for agents starting simultaneously in a n-node line.
A. Pelc, A. Tiane, Efficient grid exploration with a stationary token, International Journal of Foundations of Computer Science25 (2014), 247-262.
Abstract:
A mobile agent starting at an arbitrary node of an m by k grid, for 1< m < k+1, has to explore the grid by visiting all its nodes and traversing all edges. The cost of an exploration algorithm is the number of edge traversals by the agent. Nodes of the grid are unlabeled and ports at each node v have distinct numbers in {0,...,d-1}, where d=2,3,4, is the degree of v. Port numbering is local, i.e., there is no relation between port numbers at different nodes. When visiting a node the agent sees its degree. It also sees the port number by which it enters a node and can choose the port number by which it leaves a visited node. We are interested in deterministic exploration algorithms working at low cost. We consider the scenario in which the agent is equipped with a stationary token situated at its starting node. The agent sees the token whenever it visits this node. We give an exploration algorithm working at cost O(k^2) for 2 by k grids, and at cost O(m^2k), for m by k grids, when 2< m< k+1$, has to explore the grid by visiting all its nodes and traversing all edges. The cost of an exploration algorithm is the number of edge traversals by the agent. Nodes of the grid are unlabeled and ports at each node v have distinct numbers in {0,...,d-1}, where d=2,3,4, is the degree of v. Port numbering is local, i.e., there is no relation between port numbers at different nodes. When visiting a node the agent sees its degree. It also sees the port number by which it enters a node and can choose the port number by which it leaves a visited node. We are interested in deterministic exploration algorithms working at low cost. We consider the scenario in which the agent is equipped with a stationary token situated at its starting node. The agent sees the token whenever it visits this node. We give an exploration algorithm working at cost O(k^2) for 2 by k grids, and at cost O(m^2k), for m by k grids, when 2< m < k+1.
D. Dereniowski, A. Pelc, Leader election for anonymous asynchronous agents in arbitrary networks, Distributed Computing 27 (2014), 21-38.
Abstract:
We consider the problem of leader election among mobile agents operating in an arbitrary network modeled as an undirected graph. Nodes of the network are unlabeled and all agents are identical. Hence the only way to elect a leader among agents is by exploiting asymmetries in their initial positions in the graph. Agents do not know the graph or their positions in it, hence they must gain this knowledge by navigating in the graph and share it with other agents to accomplish leader election. This can be done using meetings of agents, which is difficult because of their asynchronous nature: an adversary has total control over the speed of agents. When can a leader be elected in this adversarial scenario and how to do it? We give a complete answer to this question by characterizing all initial configurations for which leader election is possible and by constructing an algorithm that accomplishes leader election for all configurations for which this can be done.
Y. Dieudonné, A. Pelc, Price of asynchrony in mobile agents computing, Theoretical Computer Science 524 (2014), 59-67.
Abstract:
Asynchrony is one of the main challenges in distributed computing. Some tasks, such as distributed Byzantine consensus, are impossible in the asynchronous setting, while they can be carried out synchronously. For other tasks, such as rendezvous in arbitrary graphs, the best known synchronous algorithm has cost much lower than the best asynchronous one. Various degrees of asynchrony and comparisons between them in terms of feasibility of distributed tasks have been particularly intensely studied in the context of mobile agents computing. However, somewhat surprisingly, there are no results showing a provable difference of cost between the synchronous and asynchronous versions of a task executed by mobile agents. The aim of this paper is to fill up this gap. We show for the first time that for some natural task executed by mobile agents in a network, the optimal cost of its deterministic solution in the asynchronous setting has higher order of magnitude than that in the synchronous scenario. The task for which we show this difference is well-studied: that of rendezvous of two agents in an infinite oriented grid. More precisely, we consider two agents with distinct integer labels starting at a distance D in the infinite oriented grid. Each agent knows D and its own label but not the label of the other agent and it does not know the position of the other agent relative to its own. Agents do not have any global system of coordinates. They have to meet in a node or inside an edge of the grid, and the cost of a rendezvous algorithm is the number of edge traversals by both agents until the meeting. We show that in the synchronous scenario rendezvous can be performed at cost O(DL), where L is the length of the (binary representation of the) smaller label, while cost Omega(D^2 +DL) is needed for asynchronous completion of rendezvous. Hence, for instances with L=o(D), the optimal cost of asynchronous rendezvous is asymptotically larger than that of synchronous rendezvous.