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\) groups of equal size
standard settingverifiedRobots split into \(k\) groups of \(n/k\) that converge apart; with a full compass a deterministic crash-tolerant algorithm works in ASYNC.
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: 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: 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.
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: deterministic, crash-fault tolerant, in every timing model with a full compass. Also crash-tolerant in FSYNC and SSYNC with a half compass (both axis directions, one positive orientation, no chirality), and not crash-tolerant in ASYNC with a half compass.
Open questions
None recorded for this variant.
Notes
Efrima and Peleg call this partitioning; the catalogue's partitioning also fixes, in advance, the \(k\) points at which the groups of \(n/k\) robots gather. Convergence is Partition\((n,1)\). 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.