Premium
Black hole search in common interconnection networks
Author(s) -
Dobrev S.,
Flocchini P.,
Královič R.,
Ružička P.,
Prencipe G.,
Santoro N.
Publication year - 2006
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20095
Subject(s) - computer science , hypercube , star (game theory) , interconnection , topology (electrical circuits) , trace (psycholinguistics) , polygon mesh , black hole (networking) , chordal graph , network topology , routing (electronic design automation) , theoretical computer science , combinatorics , computer network , mathematics , parallel computing , routing protocol , graph , computer graphics (images) , mathematical analysis , linguistics , philosophy , link state routing protocol
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 specific networks, it is possible to obtain (topology‐dependent but) more cost efficient 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 butterflies , chordal rings , as well as in multidimensional meshes and tori of restricted diameter. These results hold even if the networks are anonymous. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(2), 61–71 2006