Abstracts of papers published in 2016


E. Fusco, A. Pelc, R. Petreschi, Topology recognition with advice, Information and Computation 247 (2016), 254-265.

Preliminary version appeared as:

E. Fusco, A. Pelc, R. Petreschi, Use knowledge to learn faster: Topology recognition with advice, Proc. 27th International Symposium on Distributed Computing (DISC 2013), October 2013, Jerusalem, Israel, LNCS 8205, 31-45.

Abstract:

Topology recognition is one of the fundamental distributed tasks in networks. Each node of an anonymous network has to deterministically produce an isomorphic copy of the underlying graph, with all ports correctly marked. This task is usually unfeasible without any a priori information. Such information can be provided to nodes as {\em advice}. An oracle knowing the network can give a (possibly different) string of bits to each node, and all nodes must reconstruct the network using this advice, after a given number of rounds of communication. During each round each node can exchange arbitrary messages with all its neighbors and perform arbitrary local computations. The time of completing topology recognition is the number of rounds it takes, and the size of advice is the maximum length of a string given to nodes. We investigate tradeoffs between the time in which topology recognition is accomplished and the minimum size of advice that has to be given to nodes. We provide upper and lower bounds on the minimum size of advice that is sufficient to perform topology recognition in a given time, in the class of all graphs of size $n$ and diameter $D\le \alpha n$, for any constant $\alpha< 1$. In most cases, our bounds are asymptotically tight.

D. Dereniowski, A. Pelc, Topology recognition and leader election in colored networks, Theoretical Computer Science 621 (2016), 92-102.

Abstract:

Topology recognition and leader election are fundamental tasks in distributed computing in networks. The first of them requires each node to find a labeled isomorphic copy of the network, while the result of the second one consists in a single node adopting the label 1 (leader), with all other nodes adopting the label 0 and learning a path to the leader. We consider both these problems in networks whose nodes are equipped with not necessarily distinct labels called {\em colors}, and ports at each node of degree $d$ are arbitrarily numbered $0,1,\dots, d-1$. Colored networks are generalizations both of labeled networks, in which nodes have distinct labels, and of anonymous networks, in which nodes do not have labels (all nodes have the same color). In colored networks, topology recognition and leader election are not always feasible. Hence we study two more general problems. Consider a colored network and an input $I$ given to its nodes. The aim of the problem $\problemTOP$, for this colored network and for $I$, is to solve topology recognition in this network, if this is possible under input $I$, and to have all nodes answer \impossible otherwise. Likewise, the aim of the problem $\problemLE$ is to solve leader election in this network, if this is possible under input $I$, and to have all nodes answer \impossible otherwise. We show that nodes of a network can solve problems $\problemTOP$ and $\problemLE$, if they are given, as input $I$, an upper bound $k$ on the number of nodes of a given color, called the {\em size} of this color. On the other hand we show that, if the nodes are given an input that does not bound the size of any color, then the answer to $\problemTOP$ and $\problemLE$ must be \impossible, even for the class of rings. Under the assumption that nodes are given an upper bound $k$ on the size of a given color, we study the time of solving problems $\problemTOP$ and $\problemLE$ in the $\cal{LOCAL}$ model in which, during each round, each node can exchange arbitrary messages with all its neighbors and perform arbitrary local computations. We give an algorithm to solve each of these problems in arbitrary networks in time $O(kD+D\log(n/D))$, where $D$ is the diameter of the network and $n$ is its size. We also show that this time is optimal, by exhibiting classes of networks in which every algorithm solving problems $\problemTOP$ or $\problemLE$ must use time $\Omega(kD+D\log(n/D))$.

J. Chalopin, Y. Dieudonné, A. Labourel, A. Pelc, Rendezvous in networks in spite of delay faults, Distributed Computing 29 (2016), 187-205.

Preliminary version appeared in:

Proc. 41st International Colloquium on Automata, Languages and Programming (ICALP 2014), July 2014, Copenhagen, Denmark, LNCS 8573, 411-422.

Abstract:

Two mobile agents, starting from different nodes of an unknown network, have to {meet at a node}. Agents move in synchronous rounds using a deterministic algorithm. Each agent has a different label, which it can use in the execution of the algorithm, but it does not know the label of the other agent. Agents do not know any bound on the size of the network. In each round an agent decides if it remains idle or if it wants to move to one of the adjacent nodes. Agents are subject to {\em delay faults}: if an agent incurs a fault in a given round, it remains in the current node, regardless of its decision. If it planned to move and the fault happened, the agent is aware of it. We consider three scenarios of fault distribution: random (independently in each round and for each agent with constant probability p), unbounded adversarial (the adversary can delay an agent for an arbitrary finite number of consecutive rounds) and bounded adversarial (the adversary can delay an agent for at most $c$ consecutive rounds, where $c$ is unknown to the agents). The quality measure of a rendezvous algorithm is its cost, which is the total number of edge traversals. For random faults, we show an algorithm with cost polynomial in the size $n$ of the network and {\em polylogarithmic} in the larger label $L$, which achieves rendezvous with very high probability in arbitrary networks. By contrast, for unbounded adversarial faults we show that rendezvous is not {possible}, even in the class of rings. Under this scenario we give a rendezvous algorithm with cost $O(n\ell)$, where $\ell$ is the smaller label, working in arbitrary trees, and we show that $\Omega(\ell)$ is the lower bound on rendezvous cost, even for the two-node tree. For bounded adversarial faults, we give a rendezvous algorithm working for arbitrary networks, with cost polynomial in $n$, and {\em logarithmic} in the bound $c$ and in the larger label $L$.

