Adrian Kosowski
INRIA Bordeaux

Synchronous Rendezvous for Location-Aware Agents 
Wed, Nov 16, 1 to 2 pm, 5115 HP

Abstract
We study rendezvous of two anonymous agents, where each 
agent knows its own initial position in the environment. 
Their task is to meet each other as quickly as possible. 
The time of the rendezvous is measured by the number of 
synchronous rounds that agents need to use in the worst 
case in order to meet. In each round, an agent may make 
a simple move or it may stay motionless. We consider two 
types of environments, finite or infinite graphs and 
Euclidean spaces. A simple move traverses a single edge 
(in a graph) or at most a unit distance (in Euclidean space). 
The rendezvous consists in visiting by both agents the same 
point of the environment simultaneously (in the same round).
In this paper, we propose several asymptotically optimal 
rendezvous algorithms. In particular, we show that in the 
line and trees as well as in multi-dimensional Euclidean 
spaces and grids the agents can rendezvous in time O(d), 
where d is the distance between the initial positions of 
the agents. The problem of location-aware rendezvous was 
studied before in the asynchronous model for Euclidean spaces 
and multi-dimensional grids, where the emphasis was on the 
length of the adopted rendezvous trajectory. We point out that, 
contrary to the asynchronous case, where the cost of rendezvous 
is dominated by the size of potentially large neighborhoods, 
the agents are able to meet in all graphs of at most n nodes 
in time almost linear in d, namely, O(dlog^2 n). We also 
determine an infinite family of graphs in which synchronized 
rendezvous takes time \Omega(d).

(joint work with: Andrew Collins, Jurek Czyzowicz, 
Leszek Gasieniec, and Russell Martin)