USING SCATTERED MOBILE AGENTS TO LOCATE A BLACK HOLE IN AN UN-ORIENTED RING WITH TOKENS
Stefan Dobrev, Nicola Santoro, WEI SHI · International Journal of Foundations of Computer Science · 2008
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.