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).
Progress map
tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Colours
Randomized, SSYNC, strong multiplicity detection + strong multiplicity, + randomized
0 open · 2 results
tight
\(O(1)\) vs \(\text{impossible}\)
symmetry
tight
\(0\) vs —
tight
\(O(\log\log n)\) vs \(\text{not } O(1)\)
symmetry breaking
tight
\(0\) vs —
Limited visibility, connectivity preserving limited visibility, + transparent, + no faults, + SSYNC, + randomized
0 open · 1 results
tight
\(O(\min\{n,g^2+\log n\})\) vs \(\Omega(n)\)
distance
tight
\(0\) vs —
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.