Home›Mobile robots in the plane›Symmetry breaking and spreading›Uniform deployment on a ring

Uniform deployment on a ring

Robots on a circle must spread out to equal spacing.

Problem statement and measurescollapse

Uniform deployment on a ring: robots on a circle of length \(L\) must reach positions at distance exactly \(d = L/n\) from their neighbours and stop Flocchini et al. 2008. The animation runs their rule for an oriented ring with known \(d\): an activated robot whose clockwise gap (red) exceeds \(d\) moves clockwise along the ring until it is exactly \(d\) behind the next robot; here the asynchronous adversary activates one robot at a time.

\(n\) robots on a ring (a circle of length \(L\)) must reach positions at equal distance \(d=L/n\) from their neighbours (the next robots along the ring in either direction) and stop. Spreading on a segment is the one-dimensional analogue.

Measures: Time, rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known; Colours, colours of the light per robot (0 for oblivious robots).

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Imagine \(n\) guards spread at random along a circular wall who must spread out so that every two neighbours are the same distance apart. In uniform deployment the guards are \(n\) robots at distinct points of a ring, a circle of length \(L\). Consecutive robots along the ring are neighbours, and the gap of a robot is the distance along the ring to its clockwise neighbour. The robots must reach positions where every gap is exactly \(d = L/n\), and then stop. In the basic version robots are oblivious (they forget everything after each move), the scheduler is asynchronous (ASYNC: an adversary, an imagined opponent, decides the activation of each robot, that is, when it looks and moves, and a robot may see others in mid-move), and robots agree on which way is clockwise (an oriented ring).

1AlgorithmClose the gap in front of you, only clockwise Oriented ring, asynchronous, oblivious → Flocchini et al. 2008

Robots know \(d\). Each time a robot is activated:

Look clockwise and measure the distance to the next robot.
If that distance is at most \(d\), do nothing.
If it is more than \(d\), move clockwise until you are exactly \(d\) behind that robot.

Why it works and what it costs. All gaps add up to \(L = nd\), so if some gap is smaller than \(d\), another is larger. Robots only move clockwise, so the robot in front never comes closer; a robot whose gap is at least \(d\) therefore never again has a gap below \(d\), and the number of such robots never decreases. Flocchini et al. 2008 prove that this protocol (Uniform Known) reaches exact deployment in finite time, even with limited visibility \(2d\); when \(d\) is unknown, a "go to the half" rule reaches every gap within any \(\varepsilon\) of \(d\). No running-time bound is recorded in the catalogue.

Why it matters. It shows that a shared sense of direction plus one number (\(d\)) turns an impossible task into a three-line rule.

2ImpossibilityTwo mirror-image teams that always overshoot Oriented ring, asynchronous, oblivious → Flocchini et al. 2008

Without a shared clockwise direction exact deployment is impossible, even with full memory and SSYNC activation (time is divided into rounds; in each round the adversary activates some robots, and each looks and moves once). Take \(n = 4\): black robots at two opposite points, white robots at two opposite points, the white pair rotated by a small angle from the uniform position; the two black robots form one team and the two white robots the other. Black robots think clockwise is one way, white robots think it is the other, so each black robot sees exactly what each white robot sees, in mirror image. The adversary then plays:

If moving only the blacks would not finish the job, move only the blacks (the configuration, the positions of all robots, keeps the same two-team shape).
If moving only the blacks would finish, then by the mirror image moving only the whites would also finish; so move both. Each team closes the same gap, together they overshoot, and again the configuration has the same shape.
Alternate between starting with the blacks and the whites, so every robot moves infinitely often.

Why it holds. Every round leaves the robots in two rotated teams, never equally spaced, so the algorithm never finishes Flocchini et al. 2008. The argument works for every even \(n\) with two interleaved regular \(n/2\)-gons. It is why the catalogued variant assumes an oriented ring.

Why it matters. It is a model example of an adversary that exploits mirror symmetry and the freedom to choose who moves.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound

Setting

Time

Colours

Oriented ring, asynchronous, oblivious standard

On an oriented ring oblivious asynchronous robots deploy exactly if they know \(d\), and within any \(\varepsilon\) if they do not.

unknown \(\text{finite}\) vs \(\text{impossible}\) symmetry

tight \(0\) vs —

Open questions 1

Oriented ring, asynchronous, oblivious

Is knowledge of \(d\) necessary for exact deployment on an oriented ring? Which capabilities allow asynchronous exact deployment on unoriented rings? Flocchini et al. 2008

What the community started looking at

Self-deployment asked under which assumptions robots can spread uniformly around a ring Flocchini et al. 2008 or along a segment Cohen & Peleg 2008: orientation and knowledge of the target distance turned out to be the deciding factors.

All settings

The assumption tree (1 settings, 1 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Colours); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Body › Visibility › Opacity › Faults › Scheduler › Lights (persistent memory) › Agreement on coordinates › Movement › Multiplicity detection › Randomness › Identifiers.

tight near-optimal polynomial gap unknown impossible no variant

No assumptions · 1 branches by body Nothing is assumed on any axis.
- +point+unlimited visibility+transparent+no faults+chirality
  Oriented ring, asynchronous, oblivious standard setting On an oriented ring oblivious asynchronous robots deploy exactly if they know \(d\), and within any \(\varepsilon\) if they do not.

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.