Deterministic Symmetric Rendezvous in Arbitrary Graphs Overcoming Anonymity, Failures and Uncertainty

Abstract We consider the rendezvous problem of gathering two or more identical agents that are initially scattered among the nodes of an unknown graph. We discuss some of the recent results for this problem focusing only on deterministic algorithms for the general case when the graph topology is unknown, the nodes of the graph may not be uniquely labeled and the agents may not be synchronized with each other. In this scenario, the objective is to solve rendezvous whenever deterministically feasible, while optimizing on the amount of movement by the agents or the memory required (for the nodes or the agents) in the worst case. Further we also investigate some special scenarios such as (i) when the graph contains some dangerous nodes or, (ii) when there is no consistent ordering on the edges of a node. We present positive results, complexity analysis and some general techniques for dealing with such worst case scenarios for the symmetric rendezvous problem. 1.