Exploring an unknown graph to locate a black hole using tokens

Abstract

Consider a team of (one or more) mobile agents operating in a graph G. Unaware of the graph topology and starting from the same node, the team must explore the graph. This problem, known as graph exploration, was initially formulated by Shannon in 1951, and has been extensively studied since under a variety of conditions. The existing investigations have all assumed that the network is safe for the agents, and the solutions presented in the literature succeed in their task only under this assumption. Recently, the exploration problem has been examined also when the network is unsafe. The danger examined is the presence in the network of a black hole, a node that disposes of any incoming agent without leaving any observable trace of this destruction. The goal is for at least one agent to survive and to have all the surviving agents to construct a map of the network, indicating the edges leading to the black hole. This variant of the problem is also known as black hole search. This problem has been investigated assuming powerful inter-agent communication mechanisms: whiteboards at all nodes. Indeed, in this model, the black hole search problem can be solved with a minimal team size and performing a polynomial number of moves. In this paper, we consider a less powerful token model.We constructively prove that the black hole search problem can be solved also in this model; furthermore, this can be done using a minimal team size and performing a polynomial number of moves. Our algorithm works even if the agents are asynchronous and if both the agents and the nodes are anonymous.