In this thesis, the problem of decontaminating networks from Black Viruses (BVs) using a team of system mobile agents, i.e., the BVD problem, is investigated. The BV is a dynamic harmful process which, like the extensively studied black hole (BH), destroys any agent arriving at the network site where it resides; when that occurs, unlike a black hole which is static by definition, a BV moves, spreading to all the neighbouring sites, thus increasing its presence in the network. The initial location of BV is unknown a priori. The objective is to permanently remove any presence of the BV from the network with minimum number of site infections (and thus casualties) and prevent any previously decontaminated node from becoming infected again.
The BVD problem is first studied in the systems with only one BV. Initial investigations are for some common classes of interconnection networks: (multidimensional) grids, tori, and hypercubes. Optimal solutions are proposed and their complexities are analyzed in terms of node infections, agent team size, and movements. After understanding the basic properties of the decontamination process in these special graphs, the BVD problem is studied in arbitrary networks. Finally the research is extended to Multiple BV Decontamination problem (MBVD) both in arbitrary graphs and in special topologies.
To help understand the behavior of the protocol developed and support complexity analysis, an experimental study is performed using the simulator for reactive distributed algorithms DisJ. A large number of simulations are carried out on various sizes of graphs with many connectivity densities. The simulation runs show that the propose protocol beats random search; they also disclose many interesting behaviors, and validate the analytical complexity results. The simulation results also provide deep understanding on the influence of graph connectivity density and graph size on complexities, i.e., movement, time, and agent size.
Finally conclusion remarks are presented and future researches are proposed.