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

a c e g

b d f

h j

i

Fig. 13.4 Second phase of the gathering algorithm for an odd number of robots with local-weak
multiplicity detection capability. A multiplicity is denotes as a circle around an occupied node

=

eventually a configuration with only three nodes occupied is achieved where j 2

and q 2 = 0. In this case, all the robots in r 0 join those in r 2 (see rule R4 ) achieving a

configuration where k 1 robots are gathered on the same node. Finally, the single

robot joins the other ones. In the case that q 0 is not the only maximum interval
of empty nodes, the algorithm moves r 1 towards q 1 , enlarging q 0 (see rule R2-2 ).
After this moment, q 0 is the only maximum interval of empty nodes. It can occur
that q 1 becomes smaller than 2 or the maximal configuration view is reversed. For
instance this can happen when q 1 =

−

q j . In the first case, the algorithm for q 0 ≥ 3

and q 1 < 2 is applied and in the second case the algorithm is applied on the new

maximal configuration view.

13.2.3.2 Configurations with an Odd Number of Robots

The description of the algorithm requires some definitions and terminology. Let d
be the size of the minimum interval of empty nodes plus one, a d - block is a maximal
path where there is exactly one occupied node every d edges. The size of a d -block
is the number of robots that it contains.
The algorithm works in two phases. The first phase builds a configuration made
of a single 1-block, and the second phase achieves gathering.