loading...
Contiguous Search in the Hypercube for Capturing an Intruder
Denver, Colorado April 04-April 08
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2005.15119th IEEE International Parallel and ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Paola Flocchini, University of Ottawa, Canada
Miao Jun Huang, University of Ottawa, Canada
Flaminia L. Luccio, University of Trieste, Italy
In this paper we consider the problem of searching for an intruder in a network. There is a team of collaborative software agents that are deployed to capture a hostile intruder (e.g., a virus). These agents asynchronously move along the network links and the intruder has the capability of escaping arbitrarily fast. We propose two different strategies for the solution of the problem in a widely studied topology: the hypercube network. In the first strategy one of the agents acts as a coordinator making the other agents move in a precise way; this strategy requires O(n log n) moves, a team of O(\frac{n}{{n\log n}}) agents and runs in O(n log n) time steps. The second strategy is devised for a model where the agents are allowed to "see" the state of their neighbours. In this case, the computation is local, i.e., there is no need of a coordinator and agents can move automously. In this setting the solution requires \frac{n}{2} agents, but is much faster (log n time steps), and requires the same number of moves (O(n log n)).
Citation:
Paola Flocchini, Miao Jun Huang, Flaminia L. Luccio, "Contiguous Search in the Hypercube for Capturing an Intruder," ipdps, vol. 1, pp.62, 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, 2005
Usage of this product signifies your acceptance of the Terms of Use.