A. Miller, A. Pelc, Time versus cost tradeoffs for deterministic rendezvous in networks, Distributed Computing 29 (2016), 51-64.

Preliminary version appeared in:

Proc. 33rd Annual ACM Symposium on Principles of Distributed Computing (PODC 2014), July 2014, Paris, France, 282-290.

Abstract:

Two mobile agents, starting from different nodes of a network at possibly different times, have to meet at the same node. This problem is known as {\em rendezvous}. Agents move in synchronous rounds. Each agent has a distinct integer label from the set $\{1,\dots,L\}$. Two main efficiency measures of rendezvous are its {\em time} (the number of rounds until the meeting) and its {\em cost} (the total number of edge traversals). We investigate tradeoffs between these two measures. A natural benchmark for both time and cost of rendezvous in a network is the number of edge traversals needed for visiting all nodes of the network, called the exploration time. Hence we express the time and cost of rendezvous as functions of an upper bound $E$ on the time of exploration (where $E$ and a corresponding exploration procedure are known to both agents) and of the size $L$ of the label space. We present two natural rendezvous algorithms. Algorithm {\tt Cheap} has cost $O(E)$ (and, in fact, a version of this algorithm for the model where the agents start simultaneously has cost exactly $E$) and time $O(EL)$. Algorithm {\tt Fast} has both time and cost $O(E\log L)$. Our main contributions are lower bounds showing that, perhaps surprisingly, these two algorithms capture the tradeoffs between time and cost of rendezvous almost tightly. We show that any deterministic rendezvous algorithm of cost asymptotically $E$ (i.e., of cost $E+o(E)$) must have time $\Omega(EL)$. On the other hand, we show that any deterministic rendezvous algorithm with time complexity $O(E\log L)$ must have cost $\Omega (E\log L)$.

Y. Dieudonné, A. Pelc, Anonymous meeting in networks, Algorithmica 74 (2016), 908-946 .

Preliminary version appeared in:

Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), January 2013, New Orleans, USA, 737-747.

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 meet at the same node. Agents are anonymous (identical), execute the same deterministic algorithm and move in synchronous rounds along links of the network. An initial configuration of agents is called {\em gatherable} if there exists a deterministic algorithm (even dedicated to this particular configuration) that achieves meeting of all agents in one node. Which configurations are gatherable and how to gather all of them deterministically by the same algorithm? We give a complete solution of this gathering problem in arbitrary networks. We characterize all gatherable configurations and give two {\em universal} deterministic gathering algorithms, i.e., algorithms that gather all gatherable configurations. The first algorithm works under the assumption that an upper bound $n$ on the size of the network is known. In this case our algorithm guarantees {\em gathering with detection}, i.e., the existence of a round in which, for any gatherable configuration, all agents are at the same node and all declare that gathering is accomplished. If no upper bound on the size of the network is known, we show that a universal algorithm for gathering with detection does not exist. Hence, for this harder scenario, we construct a second universal gathering algorithm, which guarantees that, for any gatherable configuration, all agents eventually get to one node and stop, although they cannot tell if gathering is over. The time of the first algorithm is polynomial in the upper bound $n$ on the size of the network, and the time of the second algorithm is polynomial in the (unknown) size itself.

J. Anaya, J. Chalopin, J. Czyzowicz, A. Labourel, A. Pelc, Y. Vaxès, Convergecast and broadcast by power-aware mobile agents, Algorithmica 74 (2016), 117-155.

Preliminary version appeared in:

Proc. 26th International Symposium on Distributed Computing (DISC 2012), October 2012, Salvador, Brazil, LNCS 7611, 46-60.

Abstract:

