Gathering Asynchronous and Oblivious Robots on Basic Graph Topologies Under the Look-Compute-Move Model - Search Theory: A Game Theoretic Perspective - page 191

it is impossible to accomplish the gathering task. More precisely, initial configura-
tions composed of only two robots, periodic configurations, and those admitting an
edge-edge axis of symmetry do not allow to finalize the gathering.
In [ 21 ], the case of four robots on a ring of five nodes is pointed out as a case of
symmetric initial configurations with an even number of robots that does not allow
any gathering algorithm. This has been also studied in [ 16 ] along with other solvable
cases. In general, symmetric configurations of type node-edge with four robots and
the odd interval cut by the axis bigger than the even one are ungatherable. In the rest
of the chapter these configurations are denoted with the set SP 4. The case of four
robots on a five nodes ring belongs to SP 4. Actually, some configurations in SP 4
could be gatherable but they require strategies that are difficult to generalize.
For all the remaining initial configurations, various gathering algorithms have
been provided, depending also on the assumptions concerning the multiplicity de-
tection capability. Whenever clear by the context, we refer to initial configurations
simply as configurations.
13.2.2 Global-Weak Multiplicity Detection
In this section, a description of the techniques taken from the specific literature are
described. Based on the global-weak multiplicity detection capability, the next algo-
rithms cope with all the cases left from the impossibility results previously shown.
13.2.2.1 Asymmetric Configurations
The asymmetric initial configurations have been firstly handled in [ 22 ]. When such
configurations are aperiodic, they were referred to as rigid configurations. The gath-
ering is performed by exploiting the perception of the robots. Perception allows
robots to agree and move exactly one robot at time although the model does not
allow communication. More precisely, each robot detects which one must perform
the next move based on the configuration perceived during the Look phase. This is
done until the first (and only) multiplicity occurs. Since the scheduler that wakes
the robots up is assumed to be fair, the robot that is allowed to move will eventually
wake up and perform all its Look-Compute-Move cycle. This will ensure the robots
perform all required moves until the desired multiplicity is created. Once the mul-
tiplicity has been created, the robots with only free nodes between themselves and
the multiplicity are allowed to move towards the multiplicity, and joining it, until all
the robots gather at the same node.
At each step of the proposed strategy, and before creating the multiplicity, the
robot allowed to move will be chosen in such a way that the configuration will
never lose its original “rigidity”. Once captured the current configuration during the
Look phase, a robot looks for the pair of robots that are at the maximum distance
(in terms of empty nodes in between) from each other. If only one pair of robots