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.