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)).
Contiguous Search in the Hypercube for Capturing an Intruder
LUCCIO, Flaminia
2005-01-01
Abstract
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)).File | Dimensione | Formato | |
---|---|---|---|
ipdps05.pdf
non disponibili
Tipologia:
Documento in Pre-print
Licenza:
Accesso chiuso-personale
Dimensione
291.57 kB
Formato
Adobe PDF
|
291.57 kB | Adobe PDF | Visualizza/Apri |
I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.