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). These proposed solutions do not require the availability of a map and do not assume FIFO on either nodes or links. Second, we consider the use of scattered agents for Bhs in an asynchronous (i) torus and (ii) complete network. We show that, using 3 scattered agents and 7 tokens in total, a black hole can be located with Θ(n) moves in an oriented asynchronous torus. Again, the solution does not assume FIFO on the links and nodes. If the number of scattered agents in a torus increases, the cost is reduced but communication between these agents becomes significantly more complicated. We propose an algorithm that solves Bhs using k (k>3) scattered agents, with only 1 token per agent, with O( ^k2n2) moves. Beyond theoretical proofs, we also discuss simulations of an actual system in order to evaluate our proposed solutions.