Black hole search in a ring network has been studied in a token model. It is known that locating the black hole in an anonymous ring using tokens is feasible, if the team of agents is initially co-located. When dealing with the scattered agents, the problem was so far solved only when the orientation of the ring is known. In this paper, we prove that a black hole can be located in a ring using tokens with scattered agents, 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 fewer moves. Moreover, when k (k ≥ 4) is a constant number, the move cost can be made optimal. These results hold even if both agents and nodes are anonymous.

Additional Metadata
Keywords Anonymous, Asynchronous, Black hole, Mobile agent, Ring, Scattered, Token, Un-oriented
Citation
Dobrev, S. (Stefan), Santoro, N, & Shi, W. (2007). Locating a black hole in an un-oriented ring using tokens: The case of scattered agents.