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

Chapter 11
Rendezvous Problem
Leszek G asieniec
Abstract The rendezvous problem refers to the algorithmic challenge in which two
or more mobile entities (depending on the context) called players, agents or robots,
are expected to meet at the same time and point in space. The meeting challenge
can be a task on its own or it may form a part of a more complex communication
or coordination process in which the agents are involved. The space can be either a
network of discrete nodes between which the agents can move along existing edge
connections, or a geometric environment in which movement of agents is only re-
stricted by topological properties of the space. In order to meet, the agents must
agree in advance on a rendezvous mechanism. The feasibility and efficiency of the
adopted rendezvous solution depends on agents' ability to move, observe and com-
municate. In this chapter we give a short introduction to the rendezvous problem
including motivation, models of considered networks and participating agents. We
also provide some examples and discuss instances of the considered problem.
11.1 Introduction
With the recent advent of ad-hoc, not well-structured, large, and (very often)
dynamic network environments there is a strong need for more robust, universal,
and inexpensive distributed network protocols. The purpose of these protocols is to
support basic network integrity mechanisms as well as more dedicated tasks such
as information dissemination, network search and discovery, frequent monitoring
including handling emergencies.