Mutual visibility
Opaque robots must reach positions where no three are collinear, so that every robot sees every other.
Problem statement and measuresexpand
\(n\) opaque point robots (or unit discs) start at distinct points: a robot hides the robots behind it on the same line of sight. They must reach a configuration in which every robot sees every other (no three collinear), without collisions.
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).
Lights, crash faults, ASYNC, one axis
verifiedWith up to \(n\) crashed robots, robots that agree on one axis reach mutual visibility in non-rigid ASYNC in \(O(n)\) epochs with 3 colours.
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: opaque
- Robots are points that obstruct sight: \(r\) sees \(s\) iff no third robot lies on the open segment \(\overline{rs}\).
- 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): lights (LUMI)
- LUMI: each robot has a light with \(c\) colours, set at the end of Compute, visible to all robots including itself; it is both memory and communication. Also called luminous robots, or a full light.
- 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. 2021a; 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.
Statement for this variant
Up to \(f \le n\) robots may crash, at unknown times; a crashed robot never moves again. The correct robots must reach, without collisions, a configuration in which no three correct robots are collinear and no crashed robot lies between two correct ones Poudel et al. 2021.
What is known
- fault-free bound (no robot crashes): one colour does not suffice when \(n\) is unknown and robots must terminate (Section 7 of Di Luna et al. 2017)
Results, in order of publication
Introductory and current best (Theorem 1.1): collision-free, non-rigid moves, each robot moves at most once, and the robots do not end on a convex hull. Improves the 4 colours of the WALCOM 2018 version to 3. In SSYNC 2 colours suffice (Theorem 4.10).
Open questions
Mutual visibility with several crashes when a crashed robot's light stops changing too, which Poudel et al. 2021 call "a major open problem".
Two colours in ASYNC with crashes Poudel et al. 2021.
Notes
The fault model differs from that of Aljohani & Sharma 2018 (one crash, SSYNC, rigid moves, compass): here faults affect only mobility, and lights must keep working after the crash. Checked against the full text of Poudel et al. 2021 (Theorems 1.1 and 4.10).
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
No catalogued weaker setting.
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.