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.

Black kole, Mobile agent, Ring, Scattered, Token, Un-oriented
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