BLACK HOLE SEARCH BY MOBILE AGENTS IN HYPERCUBES AND RELATED NETWORKS
Stefan Dobrev, Paola Flocchini, Rastislav Kráľovič, Giuseppe Prencipe, Peter Růžička, Nicola Santoro · 2002
Abstract: Mobile agents operating in networked environments face threats from other agents as well as from the hosts (i.e., network sites) they visit. A black hole is a harmful host that destroys incoming agents without leaving any trace. To determine the location of such a harmful host is a dangerous but crucial task, called black hole search. The most important parameter for a solution strategy is the number of agents it requires (the size); the other parameter of interest is the total number of moves performed by the agents (the cost). Any solution requires moves in general networks; the same lower bound holds for rings. In this paper we show that this lower bound does not hold for hypercubes and related networks. In fact, we present a general strategy which allows two agents to locate the black hole with moves in hypercubes, cube-connected cycles, star graphs, wrapped butterflies, chordal rings, as well as in multidimensional meshes and tori of restricted diameter.