Rendezvous of Mobile Agents in Anonymous Networks with Faulty Channels∗

A group of identical mobile agents moving asynchronously among the nodes of an anonymous network have to gather together in a single node of the graph. This problem known as the (asyn-chronous anonymous multi-agent) rendezvous problem has been studied extensively but only for networks that are safe or fault-free. In this paper, we consider the case when some of the edges in the network are dangerous or faulty such that any agent travelling along one of these links would be destroyed. The objective is to minimize the number of agents that are destroyed and achieve rendezvous of all the surviving agents. We determine under what conditions this is possible and present algorithms for achieving rendezvous in such cases. Our algorithms are for arbitrary net-works with an arbitrary number of dangerous channels; thus our model is a generalization of the case where all the dangerous channels lead to single node, called the Black Hole. We do not assume prior knowledge of the network topology; In fact, we show that knowledge of only a “tight ” bound on the network size is sufficient for solving the problem, whenever it is solvable