Contiguous search by mobile agents in cube networks and chordal rings

Abstract

In this thesis 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 move along the network links and the intruder has the capability of escaping arbitrarily fast. We propose different strategies for the solution of the problem in some widely used topologies for the local area network and interconnection network: hypercube network, butterfly network and chordal ring network. In each topology, different models are studied depending on the capabilities of agents; i.e., agents' synchronicity, cloning power and visibility. For each model, we analyze the strategies in terms of number of agents employed, number of moves performed by the agents, and time.