k-grouping
Robots must form \(k\) distinct groups, each group at its own point.
Problem statement and measuresexpand
\(n\) robots must form exactly \(k\) distinct groups, each group gathered at its own point or converging towards one, and stay apart. The number of groups \(k\) is given; the group sizes are free unless the variant fixes them. With \(k = 1\) this is gathering (or convergence).
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).
\(k\) equal groups, randomized, SSYNC
verifiedWith randomness, robots without any common orientation partition in SSYNC, tolerating crashes.
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: crash faults
- Up to \(f\) robots stop forever at adversarial times and remain visible at their last position.
- Scheduler: SSYNC
- SSYNC: time is divided into rounds; in each round a non-empty subset of robots, chosen by a fair adversary, executes one atomic Look–Compute–Move cycle. Called Atom by Prencipe Prencipe 2007.
- Lights (persistent memory): oblivious
- OBLOT: a robot's computation depends only on the current snapshot; nothing persists across cycles.
- 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: 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: randomized
- Robots may use random bits in Compute; guarantees hold with probability 1 or in expectation, as stated per result.
- Identifiers: anonymous
- Robots are indistinguishable and run the same algorithm.
Statement for this variant
Partition\((n,k)\) of Efrima and Peleg: \(k\) is given to the robots, every group has exactly \(n/k\) robots (\(\lfloor n/k\rfloor\) or \(\lfloor n/k\rfloor + 1\) when \(k\) does not divide \(n\)), robots in one group converge (for every \(\varepsilon\) they are eventually within \(\varepsilon\) of each other) and groups stay more than \(2\eta\) apart, for some fixed \(\eta > 0\). Robots start at distinct points and can count the robots at a point.
What is known
Results, in order of publication
Introductory and current best: randomized, crash-fault tolerant, FSYNC and SSYNC.
Open questions
Partitioning in ASYNC without a common orientation, by a randomized algorithm with no extra memory.
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.