Uniform circle formation
Robots must form a regular \(n\)-gon: a circle with equal spacing.
Problem statement and measuresexpand
\(n\) robots start at distinct points and must reach the vertices of a regular \(n\)-gon (in any position and size) and stay there. Time is in epochs (ASYNC: intervals in which every robot completes at least one full Look–Compute–Move cycle) or rounds; colours count light colours in the luminous model.
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).
Opaque robots with lights, ASYNC
verifiedWith lights, opaque robots form a uniform circle in \(O(1)\) epochs with \(O(1)\) colours, which is optimal in both.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Body: point
- Each robot is a point of the plane: several robots may share a point (multiplicity), and a robot hides only what lies exactly behind it on a line of sight.
- Visibility: unlimited visibility
- A robot sees all robots (subject to opacity).
- Opacity: opaque
- Robots are points that obstruct sight: \(r\) sees \(s\) iff no third robot lies on the open segment \(\overline{rs}\).
- Faults: no faults
- All robots follow the algorithm forever.
- Scheduler: ASYNC
- ASYNC: each robot's Look, Compute and Move phases take finite but unbounded, adversarially chosen time; a robot may look while others move, and compute on an outdated snapshot. Time is counted in epochs: an epoch is an interval of time in which every robot completes at least one full Look–Compute–Move cycle; it need not be the shortest such interval. The execution is divided into consecutive epochs, and a bound of \(X\) epochs holds for every such division. In FSYNC and SSYNC time is counted in rounds. Called Corda by Prencipe Prencipe 2007. Intermediate variants restrict interleavings: LC-atomic (no Look by another robot between a robot's Look and its Compute), Move-atomic (no Look during another robot's Move) and CM-atomic Flocchini et al. 2023.
- Lights (persistent memory): lights (LUMI)
- LUMI: each robot has a light with \(c\) colours, set at the end of Compute, visible to all robots including itself; it is both memory and communication. Also called luminous robots, or a full light.
- Agreement on coordinates: disoriented
- Each robot \(r\) observes in its own coordinate system, obtained from the global one by an unknown similarity (translation, rotation, uniform scaling, and possibly reflection); systems may differ between robots and, in some models, between cycles. Papers that call robots disoriented do not always mean this: Défago and Souissi use the word while assuming chirality Défago & Souissi 2008. Some papers also let the adversary change a robot's rotation, reflection and unit at every Look (variable disorientation) Flocchini et al. 2023 Masuzawa et al. 2026.
- Movement: rigid
- Every Move phase ends at the computed destination.
- Multiplicity detection: no multiplicity detection
- A snapshot is a set of points: a point occupied by several robots looks like a single robot.
- Randomness: deterministic
- The destination computed in a cycle is a function of the snapshot (and the light, if any).
- Identifiers: anonymous
- Robots are indistinguishable and run the same algorithm.
What is known
Results, in order of publication
First ASYNC result for opaque luminous robots (ICTCS 2022; journal 2023); \(O(1)\) time in FSYNC and SSYNC.
A time–colour trade-off for \(x \in [1, O(\log\log n)]\): \(O(1)\) time with \(O(\sqrt n)\) colours, or \(O(\log\log n)\) time with \(O(1)\) colours. Abstract only.
Asymptotically optimal in time and colours.
Open questions
What is the exact minimum number of colours for \(O(1)\)-epoch uniform circle formation in ASYNC? Feletti et al. 2024
Uniform circle formation with non-rigid moves in the luminous opaque model Feletti et al. 2024.
Notes
Robots are punctiform, disoriented and do not know \(n\); collisions are avoided. The only lower bounds are trivial. Checked against the full texts of Feletti et al. 2023 and Feletti et al. 2024.
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
No catalogued weaker setting.
Lower bounds from stronger settings hold here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.