A. Pelc, R. Yadav, Latecomers help to meet: Deterministic anonymous gathering in the plane, Proc. 21st International Conference on Distributed Computing and Networking (ICDCN 2020), January 2020, Kolkata, India, 4:1-4:10.
A. Pelc, R. Yadav, Latecomers help to meet: Deterministic anonymous gathering in the plane, Proc. 21st International Conference on Distributed Computing and Networking (ICDCN 2020), January 2020, Kolkata, India, 4:1-4:10.
Abstract:
A team of anonymous mobile agents represented by points freely moving in the plane have to gather at a single point and stop. Agents start at different points of the plane and at possibly different times chosen by the adversary. They are equipped with compasses, a common unit of distance and clocks. They execute the same deterministic algorithm. When moving, agents travel at the same speed normalized to 1. When agents are at distance at most $\epsilon$, for some positive constant $\epsilon$ unknown to them, they see each other and can exchange all information known to date. Due to the anonymity of the agents and the symmetry of the plane, gathering is impossible, e.g., if agents start simultaneously at distances larger than $\epsilon$. However, if some agents start with a delay with respect to others, gathering may become possible. In which situations such latecomers can enable gathering? How can delays be used to make it possible? To answer these questions we consider initial configurations formalized as sets of pairs $\{(p_1,t_1), (p_2,t_2),\dots , (p_n,t_n)\}$, for $n\geq 2$, where $p_i$ is the starting point of the $i$-th agent and $t_i$ is its starting time. An initial configuration is {\em gatherable} if agents starting at it can be gathered by some algorithm, even dedicated to this particular configuration. Our first result is a characterization of all gatherable initial configurations. It is then natural to ask if there is a universal deterministic algorithm that can gather all gatherable configurations of a given size. It turns out that the answer to this question is negative. Indeed, we show that all gatherable configurations can be partitioned into two sets: {\em bad} configurations and {\em good} configurations. We show that bad gatherable configurations (even of size 2) cannot be gathered by a common gathering algorithm. On the other hand, we prove that there is a universal algorithm that gathers all good configurations of a given size. Then we ask the question of whether the exact knowledge of the number of agents is necessary to gather all good configurations. It turns out that the answer is no, and we prove a necessary and sufficient condition on the knowledge concerning the number of agents that an algorithm gathering all good configurations must have.
S. Bouchard, Y. Dieudonne, A. Pelc, F. Petit, Deterministic treasure hunt in the plane with angular hints, Algorithmica 82 (2020), 3250-3281.
Abstract:
A mobile agent equipped with a compass and a measure of length has to find an inert treasure in the Euclidean plane. Both the agent and the treasure are modeled as points. In the beginning, the agent is at a distance at most $D>0$ from the treasure, but knows neither the distance nor any bound on it. Finding the treasure means getting at distance at most 1 from it. The agent makes a series of moves. Each of them consists in moving straight in a chosen direction at a chosen distance. In the beginning and after each move the agent gets a hint consisting of a positive angle smaller than $2\pi$ whose vertex is at the current position of the agent and within which the treasure is contained. We investigate the problem of how these hints permit the agent to lower the cost of finding the treasure, using a deterministic algorithm, where the cost is the worst-case total length of the agent's trajectory. It is well known that without any hint the optimal (worst case) cost is $\Theta(D^2)$. We show that if all angles given as hints are at most $\pi$, then the cost can be lowered to $O(D)$, which is the optimal complexity. If all angles are at most $\beta$, where $\beta<2\pi$ is a constant unknown to the agent, then the cost is at most $O(D^{2-\epsilon})$, for some $\epsilon>0$. For both these positive results we present deterministic algorithms achieving the above costs. Finally, if angles given as hints can be arbitrary, smaller than $2\pi$, then we show that cost complexity $\Theta(D^2)$ cannot be beaten.
H. Arfaoui, P. Fraigniaud, D. Ilcinkas, F. Mathieu, A. Pelc, Deciding and verifying network properties locally with few output bits, Distributed Computing 33 (2020), 169-187.
Abstract:
Given a boolean predicate on labeled networks (e.g., the network is acyclic, or the network is properly colored, etc.), deciding in a distributed manner whether a given labeled network satisfies that predicate typically consists, in the standard setting, of every node inspecting its close neighborhood, and outputting a boolean verdict, such that the network satisfies the predicate if and only if all nodes output true. In this paper, we investigate a more general notion of distributed decision in which every node is allowed to output a constant number $b>1$ of bits, which are gathered by a central authority emitting a global boolean verdict based on these outputs, such that the network satisfies the predicate if and only if this global verdict equals true. We analyze the power and limitations of this extended notion of distributed decision.
K. Hounkanli, A. Miller, A. Pelc, Global synchronization and consensus using beeps in a fault-prone MAC, Theoretical Computer Science 806 (2020), 567-576.
Abstract:
Global synchronization is an important prerequisite to many distributed tasks. Communication between processors proceeds in synchronous rounds.
Processors are woken up in possibly different rounds. The clock of each processor starts in its wakeup round showing local round 0, and ticks once per round, incrementing the value of the local clock by one.
The global round 0, unknown to processors, is the wakeup round of the earliest processor. Global synchronization (or establishing a global clock) means that each processor chooses a local clock round such that their chosen rounds all correspond to the same global round $t$.
We study the task of global synchronization in a Multiple Access Channel (MAC) prone to faults, under a very weak communication model called the {\em beeping model}.
Some processors wake up spontaneously, in possibly different rounds decided by an adversary. In each round, an awake processor can either listen, i.e., stay silent,
or beep, i.e., emit a signal. In each round, a fault can occur in the channel independently with constant probability $0