2008-12-01
Using scattered mobile agents to locate a black hole in an un-oriented ring with tokens
Publication
Publication
International Journal of Foundations of Computer Science , Volume 19 - Issue 6 p. 1355- 1372
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 | |
---|---|
Black kole, Mobile agent, Ring, Scattered, Token, Un-oriented | |
dx.doi.org/10.1142/S0129054108006327 | |
International Journal of Foundations of Computer Science | |
Organisation | 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
|