Contiguous Search in the Hypercube for Capturing an Intruder

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)).

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( 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 autonomously. In this setting the solution requires n/2 agents, but is much faster (logn time steps), and requires the same number of moves (O(n log n)).