A black hole in a network is a highly harmful host that disposes of any incoming agents upon their arrival. Determining the location of a black hole in a ring network has been studied when each node is equipped with a whiteboard. Recently, the Black Hole Search problem was solved in a less demanding and less expensive token model with co-located agents. Whether the problem can be solved with scattered agents in a token model remains an open problem. In this paper, we show not only that a black hole can be located in a ring using tokens with scattered agents, but also that the problem is solvable even if the ring is un-oriented. More precisely, first we prove that the black hole search problem can be solved using only three scattered agents. We then show that, with K (K 4) scattered agents, the black hole can be located in O(kn + n log n) moves. Moreover, when K (K K) is a constant number, the move cost can be reduced to O(n log n), which is optimal. These results hold even if both agents and nodes are anonymous.

, , , , ,
doi.org/10.1142/S0129054108006327
International Journal of Foundations of Computer Science
School of Computer Science

Dobrev, S. (Stefan), Santoro, N, & Shi, W. (2008). Using scattered mobile agents to locate a black hole in an un-oriented ring with tokens. In International Journal of Foundations of Computer Science (Vol. 19, pp. 1355–1372). doi:10.1142/S0129054108006327