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

Partial-view, then agent A returns to its homebase and waits (instead of continuing
with the competition rounds for k iterations). This algorithm would not have an
explicit termination.
Another possible modification to the algorithm is to reduce the memory re-
quired for the whiteboards (see [ 14 ]). If the whiteboards at each node are limited
to O bits, then a modified version of Algorithm Make-Tree can be used to

solve Rendezvous-with-Detect using O

( log n )

m 2 k

( ) ( )

moves
in total. The idea of this algorithm is to perform the comparisons of partial-views
by traversing the territories of the neighbors. Thus the agents have to perform addi-
tional moves, but the only information that we need to write on the whiteboards is
the label assigned to the node and a link to its parent in the tree.

log n bit whiteboards and O

12.7 Rendezvous Using Tokens

In this section we consider the rendezvous problem in the token model where each
agent has a token which they can place on any node they visit. Note that tokens used
by all agents are identical (and thus indistinguishable). As opposed to the previous
section, there are no public whiteboards on the nodes. If every agent puts its token on
its starting location, we have a bicoloring on the nodes of the graph representing the
function . The agent can now execute Algorithm 1 with the following

modification. The initial classification partitions the nodes into two classes-those
that contain a token and those that do not! The algorithm will succeed in solving
rendezvous whenever the conditions of Theorem 2 are satisfied. Moreover, the algo-
rithm can solve Rendezvous-with-Detect, if the exact value of n is known. However
this algorithm is not efficient in terms of the moves complexity as we have seen. We
present below a different algorithm which is more efficient [ 8 ].

χ

p on V

( G )

12.7.1 Rendezvous with a Single Unmovable Token

The algorithm for rendezvous presented in this section is for two agents, though
the same idea may be used to rendezvous any k 2 agents using a more involved

algorithm. We assume that an agent always places the token at its starting loca-
tion. First, suppose there is a single agent exploring a graph G . The fact that the
starting node r of the agent is marked and can be distinguished from other nodes,
makes it easier to perform an exploration of G . The agent can perform a breadth-first
traversal building a BFS-tree T rooted at r . During the traversal, whenever the agent
explores a new edge and reaches a node v , it checks whether v is same as some
node u in its tree. This can be done by successively applying the label-sequences
for the back-paths from each node u

≥

∈

T to the root r , and checking if one of these
hits the marked node. Based on this idea, we have an algorithm for building a map
of G with a single agent starting from a unique marked homebase in G (see Algo-
rithm 3 ). The algorithm maintain a BFS-tree T containing the visited nodes and a
data structure called ROOT_PATHS that stores the edge-labeled path P in T from