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.

Additional Metadata
Keywords Black kole, Mobile agent, Ring, Scattered, Token, Un-oriented
Persistent URL dx.doi.org/10.1142/S0129054108006327
Journal International Journal of Foundations 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