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.
展开▼
