Rendezvous Problem - Search Theory: A Game Theoretic Perspective - page 162

In case of deterministic rendezvous one needs to break symmetry between
agents. For example, if the agents were anonymous (indistinguishable) they would
perform the same moves and be always separated by distance d The symmetry be-

tween the agents can be broken in many different ways including further informa-
tion about network size and topology, labels given to agents, or through awareness
of their own location.
In the context of the line most of the deterministic rendezvous strategies refer to
asynchronous models, where the cost of the solution corresponds to the cumulative
distance walked by any agent before rendezvous takes place. In [ 17 ] the authors dis-
cuss efficient rendezvous strategies for trees which impose rendezvous on the path
of length n with the cost O

.

In [ 16 ] agents are labelled and two algorithms for
the infinite line are considered. If d is known to both agents the cost of rendezvous
is O

( n ) .

2

,where L min refers to the size of the smaller label. If d is not known
in advance the rendezvous cost rises to O

( d | L min | )

d 3

3

where L max represents the
size of the larger label. Performance of the latter algorithm is improved in [ 28 ],
where we find an algorithm with cost O

( + | L max | ) ,

log 2 d ( d · + d · d log d | L max | + d | L min | 2 +

| L min | ) .

A different approach to rendezvous on the line was adopted by Collins etal.[ 11 ],
where they assumed that the agents are not aware of d but they know their own
location on the line. In particular, they proved that two agents in the synchronised
model can always meet in time at most 6 d

L max || L min | log |

Further, they also showed that their
approach can be adopted in the asynchronous model with the rendezvous cost O

.

( d ) .

11.4 Also in This Volume

In this short introduction to the rendezvous problem the emphasis is mainly on major
features of considered models of networks and mobile agents. Two more compre-
hensive survey type documents can be found in Chaps. 12 and 13 . The list of ten
open problems from the perspective of Operational Research, including the Astro-
naut Problem and the Telephone Problem, can be found in Chap. 14 .
Chapter 12 surveys rendezvous in several models of distributed networks where
the emphasis is on deterministic algorithms for networks with unknown topology.
The authors consider several types of networks including those containing 'mali-
cious' nodes (known in literature as black holes) and networks in which no consis-
tent ordering on the edges at each node is imposed. The chapter provides a selection
of algorithmic solutions (upper bounds), non trivial complexity analysis as well as
it introduces more general techniques developed for the worst case scenarios in the
rendezvous problem. This work is a nice complement of the recent survey on the
topic written by Pelc [ 24 ] that adopts stronger assumptions about the network en-
vironment including distinct node identifiers, synchronicity, or restricted network
topologies such as the ring, mesh or tree topologies.
Chapter 13 refers to the rendezvous problem in asynchronous networks in which
the oblivious memory Look-Compute-Move model is assumed [ 25 ]. The mobile