Deterministic Symmetric Rendezvous in Arbitrary Graphs: Overcoming Anonymity, Failures and Uncertainty - Search Theory: A Game Theoretic Perspective - page 177

whiteboard of its territory (function “WRITE-ALL”). To read the partial-view of
neighboring agents, an agent visits each external node x and reads the contents of the
whiteboard at x (function “READ-PV”). In any round i , if agent A reads a partial-
view PV i , x greater than its own partial-view PV i , A in this round, then agent A is
defeated (i.e. it becomes passive and does not participate in the algorithm anymore)
and the edge connecting node x to the tree T A is used to merge the two trees. This
process is repeated for k iterations or until the territory of an agent spans the whole
graph.
The algorithm assumes the prior knowledge of k

= |Q|

. Alternately if the value
of n is known (but not k ) then the algorithm may be modified accordingly to use
this information. In this case, the main loop of the algorithm will be executed for
at most n iterations and the agent will terminate the algorithm successfully if its
territory contains n nodes.

Algorithm 2: Make-Tree(k)
Execute procedure DDFS to construct the territory T A ;
PV 1 , A COMPUTE-PV( T A );

for phase i

←

1 to k do
if Number of Agents in T A is k then
Collect all agents to root;
Return(“Success”);
WRITE-ALL( PV i , A , i );
S ← READ-PV ( i );
State ← COMPARE-PV( PV iA , S );
if State = Passive then
SEND-MERGE( i );
WRITE-ALL(“Defeated”, i );
Return to homebase and execute WAIT();

=

else

RECEIVE-MERGE( i );
execute UPDATE-PV() and continue;

WRITE-ALL(“Failure”);

Lemma 1 ([ 14 ]). Algorithm Make-Tree solves Rendezvous-with-Detect using O ( mk )

moves in total and requires O ( m log n ) whiteboard memory for each node.

A modified version of the algorithm solves rendezvous for all solvable instances
in at most O

moves. The only modification is during the comparison of
the partial-views; if the agent A finds that all neighboring agents have the same

( m log k )