Searching for a black hole in interconnected networks using mobile agents and tokens

We study the impact of the topological structure on the complexity of the Black hole search (Bhs) problem using mobile agents that communicate via tokens. First, we show that the token model can support the same cost as in the whiteboard model, despite the fact that communication between mobile agents is considerably more restricted (and complex) in a token model than in a whiteboard one. More precisely, in this paper, we focus on three specific topologies, namely: an asynchronous (i) hypercube, (ii) torus and (iii) complete network. With knowledge of which of these topologies is being used, we present token-based solutions for Bhs   where the number of moves executed by a team of two co-located anonymous agents can be reduced to Θ(n)$\Theta \left(n\right)$. These proposed solutions do not require the availability of a map and do not assume FIFO on either nodes or links.