Information Technology Reference
In-Depth Information
At this point the algorithm exploits the local-weak multiplicity detection capability
and moves the robot which is not on the multiplicity towards the other occupied
node.
13.2.3.3 Configurations with an Even Number of Robots on an Odd Size Ring
In this case, the algorithm is divided into three phases. The first two phases aim at
creating a terminal configuration, i.e., a configuration made of only two 1-blocks
of size
k
2 which are separated by exactly one empty node. Finally, the third phase
finalizes the gathering.
The first phase starts from any allowed configuration and creates a configuration
with either a single 1-block or two 1-blocks of size
k
2 . The idea is similar to that of
the case of odd robots. First, only d -blocks are created by moving all the isolated
blocks towards the d -blocks until joining them. Then, the robots move with the
aim of creating a unique d -block. When all the robots belong to the same d -block,
some robots move in order to decrease the d and repeat the algorithm until d
1.
The correctness of the algorithm relies on the fact that the number of nodes in the
ring is odd and the number of robots is even. This implies that if the configuration
is symmetric, then the axis of symmetry passes through exactly one empty node
and one edge. In the second phase, the algorithm moves the two 1-blocks towards
the empty node crossed by the axis of symmetry until a terminal configuration is
created. In the case that the first phase ends with a single 1-block, this is split into
two 1-blocks. All these movements are done by preserving the symmetry of the
configuration. The third phase achieves the gathering from terminal configuration
by moving the two robots that are on the border of the two 1-blocks and that are
neighbors of a single empty node. These two robots move towards the single empty
node. For an example, see Fig. 13.5 . When these two robots are moved one of the
following cases (depending on the activation schedule) can occur:
=
The two robots move synchronously and create a symmetric configuration with
a multiplicity crossed by the axis of symmetry (see Fig. 13.5 c);
Only one robot moves and creates a configuration with two 1-blocks separated
by a single empty node and whose sizes differ by 2 (see Fig. 13.5 b). This con-
figuration is easy to recognize and hence the pending move can be performed,
achieving again a symmetric configuration with a multiplicity crossed by the
axis of symmetry (see Fig. 13.5 c).
At this point, the robots on the multiplicity are not allowed to move. The other
robots see an odd number of robots and perform the last phase of the algorithm
for an odd number of robots (see Fig. 13.4 c-j), so that the gathering is eventually
achieved. This implies that the maximum number k of allowed robots has to satisfy
k
1
<
n
3, that is k
n
5.
Search WWH ::




Custom Search