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 fat robots, ASYNC, limited visibility, compass
verifiedTime: unknownColours: tight
Opaque fat robots with limited visibility and a common coordinate system form a uniform circle of given centre and radius in ASYNC.
Assumed (added on the last edge are outlined)
+Faultsno faults+Agreement on coordinatesagreement on both axes (common compass)+Movementrigid: every move reaches its destination
Not assumed
Bodyfat robots (unit discs)Visibilitylimited: robots see only within a fixed radiusOpacityopaque: collinear robots hide each otherSchedulerasynchronous (ASYNC)Lights (persistent memory)oblivious, no light (OBLOT)Multiplicity detectionnone: a point with several robots looks like one robotRandomnessdeterministicIdentifiersanonymous: all robots are identical
Formal definitions of this setting
- Body: fat
- Each robot is a closed disc of radius 1 (unit disc). Discs may not overlap, so robots cannot share a point and must avoid collisions; a disc hides what lies behind it from other robots. Gathering then asks for a configuration whose union of discs is connected and in which every robot sees all others Czyzowicz et al. 2009.
- Visibility: limited visibility
- A robot sees exactly the robots within Euclidean distance \(V\) of its position, for a fixed radius \(V>0\).
- 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): oblivious
- OBLOT: a robot's computation depends only on the current snapshot; nothing persists across cycles.
- Agreement on coordinates: compass
- All robots agree on the directions and orientations of both axes (a common compass); they may still disagree on origin and unit. Called full compass by Efrima and Peleg, who also use half compass (both axis directions, the positive sense of one axis, no chirality), direction-only and axes-only Efrima & Peleg 2009. Agreement on one axis together with common chirality is equivalent: the orientation of the second axis then follows from handedness.
- 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
Time · rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known
unknown
—
lower boundnone known
introductory—
current best
\(\text{finite}\)
common origin and axesthe circle's centre and radius are given
Colours · colours of the light per robot (0 for oblivious robots)
tight
No colours.
lower boundnone known
introductory—
current best
\(0\)
common origin and axesthe circle's centre and radius are given
Results, in order of publication
Mondal et al. 2020 current best
Time \(\text{finite}\)Colours \(0\)
common origin and axesthe circle's centre and radius are given
Introductory and current best (Theorem 1). A preprint.
Open questions
None recorded for this variant.
Notes
Checked against the full text.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.