Y. Dieudonné, A. Pelc, V. Villain, How to meet asynchronously at polynomial cost, SIAM Journal on Computing 44 (2015), 844-867.
Y. Dieudonné, A. Pelc, V. Villain, How to meet asynchronously at polynomial cost, SIAM Journal on Computing 44 (2015), 844-867.
Preliminary version appeared in:
Proc. 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC 2013), July 2013, Montreal, Canada, 92-99.
Abstract:
Two mobile agents starting at different nodes of an unknown network have to meet. This task is known in the literature as {\em rendezvous}. Each agent has a different label which is a positive integer known to it, but unknown to the other agent. Agents move in an asynchronous way: the speed of agents may vary and is controlled by an adversary. The cost of a rendezvous algorithm is the total number of edge traversals by both agents until their meeting. The only previous deterministic algorithm solving this problem has cost exponential in the size of the graph and in the larger label. In this paper we present a deterministic rendezvous algorithm with cost {\em polynomial} in the size of the graph and in the {\em length} of the {\em smaller} label. Hence we decrease the cost exponentially in the size of the graph and doubly exponentially in the labels of agents. As an application of our rendezvous algorithm we solve several fundamental problems involving teams of unknown size larger than 1 of labeled agents moving asynchronously in unknown networks. Among them are the following problems: {\tt team size}, in which every agent has to find the total number of agents, {\tt leader election}, in which all agents have to output the label of a single agent, {\tt perfect renaming} in which all agents have to adopt new different labels from the set $\{1,\dots,k\}$, where $k$ is the number of agents, and {\tt gossiping}, in which each agent has initially a piece of information (value) and all agents have to output all the values. Using our rendezvous algorithm we solve all these problems at cost polynomial in the size of the graph and in the smallest length of all labels of participating agents.
A. Miller, A. Pelc, Tradeoffs between cost and information for rendezvous and treasure hunt, Journal of Parallel and Distributed Computing 83 (2015), 159-167.
Preliminary version appeared in:
Proc. 18th International Conference on Principles of Distributed Systems (OPODIS 2014), December 2014, Cortina d'Ampezzo, Italy, LNCS 8878, 263-276.
Abstract:
In rendezvous, two agents traverse network edges in synchronous rounds and have to meet at some node. In treasure hunt, a single agent has to find a stationary target situated at an unknown node of the network. We study tradeoffs between the amount of information ({\em advice}) available {\em a priori} to the agents and the cost (number of edge traversals) of rendezvous and treasure hunt. Our goal is to find the smallest size of advice which enables the agents to solve these tasks at some cost $C$ in a network with $e$ edges. This size turns out to depend on the initial distance $D$ and on the ratio $\frac{e}{C}$, which is the {\em relative cost gain} due to advice. For arbitrary graphs, we give upper and lower bounds of $O(D\log(D\cdot \frac{e}{C}) +\log\log e)$ and $\Omega(D\log \frac{e}{C})$, respectively, on the optimal size of advice. For the class of trees, we give nearly tight upper and lower bounds of $O(D\log \frac{e}{C} + \log\log e)$ and $\Omega (D\log \frac{e}{C})$, respectively.
A. Miller, A. Pelc, Fast rendezvous with advice, Theoretical Computer Science 608 (2015), 190-198.
Preliminary version appeared in:
Proc. 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS 2014), September 2014, Wroclaw, Poland, LNCS 8847, 75-87.
Abstract:
Two mobile agents, starting from different nodes of an $n$-node network at possibly different times, have to meet at the same node. This problem is known as {\em rendezvous}. Agents move in synchronous rounds using a deterministic algorithm. In each round, an agent decides to either remain idle or to move to one of the adjacent nodes. Each agent has a distinct integer label from the set $\{1,\dots,L\}$, which it can use in the execution of the algorithm, but it does not know the label of the other agent. The main efficiency measure of a rendezvous algorithm's performance is its {\em time} , i.e., the number of rounds from the start of the earlier agent until the meeting. If $D$ is the distance between the initial positions of the agents, then $\Omega(D)$ is an obvious lower bound on the time of rendezvous. However, if each agent has no initial knowledge other than its label, time $O(D)$ is usually impossible to achieve. We study the minimum amount of information that has to be available {\em a priori} to the agents to achieve rendezvous in optimal time $\Theta(D)$. Following the standard paradigm of {\em algorithms with advice}, this information is provided to the agents at the start by an oracle knowing the entire instance of the problem, i.e., the network, the starting positions of the agents, their wake-up rounds, and both of their labels. The oracle helps the agents by providing them with the {\em same} binary string called {\em advice}, which can be used by the agents during their navigation. The length of this string is called the {\em size of advice}. Our goal is to find the smallest size of advice which enables the agents to meet in time $\Theta(D)$. We show that this optimal size of advice is $\Theta(D\log(n/D)+\log\log L)$. The upper bound is proved by constructing an advice string of this size, and providing a natural rendezvous algorithm using this advice that works in time $\Theta(D)$ for all networks. The matching lower bound, which is the main contribution of this paper, is proved by exhibiting classes of networks for which it is impossible to achieve rendezvous in time $\Theta(D)$ with smaller advice.
E. Fusco, A. Pelc, Knowledge, level of symmetry and time of leader election, Distributed Computing 28 (2015), 221-232.
Preliminary version appeared in:
Proc. 20th Annual European Symposium on Algorithms (ESA 2012), September 2012, Ljubljana, Slovenia, LNCS 7501, 479-490.
Abstract:
We study the time needed for deterministic leader election in the $\loc$ model, where in every round a node can exchange any messages with its neighbors and perform any local computations. The topology of the network is unknown and nodes are unlabeled, but ports at each node have arbitrary fixed labelings which, together with the topology of the network, can create asymmetries to be exploited in leader election. We consider two versions of the leader election problem: strong LE in which exactly one leader has to be elected, if this is possible, while all nodes must terminate declaring that leader election is impossible otherwise, and weak LE, which differs from strong LE in that no requirement on the behavior of nodes is imposed, if leader election is impossible. We show that the time of leader election depends on three parameters of the network: its diameter $D$, its size $n$, and its {\em level of symmetry} $\lambda$, which, when leader election is feasible, is the smallest depth at which some node has a unique view of the network. It also depends on the knowledge by the nodes, or lack of it, of parameters $D$ and $n$.
Y. Dieudonné, A. Pelc, Deterministic polynomial approach in the plane, Distributed Computing 28 (2015), 111-129.
Preliminary version appeared in:
Proc. 40th International Colloquium on Automata, Languages and Programming (ICALP 2013), July 2013, Riga, Latvia, LNCS 7966, 533-544.
Abstract:
Two mobile agents with range of vision 1 start at arbitrary points in the plane and have to accomplish the task of {\em approach}, which consists in {getting at distance} at most one from each other, i.e., in getting within each other's range of vision. An adversary chooses the initial positions of the agents, their possibly different starting times, and assigns a different positive integer label and a possibly different speed to each of them. Each agent is equipped with a compass showing the cardinal directions, with a measure of length and a clock. Each agent knows its label and speed but not those of the other agent and it does not know the initial position of the other agent relative to its own. Agents do not have any global system of coordinates and they cannot communicate. Our main result is a deterministic algorithm to accomplish the task of approach, working in time polynomial in the unknown initial distance between the agents, in the length of the smaller label and in the inverse of the larger speed. The distance travelled by each agent until approach is polynomial in the first two parameters and does not depend on the third. The problem of approach in the plane reduces to a network problem: that of rendezvous in an infinite grid.
E. Fusco, A. Pelc, Communication complexity of consensus in anonymous message passing systems, Fundamenta Informaticae 137 (2015), 305-322.
Preliminary version appeared in:
Proc. 15th International Conference on Principles of Distributed Systems (OPODIS 2011), December 2011, Toulouse, France, LNCS 7109, 191-206.
Abstract:
We consider the message complexity of achieving consensus in synchronous anonymous message passing systems. Unlabeled processors (nodes) communicate through links of a network. An adversary wakes up some subset of processors at possibly different times and assigns them arbitrary numerical input values. All other processors are dormant and do not have input values. Any message wakes up a dormant processor. The goal of consensus is to have all processors agree on one of the input values. We seek deterministic consensus algorithms using as few messages as possible. As opposed to most of the literature on consensus, the difficulty of our scenario are not faults (we assume that the network is fault-free) but the arbitrary network topology combined with the anonymity of nodes. For $n$-node networks of unknown topology we show a consensus algorithm using $O(n^2)$ messages; this complexity is optimal for this class. We show that if the network topology is known, then the complexity of consensus decreases significantly. Our main contribution is an algorithm that uses $O(n^{3/2}\log ^2n)$ messages on any $n$-node network and we show that some networks require $\Omega(n\log n)$ messages to achieve consensus.