WorldCIST'15 - 3rd World Conference on Information Systems and Technologies

Full Program »

Black Virus Decontamination in Arbitrary Networks

In this paper we investigate the problem of decontaminating a network from the presence of a black virus (BV), a harmful entity capable both of destroying any agent arriving at the site where it resides, and of moving to all the neighbouring sites.
This problem integrates in its definition both the harmful aspects of the classical static black hole search problem with the mobility aspects of the classical intruder capture or network decontamination problem.
The initial location of the BV is unknown; the critical objective for a team of system agents is to locate and eliminate the BV with the minimum number of network infections and agent casualties. The decontamination process is clearly dangerous for the system agents and for the nodes infected by the spreading of the BV.
The problem of black virus decontamination (BVD) has been investigated only for special classes of highly regular network topologies.

In this paper, we consider the BVD problem and show how to solve it in networks of arbitrary topology.
The solution protocol is provably correct, deterministic, generic (i.e., works irrespective of the network topology), and worst-case optimal. In fact, we prove that our protocol always correctly decontaminates the network with the minimum number of system agents' casualties and network infections. Furthermore, we show that the total number of system agents is asymptotically optimal.


Jie Cai    
Carleton University

Paola Flocchini    
University of Ottawa

Nicola Santoro    
Carleton University


Powered by OpenConf®
Copyright ©2002-2013 Zakon Group LLC