Scattering
Robots that may start at shared points must move to pairwise distinct points.
Problem statement and measuresexpand
\(n\) robots start at points of the plane, several possibly at the same point (a multiplicity). They must reach a configuration in which all positions are distinct, and stay there.
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).
Randomized, SSYNC, weak multiplicity detection
verifiedWithout strong multiplicity detection no algorithm scatters in \(O(1)\) expected rounds; with an optimal number of random bits \(O(\log\log n)\) rounds suffice.
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: 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: weak multiplicity
- A snapshot marks each occupied point as holding one robot or more than one.
- 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.
What is known
- Theorem 4.1: no algorithm runs in \(O(1)\) expected rounds without strong multiplicity detection
- Theorem 4.5: only for algorithms that use the optimal number of random bits
Results, in order of publication
Corollary 4.1, with an optimal number of random bits. The analysis is in FSYNC; the algorithms are valid in SSYNC. Without any multiplicity detection, algorithm \(SA_\phi\) (their \(SA_f\)) scatters in \(O(\phi(n))\) expected rounds for any increasing surjective function \(\phi\) (Theorem 4.2), but the robots never stop moving.
Open questions
None recorded for this variant.
Notes
\(n\log n\) random bits are necessary in any setting Bramas & Tixeuil 2017. Bramas and Tixeuil split multiplicity detection into local and global. Checked against arXiv 1309.6603 version 2, not the journal version.
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
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.