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

the objective was to minimize the expected time to meet. If we are restricted to de-
terministic strategies, the objective may be to minimize the worst-case time to meet,
over all possible starting configurations. Moreover if there is no common notion of
time, we may wish to minimize the total distance traveled by the agents until ren-
dezvous. In some cases, there are other parameters to consider, for example the size
of memory used by the agents or the number of additional resources (e.g. flags for
marking) used by the agents.
This chapter considers the deterministic rendezvous of two or more agents in
a finite connected graph, placed initially at locations chosen by an adversary. The
agents are assumed to be identical and they execute the same algorithm, without
global knowledge about the graph. Other than finiteness and connectivity, we make
no other assumptions about the topology of the graph. In an arbitrary connected
graph, it is not always possible to solve rendezvous using deterministic means. For
instance consider a ring of size n , where two agents are placed at a distance of n 2

from each other; if each agent follows the same strategy (any combination of moving
clockwise, counterclockwise or remaining stationary) the agents may forever be
the same distance apart from each-other. In most cases, the ability to distinguish
vertices in some way allows the agents to rendezvous even if they are using identical
strategies. Given any graph and the starting locations of the agents in the graph, it
is possible to determine whether rendezvous is possible for the particular instance.
Thus, it is possible to characterize the instances where deterministic rendezvous
is feasible. The prior knowledge of certain graph parameters (such as the size or
diameter) or the ability to mark vertices of the graph also influences the feasibility
of rendezvous.
The model considered here is very generic in the sense that we do not assume
any global clock (the agents act asynchronously), nor do we assume unique identi-
fiers for the nodes of the graph or for the agents (the graph and the agents may be
anonymous); and the graph topology is not known to the agents (i.e. the topology
could be any arbitrary connected graph). In stronger models, e.g. when the agents
have distinct identifiers [ 11 , 16 ] or, when they are synchronous [ 12 , 13 ], or if the
environment is restricted to specific topologies such as the ring [ 19 , 22 ], grid [ 4 ]
or tree [ 13 ] topologies, then it becomes easier to solve rendezvous and the set of
solvable instances may become relatively larger. For results on rendezvous in such
models, please see the recent survey [ 23 ]. Another significant difference between
the results in this chapter and those of [ 23 ] is that we allow the agents to meet only
at a node, whereas most results from the above paper also allow meeting on an edge
when two agents are traversing it from opposite sides. 1 The rendezvous problem
has also been studied in a completely different model where the agents move in a
continuous terrain [ 18 ]orinagraph[ 21 ] but have global visibility. Finally there
exist many results on solving rendezvous using randomized algorithms (see [ 3 ]for
a survey).

/

1 This difference implies that in our model it is not possible to rendezvous even on the trivial graph
consisting of two nodes and a single edge.