Partitioning
Robots must partition themselves into \(k\) groups of exactly \(n/k\) robots each, each group at its own point.
Problem statement and measuresexpand
\(n\) robots, with \(k\) dividing \(n\), must partition themselves into \(k\) groups of exactly \(n/k\) robots, each group gathered at its own point, and stay there. The \(k\) points, and so the group size \(n/k\), are given (the papers' \(k\)-EPF and \(k\)-circle formation name the group size \(k\), which is \(n/k\) here).
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).
Exactly \(n/k\) robots at each fixed point
standard settingverifiedWith one common axis, the configurations and numbers \(k\) of fixed points for which exactly \(n/k\) robots can gather at each of given fixed points are characterised.
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: transparent
- Robots do not obstruct each other's view.
- 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: one axis
- All robots agree on the direction and orientation of one axis (e.g. North), but not necessarily on handedness: two robots may disagree on which side is East. This is how the papers use one axis agreement (e.g. robots "agree on only 'left' and 'right'" Bose et al. 2021; robots "do not necessarily have the same handedness" Pagli et al. 2015). One axis and chirality are alternatives on this axis; together they amount to a common compass.
- Movement: non-rigid
- In a Move phase the adversary may stop a robot before its destination, but only after it has travelled at least \(\delta>0\) (a constant unknown to the robots) or reached the 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
Introductory and current best. Also \(k\)-circle formation: disjoint circles of \(n/k\) robots each, centred at the fixed points.
Open questions
Partitioning into \(k\) groups of size \(n/k\) at points chosen by the robots (no fixed points given).
Notes
The \(k\)-EPF problem generalises embedded pattern formation: the fixed points are visible to all robots and each must end with exactly \(n/k\) robots (their \(k\) is \(n/k\) here) Bhagat et al. 2021.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.