P. Fraigniaud, A. Pelc, Decidability classes for mobile agents computing, Journal of Parallel and Distributed Computing 109 (2017), 117-128.
P. Fraigniaud, A. Pelc, Decidability classes for mobile agents computing, Journal of Parallel and Distributed Computing 109 (2017), 117-128.
Preliminary version appeared in:
Proc. 10th Latin American Theoretical Informatics Symposium (LATIN 2012), April 2012, Arequipa, Peru, LNCS 7256, 362-374.
Abstract:
We establish a classification of decision problems that are to be solved by mobile agents operating in unlabeled graphs, using a deterministic protocol. The classification is with respect to the ability of a team of agents to solve the problem, possibly with the aid of additional information. In particular, our focus is on studying differences between the decidability of a decision problem by agents and its verifiability when a certificate for a positive answer is provided to the agents. We show that the class MAV of mobile agents verifiable} problems is much wider than the class MAD of mobile agents decidable problems. Our main result shows that there exist natural MAV-complete problems: the most difficult problems in this class, to which all problems in MAV are reducible. Our construction of a MAV-complete problem involves two main ingredients in mobile agents computability: the topology of the quotient graph and the number of operating agents. Beyond the class MAV, we show that, for a single agent, three natural oracles yield a strictly increasing chain of relative decidability classes.
C. Glacet, A. Miller, A. Pelc, Time vs. information tradeoffs for leader election in anonymous trees, ACM Transactions on Algorithms 13 (2017), 31:1-31:41.
Preliminary version appeared in:
Proc. 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), January 2016, Arlington, USA, 600-609.
Abstract:
Leader election is one of the fundamental problems in distributed computing. It calls for all nodes of a network to agree on a single node, called the leader. If the nodes of the network have distinct labels, then agreeing on a single node means that all nodes have to output the label of the elected leader. If the nodes of the network are anonymous, the task of leader election is formulated as follows: every node $v$ of the network must output a simple path, which is coded as a sequence of port numbers, such that all these paths end at a common node, the leader. In this paper, we study deterministic leader election in anonymous trees. \\Our aim is to establish tradeoffs between the allocated time $\tau$ and the amount of information that has to be given {\em a priori} to the nodes to enable leader election in time $\tau$ in all trees for which leader election in this time is at all possible. Following the 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 tree. The length of this string is called the {\em size of advice}. For a given time $\tau$ allocated to leader election, we give upper and lower bounds on the minimum size of advice sufficient to perform leader election in time $\tau$. \\For most values of $\tau$, our upper and lower bounds are either tight up to multiplicative constants, or they differ only by a logarithmic factor. Let $T$ be an $n$-node tree of diameter $diam \leq D$. While leader election in time $diam$ can be performed without any advice, for time $diam-1$ we give tight upper and lower bounds of $\Theta (\log D)$. For time $diam-2$ we give tight upper and lower bounds of $\Theta (\log D)$ for even values of $diam$, and tight upper and lower bounds of $\Theta (\log n)$ for odd values of $diam$. Moving to shorter time, in the interval $[\beta \cdot diam, diam -3]$ for constant $\beta >1/2$, we prove an upper bound of $O(\frac{n\log n}{D})$ and a lower bound of $\Omega(\frac{n}{D})$, the latter being valid whenever $diam$ is odd or when the time is at most $diam-4$. Hence, with the exception of the special case when $diam$ is even and time is exactly $diam-3$, our bounds leave only a logarithmic gap in this time interval. Finally, for time $\alpha \cdot diam$ for any constant $\alpha <1/2$ (except for the case of very small diameters), we again give tight upper and lower bounds, this time $\Theta (n)$.
A. Miller, A. Pelc, Deterministic distributed construction of T-dominating sets in time T, Discrete Applied Mathematics 222 (2017), 172-178.
Abstract:
A $k$-dominating set is a set $D$ of nodes of a graph such that, for each node $v$, there exists a node $w \in D$ at distance at most $k$ from $v$. Our aim is the deterministic distributed construction of small $T$-dominating sets in time $T$ in networks modeled as undirected $n$-node graphs and under the $\cal{LOCAL}$ communication model. For any positive integer $T$, if $b$ is the size of a pairwise disjoint collection of balls of radii at least $T$ in a graph, then $b$ is an obvious lower bound on the size of a $T$-dominating set. Our first result shows that, even on rings, it is impossible to construct a $T$-dominating set of size $s$ asymptotically $b$ (i.e., such that $s/b \rightarrow 1$) in time $T$. In the range of time $T \in \Theta (\log^* n)$, the size of a $T$-dominating set turns out to be very sensitive to multiplicative constants in running time. Indeed, it follows from \cite{KP}, that for time $T=\gamma \log^* n$ with large constant $\gamma$, it is possible to construct a $T$-dominating set whose size is a small fraction of $n$. By contrast, we show that, for time $T=\alpha \log^* n $ for small constant $\alpha$, the size of a $T$-dominating set must be a large fraction of $n$. Finally, when $T \in o (\log^* n)$, the above lower bound implies that, for any constant $x<1$, it is impossible to construct a $T$-dominating set of size smaller than $xn$, even on rings. On the positive side, we provide an algorithm that constructs a $T$-dominating set of size $n- \Theta(T)$ on all graphs.
S. Elouasbi, A. Pelc, Deterministic rendezvous with detection using beeps, International Journal of Foundations of Computer Science 28 (2017), 77-97.
Preliminary version appeared in:
Proc. 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS 2015), September 2015, Patras, Greece, LNCS 9536, 85-97.
Abstract:
Two mobile agents, starting at arbitrary, possibly different times from arbitrary nodes of an unknown network, 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. Agents have different labels which are positive integers. Each agent knows its own label, but not the label of the other agent. In traditional formulations of the rendezvous problem, meeting is accomplished when the agents get to the same node in the same round. We want to achieve a more demanding goal, called {\em rendezvous with detection}: agents must become aware that the meeting is accomplished, simultaneously declare this and stop. This awareness depends on how an agent can communicate to the other agent its presence at a node. We use two variations of the arguably weakest model of communication, called the {\em beeping model}, introduced in \cite{CK}. In each round an agent can either listen or beep. In the {\em local beeping model}, an agent hears a beep in a round if it listens in this round and if the other agent is at the same node and beeps. In the {\em global beeping model}, an agent hears a {\em loud} beep in a round if it listens in this round and if the other agent is at the same node and beeps, and it hears a {\em soft} beep in a round if it listens in this round and if the other agent is at some other node and beeps. We first present a deterministic algorithm of rendezvous with detection working, even for the local beeping model, in an arbitrary unknown network in time polynomial in the size of the network and in the length of the smaller label (i.e., in the logarithm of this label). However, in this algorithm, agents spend a lot of energy: the number of moves that an agent must make, is proportional to the time of rendezvous. It is thus natural to ask if {\em bounded-energy agents}, i.e., agents that can make at most $c$ moves, for some constant $c$, can always achieve rendezvous with detection as well. This is impossible for some networks of unbounded size. Hence we rephrase the question: Can bounded-energy agents always achieve rendezvous with detection in bounded-size networks? We prove that the answer to this question is positive, even in the local beeping model but, perhaps surprisingly, this ability comes at a steep price of time: the meeting time of bounded-energy agents is {\em exponentially} larger than that of unrestricted agents. By contrast, we show an algorithm for rendezvous with detection in the global beeping model that works for bounded-energy agents (in bounded-size networks) as fast as for unrestricted agents.