A set of identical, mobile agents is deployed in a weighted network. Each agent has a battery -- a power source allowing it to move along network edges. An agent uses its battery proportionally to the distance traveled. We consider two tasks : {\em \convergecast}, in which at the beginning, each agent has some initial piece of information, and information of all agents has to be collected by some agent; and {\em \broadcast} in which information of one specified agent has to be made available to all other agents. In both tasks, the agents exchange the currently possessed information when they meet. The objective of this paper is to investigate what is the minimal value of power, initially available to all agents, so that {\convergecast} or {\broadcast} can be achieved. We study this question in the centralized and the distributed settings. In the centralized setting, there is a central monitor that schedules the moves of all agents. In the distributed setting every agent has to perform an algorithm being unaware of the network. In the centralized setting, we give a linear-time algorithm to compute the optimal battery power and the strategy using it, both for \convergecast and for \broadcast, when agents are on the line. We also show that finding the optimal battery power for \convergecast or for \broadcast is NP-hard for the class of trees. On the other hand, we give a polynomial algorithm that finds a 2-approximation for \convergecast and a 4-approximation for \broadcast, for arbitrary graphs. In the distributed setting, we give a 2-competitive algorithm for {\convergecast} in trees and a 4-competitive algorithm for \broadcast in trees. The competitive ratio of 2 is proved to be the best for the problem of \convergecast, even if we only consider line networks. Indeed, we show that there is no ($2-\epsilon$)-competitive algorithm for \convergecast or for \broadcast in the class of lines, for any $\epsilon>0$.

K. Hounkanli, A. Pelc, Asynchronous broadcasting with bivalent beeps, Proc. 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO 2016), July 2016, Helsinki, Finland, 291-306.

Abstract:

In broadcasting, one node of a network has a message that must be learned by all other nodes. We study deterministic algorithms for this fundamental communication task in a very weak model of wireless communication. The only signals sent by nodes are {\em beeps}. Moreover, they are delivered to neighbors of the beeping node in an asynchronous way: the time between sending and reception is finite but unpredictable. We first observe that under this scenario, no communication is possible, if beeps are all of the same strength. Hence we study broadcasting in the {\em bivalent beeping model}, where every beep can be either {\em soft} or {\em loud}. At the receiving end, if exactly one soft beep is received by a node in a round, it is heard as soft. Any other combination of beeps received in a round is heard as a loud beep. The cost of a broadcasting algorithm is the total number of beeps sent by all nodes. We consider four levels of knowledge that nodes may have about the network: anonymity (no knowledge whatsoever), ad-hoc (all nodes have distinct labels and every node knows only its own label), neighborhood awareness (every node knows its label and labels of all neighbors), and full knowledge (every node knows the entire labeled map of the network and the identity of the source). We first show that in the anonymous case, broadcasting is impossible even for very simple networks. For each of the other three knowledge levels we provide upper and lower bounds on the minimum cost of a broadcasting algorithm. Our results show separations between all these scenarios. Perhaps surprisingly, the jump in broadcasting cost between the ad-hoc and neighborhood awareness levels is much larger than between the neighborhood awareness and full knowledge levels, although in the two former levels knowledge of nodes is local, and in the latter it is global.

A. Miller, A. Pelc, Election vs. selection: How much advice is needed to find the largest node in a graph?, Proc. 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016), July 2016, Asilomar State Beach, USA, 377-386.

Abstract:

Finding the node with the largest label in a labeled network, modeled as an undirected connected graph, is one of the fundamental problems in distributed computing. This is the way in which {\em leader election} is usually solved. We consider two distinct tasks in which the largest-labeled node is found deterministically. In {\em selection}, this node has to output 1 and all other nodes have to output 0. In {\em election}, the other nodes must additionally learn the largest label (everybody has to know who is the elected leader). Our aim is to compare the difficulty of these two seemingly similar tasks executed under stringent running time constraints. The measure of difficulty is the amount of information that nodes of the network must initially possess, in order to solve the given task in an imposed amount of time. Following the standard framework of {\em algorithms with advice}, this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire graph. The length of this string is called the {\em size of advice}. The paradigm of algorithms with advice has a far-reaching importance in the realm of network algorithms. Lower bounds on the size of advice give us impossibility results based strictly on the \emph{amount} of initial knowledge outlined in a model's description. This more general approach should be contrasted with traditional results that focus on specific \emph{kinds} of information available to nodes, such as the size, diameter, or maximum node degree. Consider the class of $n$-node graphs with any diameter $diam \leq D$, for some integer $D$. If time is larger than $diam$, then both tasks can be solved without advice. For the task of {\em election}, we show that if time is smaller than $diam$, then the optimal size of advice is $\Theta(\log n)$, and if time is exactly $diam$, then the optimal size of advice is $\Theta(\log D)$. For the task of {\em selection}, the situation changes dramatically, even within the class of rings. Indeed, for the class of rings, we show that, if time is $O(diam^{\epsilon})$, for any $\epsilon <1$, then the optimal size of advice is $\Theta(\log D)$, and, if time is $\Theta(diam)$ (and at most $diam$) then this optimal size is $\Theta(\log \log D)$. Thus there is an {\em exponential} increase of difficulty (measured by the size of advice) between selection in time $O(diam^{\epsilon})$, for any $\epsilon <1$, and selection in time $\Theta(diam)$. As for the comparison between election and selection, our results show that, perhaps surprisingly, while for small time, the difficulty of these two tasks on rings is similar, for time $\Theta(diam)$ the difficulty of election (measured by the size of advice) is exponentially larger than that of selection.