S. Bouchard, Y. Dieudonné, A. Pelc, F. Petit, Deterministic rendezvous at a node of agents with arbitrary velocities, Information Processing Letters 133 (2018), 39-43.
S. Bouchard, Y. Dieudonné, A. Pelc, F. Petit, Deterministic rendezvous at a node of agents with arbitrary velocities, Information Processing Letters 133 (2018), 39-43.
Abstract:
We consider the task of rendezvous in networks modeled as undirected graphs. Two mobile agents with different labels, starting at different nodes of an anonymous graph, have to meet. This task has been considered in the literature under two alternative scenarios: weak and strong. Under the weak scenario, agents may meet either at a node or inside an edge. Under the strong scenario, they have to meet at a node, and they do not even notice meetings inside an edge. Rendezvous algorithms under the strong scenario are known for synchronous agents. For asynchronous agents, rendezvous under the strong scenario is impossible even in the two-node graph, and hence only algorithms under the weak scenario were constructed. In this paper we show that rendezvous under the strong scenario is possible for agents with asynchrony restricted in the following way: agents have the same measure of time but the adversary can impose, for each agent and each edge, the speed of traversing this edge by this agent. The speeds may be different for different edges and different agents but all traversals of a given edge by a given agent have to be at the same imposed speed. We construct a deterministic rendezvous algorithm for such agents, working in time polynomial in the size of the graph, in the length of the smaller label, and in the largest edge traversal time.
A. Pelc, Use of information, memory and randomization in asynchronous gathering, Journal of Computer and System Sciences 94 (2018), 193-205.
Abstract:
We investigate initial information, unbounded memory and randomization in gathering mobile agents on a grid. We construct a state machine, such that it is possible to gather, with probability 1, all configurations of its copies. This machine has initial input, unbounded memory, and is randomized. We show that no machine having any two of these capabilities but not the third, can be used to gather, with high probability, all configurations. We construct deterministic Turing Machines that are used to gather all connected configurations, and we construct deterministic finite automata that are used to gather all contractible connected configurations.
S. Elouasbi, A. Pelc, Deterministic meeting of sniffing agents in the plane, Fundamenta Informaticae 160 (2018), 281-301.
Preliminary version appeared in:
Proc. 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO 2016), July 2016, Helsinki, Finland, 212-227.
Abstract:
Two mobile agents, starting at arbitrary, possibly different times from arbitrary locations in the plane, have to meet. Agents are modeled as discs of diameter 1, and meeting occurs when these discs touch. Agents have different labels which are positive integers. Each agent knows its own label, but not the label of the other agent. Agents are equipped with compasses and have synchronized clocks. They make a series of moves. Each move specifies the direction and the duration of moving. This includes a $null$ move which consists in staying inert for some time, or forever. In a non-null move agents travel at the same constant speed, normalized to 1. We assume that agents have sensors enabling them to estimate the distance from the other agent (defined as the distance between centers of discs), but not the direction towards it. We consider two models of estimation. In both models an agent reads its sensor at the moment of its appearance in the plane and then at the end of each move. This reading (together with the previous ones) determines the decision concerning the next move. In both models the reading of the sensor tells the agent if the other agent is already present. Moreover, in the {\em monotone model}, each agent can find out, for any two readings in moments $t_1$ and $t_2$, whether the distance from the other agent at time $t_1$ was smaller, equal or larger than at time $t_2$. In the weaker {\em binary model}, each agent can find out, at any reading, whether it is at distance less than $\rho$ or at distance at least $\rho$ from the other agent, for some real $\rho>1$ unknown to them. Such distance estimation mechanism can be implemented, e.g., using chemical sensors. Each agent emits some chemical substance (scent), and the sensor of the other agent detects it, i.e., {\em sniffs}. The intensity of the scent decreases with the distance. In the monotone model it is assumed that the sensor is ideally accurate and can measure any change of intensity. In the binary model it is only assumed that the sensor can detect the scent below some distance (without being able to measure intensity) above which the scent is too weak to be detected. We show the impact of the two ways of sensing on the cost of meeting, defined as the total distance travelled by both agents until the meeting. For the monotone model we show an algorithm achieving meeting at cost $O(D)$, where $D$ is the initial distance between the agents. This complexity is optimal. For the binary model we show that, if agents start at distance smaller than $\rho$ (i.e., when they sense each other initially) then meeting can be guaranteed at cost $O(\rho\log \lambda)$, where $\lambda$ is the larger label, and that this cost cannot be improved in general. Finally we observe that, if agents start at distance $\alpha\rho$, for some constant $\alpha >1$ in the binary model, then sniffing does not help, i.e., the worst-case optimal meeting cost is of the same order of magnitude as without any sniffing ability.
A. Pelc, Deterministic gathering with crash faults, Networks 72 (2018), 182-199.
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 and terminate. This problem is known as {\em gathering}. We study deterministic gathering algorithms under the assumption that agents are subject to {\em crash faults} which can occur at any time. Two fault scenarios are considered. A {\em motion fault} immobilizes the agent at a node or inside an edge but leaves intact its memory at the time when the fault occurred. A more severe {\em total fault} immobilizes the agent as well, but also erases its entire memory. Of course, we cannot require faulty agents to gather. Thus the gathering problem for fault prone agents calls for all fault-free agents to gather at a single node, and terminate. When agents move completely asynchronously, gathering with crash faults of any type is impossible. Hence we consider a restricted version of asynchrony, where each agent is assigned by the adversary a fixed speed, possibly different for each agent. Agents have clocks ticking at the same rate. Each agent can wait for a time of its choice at any node, or decide to traverse an edge but then it moves at constant speed assigned to it. Moreover, agents have different labels. Each agent knows its label and speed but not those of other agents. We construct a gathering algorithm working for any team of at least two agents in the scenario of motion faults, and a gathering algorithm working in the presence of total faults, provided that at least two agents are fault free all the time. If only one agent is fault free, the task of gathering with total faults is sometimes impossible. Both our algorithms work in time polynomial in the size of the graph, in the logarithm of the largest label, in the inverse of the smallest speed, and in the ratio between the largest and the smallest speed.
A. Pelc, Reaching a target in the plane with no information, Information Processing Letters 140 (2018), 13-17.
Abstract:
A mobile agent has to reach a target in the Euclidean plane. Both the agent and the target are modeled as points. At the beginning, the agent is at distance at most $D>0$ from the target. Reaching the target means that the agent gets at a {\em sensing distance} at most $r>0$ from it. The agent has a measure of length and a compass. We consider two scenarios: in the {\em static} scenario the target is inert, and in the {\em dynamic} scenario it may move arbitrarily at any (possibly varying) speed bounded by $v$. The agent has no information about the parameters of the problem, in particular it does not know $D$, $r$ or $v$. The goal is to reach the target at lowest possible cost, measured by the total length of the trajectory of the agent. Our main result is establishing the minimum cost (up to multiplicative constants) of reaching the target under both scenarios, and providing the optimal algorithm for the agent. For the static scenario the minimum cost is $\Theta((\log D + \log \frac{1}{r}) D^2/r)$, and for the dynamic scenario it is $\Theta((\log M + \log \frac{1}{r}) M^2/r)$, where $M=\max(D,v)$. Under the latter scenario, the speed of the agent in our algorithm grows exponentially with time, and we prove that for an agent whose speed grows only polynomially with time, this cost is impossible to achieve.
B. Gorain, A. Pelc, Deterministic graph exploration with advice, ACM Transactions on Algorithms 8 (2018), 8:1-8:27.
Preliminary version appeared in:
Proc. 44th International Colloquium on Automata, Languages and Programming (ICALP 2017), July 2017, Warsaw, Poland, 132:1-132:14.
Abstract:
We consider the fundamental task of graph exploration. An $n$-node graph has unlabeled nodes, and all ports at any node of degree $d$ are arbitrarily numbered $0,\dots, d-1$. A mobile agent, initially situated at some starting node $v$, has to visit all nodes and stop. The {\em time} of the exploration is the number of edge traversals. We consider the problem of how much knowledge the agent has to have a priori, in order to explore the graph in a given time, using a deterministic algorithm. Following the paradigm of {\em algorithms with advice}, this a priori information (advice) is provided to the agent by an {\em oracle}, in the form of a binary string, whose length is called the {\em size of advice}. We consider two types of oracles. The {\em instance oracle} knows the entire instance of the exploration problem, i.e., the port-numbered map of the graph and the starting node of the agent in this map. The {\em map oracle} knows the port-numbered map of the graph but does not know the starting node of the agent. What is the minimum size of advice that must be given to the agent by each of these oracles, so that the agent explores the graph in a given time?
We first determine the minimum size of advice to achieve exploration in polynomial time. We prove that some advice of size $\log\log\log n -c$, for any constant $c$, is sufficient for polynomial exploration, and that no advice of size $\log\log\log n -\phi(n)$, where $\phi$ is any function diverging to infinity, can help to do this. These results hold both for the instance and for the map oracles.
On the other side of the spectrum, when advice is large, there are two natural time thresholds: $\Theta(n^2)$ for a map oracle, and $\Theta(n)$ for an instance oracle. This is because, in both cases, these time benchmarks can be achieved with sufficiently large advice (advice of size $O(n\log n)$ suffices). We show that, with a map oracle, time $\Theta(n^2)$ cannot be improved in general, regardless of the size of advice. What is then the smallest advice to achieve time $\Theta(n^2)$ with a map oracle? We show that this smallest size of advice is larger than $n^\delta$, for any $\delta <1/3$.
For large advice, the situation changes significantly when we allow an instance oracle instead of a map oracle. In this case, advice of size $O(n\log n)$ is enough to achieve time $O(n)$. Is such a large advice needed to achieve linear time? We answer this question affirmatively. Indeed, we show more: with any advice of size $o(n\log n)$, the time of exploration must be at least $n^\epsilon$, for any $\epsilon <2$, and with any advice of size $O(n)$, the time must be $\Omega(n^2)$.
We finally look at Hamiltonian graphs, as for them it is possible to achieve the absolutely optimal exploration time $n-1$, when sufficiently large advice (of size $O(n\log n)$) is given by an instance oracle. We show that a map oracle cannot achieve this: regardless of the size of advice, the time of exploration must be $\Omega(n^2)$, for some Hamiltonian graphs. On the other hand, even for the instance oracle, with advice of size $o(n\log n)$, optimal time $n-1$ cannot be achieved: indeed, we show that the time of exploration with such advice must sometimes exceed the optimal time $n-1$ by a summand $n^\epsilon$, for any $\epsilon <1$.
B. Gorain, A. Pelc, Finding the size of a radio network with short labels, Proc. 19th International Conference on Distributed Computing and Networking (ICDCN 2018), January 2018, Varanasi, India, 10:1-10:10.
Abstract:
The number of nodes of a network, called its {\em size}, is one of the most important network parameters. Knowing the size (or a good upper bound on it) is a prerequisite of many distributed network algorithms, ranging from broadcasting and gossiping, through leader election, to rendezvous and exploration. A radio network is a collection of stations, called nodes, with wireless transmission and receiving capabilities. It is modeled as a simple connected undirected graph whose nodes communicate in \\synchronous rounds. In each round, a node can either transmit a message to all its neighbors, or stay silent and listen. At the receiving end, a node $v$ hears a message from a neighbor $w$ in a given round, if $v$ listens in this round, and if $w$ is its only neighbor that transmits in this round. If $v$ listens in a round, and two or more neighbors of $v$ transmit in this round, a {\em collision} occurs at $v$. If $v$ transmits in a round, it does not hear anything in this round. Two scenarios are considered in the literature: if listening nodes can distinguish collision from silence (the latter occurs when no neighbor transmits), we say that the network has the {\em collision detection} capability, otherwise there is no collision detection.
We consider the task of {\em size discovery}: finding the size of an unknown radio network with collision detection. All nodes have to output the size of the network, using a deterministic algorithm. Nodes have labels which are (not necessarily distinct) binary \\strings. The length of a labeling scheme is the largest length of a label.
We concentrate on the following problem: What is the shortest labeling scheme that permits size discovery in all radio networks of maximum degree $\Delta$?
Our main result states that the minimum length of such a labeling scheme is $\Theta(\log\log \Delta)$. The upper bound is proven by designing a size discovery algorithm using a labeling scheme of length $O(\log\log \Delta)$, for all networks of maximum degree $\Delta$. The matching lower bound is proven by constructing a class of graphs (in fact even of trees) of maximum degree $\Delta$, for which any size discovery algorithm must use a labeling scheme of length at least $\Omega(\log \log\Delta)$ on some graph of this class.
A. Pelc, Explorable families of graphs, Proc. 25th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2018), June 2018, Ma'ale HaHamisha, Israel, 165-177.
Abstract:
Graph exploration is one of the fundamental tasks performed by a mobile agent in a graph. An $n$-node graph has unlabeled nodes, and all ports at any node of degree $d$ are arbitrarily numbered $0,\dots, d-1$. A mobile agent, initially situated at some starting node $v$, has to visit all nodes of the graph and stop. In the absence of any initial knowledge of the graph the task of deterministic exploration is often impossible. On the other hand, for some families of graphs it is possible to design deterministic exploration algorithms working for any graph of the family. We call such families of graphs {\em explorable}. Examples of explorable families are all finite families of graphs, as well as the family of all trees. In this paper we study the problem of which families of graphs are explorable. We characterize all such families, and then ask the question whether there exists a universal deterministic algorithm that, given an explorable family of graphs, explores any graph of this family, without knowing which graph of the family is being explored. The answer to this question turns out to depend on how the explorable family is given to the hypothetical universal algorithm. If the algorithm can get the answer to any yes/no question about the family, then such a universal algorithm can be constructed. If, on the other hand, the algorithm can be only given an algorithmic description of the input explorable family, then such a universal deterministic algorithm does not exist.