Network Decontamination from Black Viruses

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.


Cai, Jie




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.


Computer Science
Artificial Intelligence




Carleton University

Thesis Degree Name: 

Doctor of Philosophy: 

Thesis Degree Level: 


Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).