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

a b c d

Fig. 13.1 Symmetric and periodic initial configurations on a ring. White nodes are empty while
each black node is occupied by one robot

The model assumes that k robots are placed over the n nodes of a ring, and in the
initial configurations , nodes are occupied by at most one robot. Depending on the
movements imposed by the running algorithms, multiplicities may occur. A config-
uration is called symmetric if the ring admits a geometrical axis of symmetry ,that
defines a bijective function among the robots residing in the two halves of the ring
cut by the axis. When the global-weak multiplicity is considered, a configuration
is called symmetric if the ring admits a geometrical axis of symmetry that reflects
single robots into single robots, multiplicities into multiplicities, and empty nodes
into empty nodes. In this case, a configuration might be considered symmetric even
though the two halves of the ring cut by the axis do not contain the same number
of robots. This can happen if two symmetric multiplicities at the two halves are
composed of a different number of robots. If the local-strong (or the local-weak)
multiplicity detection is assumed, then a configuration might result symmetric for
some robots while asymmetric for others. For instance, if robots are part of a mul-
tiplicity and the configuration does not admit an axis of symmetry passing through
such a node, then the configuration would result asymmetric for all the robots com-
posing the multiplicity, while it might be symmetric with respect to the perception
of all the other ones. However, symmetric peculiarities of initial configurations are
invariant with respect to the assumed multiplicity detection, as multiplicities are not
allowed at the beginning.
As shown in Fig. 13.1 , a symmetric configuration with an axis of symmetry has
an edge-edge symmetry if the axis goes through two edges (Fig. 13.1 a); it has a node-
edge symmetry if the axis goes through one node and one edge (Fig. 13.1 a); it has a
node-node symmetry if the axis goes through two nodes (Fig. 13.1 c); it has a robot-
on-axis symmetry if there is at least one node on the axis of symmetry occupied by
a robot (both Fig. 13.1 b, c).
A configuration is called periodic if it is invariable under non-trivial (i.e., non-
complete) rotations (Fig. 13.1 d).

13.2.1 Impossibility Results

In [ 22 ], it is proved that the gathering is unsolvable if the multiplicity detection capa-
bility is completely removed in either of its forms. When the multiplicity detection is
assumed, even in its strong and global form, still there are configurations for which