A. Pelc, Deterministic rendezvous in networks: A comprehensive survey, Networks 59 (2012), 331-347.
A. Pelc, Deterministic rendezvous in networks: A comprehensive survey, Networks 59 (2012), 331-347.
Preliminary version appeared as:
A. Pelc, DISC 2011 Invited Lecture: Deterministic rendezvous in networks: Survey of models and results, Proc. 25th International Symposium on Distributed Computing (DISC 2011), September 2011, Rome, Italy, LNCS 6950, 1-15.
Abstract:
Two or more mobile entities, called agents or robots, starting at distinct initial positions, have to meet. This task is known in the literature as rendezvousi>. Among many alternative assumptions that have been used to study the rendezvous problem, two most significantly influence the methodology appropriate for its solution. The first of these assumptions concerns the environment in which the mobile entities navigate: it can be either a terrain in the plane, or a network modeled as an undirected graph. The second assumption concerns the way in which the entities move: it can be either deterministic or randomized. In this paper we survey results on deterministic rendezvous in networks.
J. Czyzowicz, A. Labourel, A. Pelc, How to meet asynchronously (almost) everywhere, ACM Transactions on Algorithms 8 (2012), article 37.
Preliminary version appeared in:
Proc. 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), January 2010, Austin, Texas, U.S.A., 22-30.
Abstract:
Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane. Agents are modeled as points, and the route of each of them only depends on its label and on the unknown environment. The actual walk of each agent also depends on an asynchronous adversary that may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent is continuous, does not leave its route and covers all of it. Meeting in a graph means that both agents must be at the same time in some node or in some point inside an edge of the graph, while meeting in a terrain means that both agents must be at the same time in some point of the terrain. Does there exist a deterministic algorithm that allows any two agents to meet in any unknown environment in spite of this very powerfull adversary? We give deterministic rendezvous algorithms for agents starting at arbitrary nodes of any anonymous connected graph (finite or infinite) and for agents starting at any interior points with rational coordinates in any closed region of the plane with path-connected interior. In the geometric scenario agents may have different compasses and different units of length. While our algorithms work in a very general setting - agents can, indeed, meet almost everywhere - we show that none of the above few limitations imposed on the environment can be removed. On the other hand, our algorithm also guarantees the following approximate rendezvous for agents starting at arbitrary interior points of a terrain as above: agents will eventually get at an arbitrarily small positive distance from each other.
J. Czyzowicz, A. Kosowski, A. Pelc, How to meet when you forget: Log-space rendezvous in arbitrary graphs, Distributed Computing 25 (2012), 165-178.
Preliminary version appeared in:
Proc. 29th Annual ACM Symposium on Principles of Distributed Computing (PODC 2010), July 2010, Zurich, Switzerland, 450-459.
Abstract:
Two identical (anonymous) mobile agents start from arbitrary nodes in an a priori unknown graph and move synchronously from node to node with the goal of meeting. This rendezvous problem has been thoroughly studied, both for anonymous and for labeled agents, along with another basic task, that of exploring graphs by mobile agents. Intuitively, the rendezvous problem is more difficult than exploration, as it reduces to the latter, if one of the agents is inert. A well-known recent result on exploration, due to Reingold, states that deterministic exploration of arbitrary graphs can be performed in log-space, i.e., using an agent equipped with O(log n) bits of memory, where n is the size of the graph. In this paper we study the size of memory of mobile agents that permits us to solve the rendezvous problem deterministically. Our main result establishes the minimum size of the memory of anonymous agents that guarantees deterministic rendezvous when it is feasible. We show that this mini- mum size is Theta(log n), where n is the size of the graph, regardless of the delay between the starting times of the agents. More precisely, we construct identical agents equipped with Theta(log n) memory bits that solve the rendezvous problem in all graphs with at most n nodes, if they start with any delay, and we prove a matching lower bound Omega(log n) on the number of memory bits needed to accomplish rendezvous, even for simultaneous start. In fact, this lower bound is achieved already on the class of rings. This shows a significant contrast between rendezvous and exploration: e.g., while exploration of rings (without stopping) can be done using constant memory, rendezvous, even with simultaneous start, requires logarithmic memory. As a by-product of our techniques introduced to obtain log-space rendezvous we get the first polynomial time algorithm to find a quotient graph of a given unlabeled graph.
D. Dereniowski, A. Pelc, Drawing maps with advice, Journal of Parallel and Distributed Computing 72 (2012), 132-143.
Preliminary version appeared in:
Proc. 24th International Symposium on Distributed Computing (DISC 2010), September 2010, Boston, U.S.A., LNCS 6343, 328-342.
Abstract:
We study the problem of the amount of information required to draw a complete or a partial map of a graph with unlabeled nodes and arbitrarily labeled ports. A mobile agent, starting at any node of an unknown connected graph and walking in it, has to accomplish one of the following tasks: draw a complete map of the graph, i.e., find an isomorphic copy of it including port numbering, or draw a partial map, i.e., a spanning tree, again with port numbering. The agent executes a deterministic algorithm and cannot mark visited nodes in any way. None of these map drawing tasks is feasible without any additional information, unless the graph is a tree. Hence we investigate the minimum number of bits of information (minimum size of advice) that has to be given to the agent to complete these tasks. It turns out that this minimum size of advice depends on the number n of nodes or the number m of edges of the graph, and on a crucial parameter \mu, called the multiplicity of the graph, which measures the number of nodes that have an identical view of the graph. We give bounds on the minimum size of advice for both above tasks. For \mu=1 our bounds are asymptotically tight for both tasks and show that the minimum size of advice is very small. For \mu>1 the minimum size of advice increases abruptly. In this case our bounds are asymptotically tight for topology recognition and asymptotically almost tight for spanning tree construction.
Y. Dieudonné, A. Pelc, Deterministic network exploration by a single agent with Byzantine tokens, Information Processing Letters 112 (2012), 467-470.
Abstract:
A mobile agent has to explore an unknown network with unlabeled nodes: it must visit all nodes by walking along the links of the network, and eventually stop. If no upper bound on the size of the network is known and nodes of the network cannot be marked, then this exploration task cannot be accomplished for arbitrary networks by a deterministic terminating algorithm. On the other hand, it is feasible, if there is one unmovable token at the starting node of the agent. We investigate the exploration problem in arbitrary networks in the presence of identical unmovable tokens, some of which are Byzantine. A Byzantine token can be visible or invisible to the agent whenever the latter visits the node where the token is located, and visibility is decided by the adversary at each visit of the agent. If no upper bound on the number of tokens is known to the agent, deterministic exploration of all networks is impossible, even if all tokens are fault free. It is also impossible if all tokens are Byzantine, even if their number is known. Our main result is a deterministic exploration algorithm with cost polynomial in the (unknown) size of the network, which works in arbitrary networks, provided that the agent knows some upper bound on the total number of tokens, and that at least one token is fault free.
E. Fusco, A. Pelc, Distributed tree comparison with nodes of limited memory, Networks 60 (2012), 235-244.
Preliminary version appeared in:
Proc. 17th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2010), June 2010, Sirince, Turkey, LNCS 6058, 142-156.
Abstract:
We consider the task of comparing two rooted trees with port labelings. Roots of the trees are joined by an edge and the comparison has to be carried out distributedly, by exchanging messages among nodes. If the two trees are isomorphic, all nodes must finish in a state YES, otherwise they have to finish in a state NO and break symmetry, nodes of one tree getting label 0 and of the other - label 1. Nodes are modeled as identical automata, and our goal is to establish trade-offs between the memory size of such an automaton and the efficiency of distributed tree comparison, measured either by the time or by the number of messages used for communication between nodes. We consider both the synchronous and the asynchronous communication and establish exact trade-offs in both scenarios. For the synchronous scenario we are concerned with memory vs. time trade-offs. We show that if the automaton has x bits of memory, where x \geq c log n, for a small constant c, then the optimal time to accomplish the comparison task in the class of trees of size at most n and of height at most h>1 is Theta (max(h,n/x)). For the asynchronous scenario we study memory vs. number of messages trade-offs. We show that if the automaton has x bits of memory, where n \geq x \geq c log Delta, then the optimal number of messages to accomplish the comparison task in the class of trees of size at most n and of maximum degree at most Delta is Theta (n^2/x).
J. Czyzowicz, L. Gasieniec, A. Pelc, Choosing the best among peers, Theoretical Computer Science 440-441 (2012), 52-59.
Abstract:
A group of n peers, e.g., computer scientists, has to choose the best, i.e., the most competent among them. Each member of the group may vote for one other member, or abstain. Self-voting is not allowed. A voting graph is a directed graph in which an arc (u,v) means that u votes for v. While opinions may be subjective, resulting in various voting graphs, it is natural to assume that more competent peers are also, in general, more competent in evaluating competence of others. We capture this by proposing a voting system in which each member is assigned a positive integer value satisfying the following strict support monotonicity property: the value of x is larger than the value of y if and only if the sum of values of members voting for x is larger than the sum of values of members voting for y. Then we choose the member with the highest value, or if there are several such members, another election mechanism, e.g., using randomness, chooses one of them. We show that for every voting graph there is a value function satisfying the strict support monotonicity property and that such a function can be computed in linear time. However, it turns out that this method of choosing the best among peers is vulnerable to vote manipulation: even one voter of very low value may change his/her vote so as to get the highest value. This is due to the possibility of loops (directed cycles) in the voting graph. Hence we slightly modify voting graphs by erasing all arcs that belong to some cycle. This modification results in a pruned voting graph which is always a rooted forest. We show that for all pruned voting graphs there are value functions giving a guarantee against manipulation. More precisely, we show a value function guaranteeing that no coalition of k members all of whose values are lower than those of (1-1/(k+1))n other members can manipulate their votes so that one of them gets the largest value. In particular, no single member from the lower half of the group is able to manipulate his/her vote to become elected. We also show that no better guarantee can be given for any value function satisfying the strict support monotonicity property.
J. Czyzowicz, A. Pelc, M. Roy, Tree exploration by a swarm of mobile agents, Proc. 16th International Conference on Principles of Distributed Systems (OPODIS 2012), December 2012, Rome, Italy, LNCS 7702, 121-134.
Abstract:
A swarm of mobile agents starting at the root of a tree has to explore it: every node of the tree has to be visited by at least one agent. In every round, each agent can remain idle or move to an adjacent node. In any round all agents have to be at distance at most d, where d is a parameter called the range of the swarm. The goal is to explore the tree as fast as possible. If the topology of the tree is known to the agents, we establish optimal exploration time for any range d and give an optimal exploration algorithm. The formula for the optimal exploration time of a tree by a swarm of agents depends on the range of the swarm and on the characteristics of the tree. If the tree is unknown, the quality of an exploration algorithm A is measured by comparing its time to that of the optimal algorithm having full knowledge of the tree. The ratio between these times, maximized over all starting nodes and over all trees, is called the overhead of algorithm A. Overhead 2 is achieved when the swarm executes a DFS, remaining together all the time. We show that this overhead cannot be improved, for any range d.
S. Elouasbi, A. Pelc, Time of anonymous rendezvous in trees: Determinism vs. randomization, Proc. 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012), June 2012, Reykjavik, Iceland, LNCS 7355, 291-302.
Abstract:
Two identical (anonymous) mobile agents start from arbitrary nodes of an unknown tree and move along its edges with the goal of meeting 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 study optimal time of completing this rendezvous task. For deterministic rendezvous we seek algorithms that achieve rendezvous whenever possible, while for randomized rendezvous we seek almost safe algorithms, which achieve rendezvous with probability at least 1-1/n in n-node trees, for sufficiently large n. We construct a deterministic algorithm that achieves rendezvous in time O(n) in n-node trees, whenever rendezvous is feasible, and we show that this time cannot be improved in general, even when agents start at distance 1 in bounded degree trees. We also show an almost safe algorithm that achieves rendezvous in time O(n) for arbitrary starting positions in any n-node tree. We then analyze when randomization can help to speed up rendezvous. For n-node trees of known constant maximum degree and for a known constant upper bound on the initial distance between the agents, we show an almost safe algorithm achieving rendezvous in time O(\log n). By contrast, we show that for some trees, every almost safe algorithm must use time \Omega(n), even for initial distance 1. This shows an exponential gap between randomized rendezvous time in trees of bounded degree and in arbitrary trees. Such a gap does not occur for deterministic rendezvous. All our upper bounds hold when agents start with an arbitrary delay, controlled by the adversary, and all our lower bounds hold even when agents start simultaneously.