Information Technology Reference
In-Depth Information
of exploration are alternated with rounds of competition between agents. During an
exploration round, an agent may fall into a black hole and die, without completing
the process of marking its territory. Thus, during the competition an agent can win
over another agent based on either comparison of territories or comparison of round
number (a dead agent would not be able to increment its round number). When an
agent
A
wins the territory of another agent (that may have died) there may be unex-
plored edges incident to this territory and the agent
A
needs to expand the territory
during the next exploration round. Recall that it is not possible to distinguish be-
tween a dead agent and an agent that is slow in moving along an edge. This means
that an agent cannot wait for another agent to complete its exploration. Thus, there
could be multiple agents expanding a given territory simultaneously. Those agents
which are in the same territory need to coordinate with each other in the exploration
and competition tasks. This is done by communicating using messages written on
the whiteboard of the root node. The algorithm ensures that there is always a unique
root node in every territory during the execution of the algorithm.
At any stage of the algorithm, there are teams of agents, each team possessing a
territory
which is a connected acyclic subgraph of
G
(disjoint from other territories).
Each team of agents tries to expand its territory until it spans a majority of the nodes.
Once a team is able to acquire more than half the nodes of the network, it wins and
agents from all other teams join the winning team to achieve rendezvous. We call
this algorithm as Algorithm
RDV_BH
.
−
τ
Theorem 12 ([
9
]).
Algorithm
RDV_BH
correctly solves rendezvous for k
agents
in any network whose extended-map is symmetric-covering minimal provided the
agents initially knows a bound B such that n
≤
B
<
2
n. The moves complexity of
algorithm
RDV_BH
is O
(
m
(
m
+
k
))
.
The above result implies that the algorithm described in this section is optimal in
terms of the moves complexity.
12.9 Conclusion
We considered the problem of symmetric asynchronous rendezvous in graphs whose
nodes are anonymous and whose edges are locally ordered. Since the agents are
identical and follow the same deterministic algorithm, solving the problem requires
breaking the symmetry and finding a unique location to meet. This is possible only
if there is some asymmetry in the structure of the graph (for agents that cannot
mark the graph) or if the agents start from asymmetric locations within the graph
(in the case when agents are allowed to mark their starting location). It is possible
determine for exactly which instances rendezvous is feasible and then solve ren-
dezvous in those cases. We presented solutions for rendezvous with detection and
also discussed techniques for dealing with exceptional situations involving faulty
nodes, token failures and inconsistencies in local labelling of the edges. While all
solutions studied here assume that the edges of the graph are bidirectional, some of
Search WWH ::
Custom Search