Corelab Seminar

Shantanu Das (Aix-Marseille University, Marseille, France)
Symmetric Rendezvous in Graphs: Deterministic Approaches

We present deterministic strategies for the rendezvous of two (or more) identical agents moving in an arbitrary connected graph. The agent move asynchronously starting from distinct vertices of the graph and they are required to eventually meet at a single vertex of the graph. Since the agents are identical and execute the same algorithm, rendezvousing the agents requires exploiting the asymmetry in the environment, in terms of the structure of the graph, the graph labeling and the initial positions of the agents. Thus, in some cases rendezvous is not realizable and we are interested in algorithms that detect the feasibility of deterministic rendezvous in a given environment and achieve rendezvous whenever it is feasible. The techniques used for solving Rendezvous-with-Detect depends on the capabilities of the agents (e.g. are they allowed to mark the vertices), the prior knowledge available to the agents (e.g. an estimate of the graph size) and the optimization criteria (e.g. whether we wish to minimize the amount of movement or the memory required for rendezvous). We will review several such techniques that are applicable for graphs of arbitrary and unknown topologies. We will also consider certain fault-tolerance issues.