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). It is known that at least two agents are needed; furthermore, with full topological knowledge, (n log n) moves are required in arbitrary networks. The natural question is whether, in speciﬁc networks, it is possible to obtain (topology-dependent but) more cost efﬁcient solutions. It is known that this is not the case for rings. In this article, we show that this negative result does not generalizes. In fact, we present a general strategy that allows two agents to locate the black hole with O(n) moves in common interconnection networks: hypercubes, cube-connected cycles, star graphs, wrapped butterﬂies, chordal rings, as well as in multidimensional meshes and tori of restricted diameter. These results hold even if the networks are anonymous.
|Autori:||DOBREV STEFAN; FLOCCHINI PAOLA; KRÁLOVIC RASTISLAV; PRENCIPE G; RUZICKA PETER; SANTORO NICOLA|
|Titolo:||Black Hole Search in Common Interconnection Networks|
|Anno del prodotto:||2006|
|Appare nelle tipologie:||1.1 Articolo in rivista|