Observe and remain silent
(Communication-less agent location discovery)

Leszek Gasieniec

U of Liverpool

Abstract:
We study a randomised distributed communication-less coordination mechanism for uniform
anonymous agents located on a circle. The agents perform their actions in synchronised rounds.
At the beginning of each round an agent chooses the direction of its movement from clockwise
and anticlockwise, as well as its speed 0 \leq v \leq 1 during this round. We assume that the agents
are not allowed to overpass. I.e., when an agent collides with another it instantly starts moving
with the same speed towards the opposite direction. The agents cannot leave marks on the ring,
they have zero visibility and they cannot exchange messages. However, on the conclusion of each
round each agent has access to a detailed trajectory of its movement during this round. This
information can be processed and stored by the agent for further analysis.
We assume that n mobile agents are initially located on a circle with circumference one at
arbitrary but distinct positions unknown to other agents. The main location discovery task to be
performed by each agent is to determine the initial position of every other agent and eventually
to stop at its initial position, or proceed to another task, in a fully synchronised manner.
Our main result constitutes of a fully distributed randomised algorithm that solves the loc-
ation discovery problem with high probability in O(n \log^2 n) rounds. We also show how this
mechanism can be adopted to distribute the agents evenly, at equidistant positions, and how to
coordinate their joint effort in patrolling the circle. Note that our result also holds if initially the
agents do not know the value of n and they have no coherent sense of direction.

(joint work with: T. Friedetzky, T. Gorry, and R. Martin)