Decontamination from Black Viruses Using Parallel Strategies

Abstract

In this thesis, we consider the problem of decontaminating networks from black viruses (BVs) with a team of mobile agents, using parallel strategies. The BV is a harmful process whose initial location is unknown a priori. It destroys any agent arriving at the network site where it resides and, once triggered, it spreads to all the neighboring sites, creating copies of itself, thus increasing its presence in the network. To eliminate a virus present in a node, an agent has to move on that node; however, once the disinfection is performed, the agent is destroyed (i.e., it becomes inactive and cannot operate anymore). Existing literature has proposed sequential strategies that minimize the spread of the virus, such techniques are however quite inefficient in terms of time complexity. Instead of exploring the network sequentially, we propose to employ a group of agents that cooperate to follow a collective protocol to explore the network simultaneously. In this way, we dramatically reduce the decontamination time, still keeping the spread (and the number of agents loss) asymptotically optimal. In the thesis, various protocols are proposed in meshes, tori, and chordal rings following the monotonicity principle (i.e., once a node is disinfected we prevent it from being recontaminated). Finally, a solution is proposed also for the general case of the arbitrary topology. We analyze theoretically the cost of all our solutions for special topologies showing the advantages of our strategies with respect to the existing ones. In the case of the arbitrary topology, we conduct experimental analysis to assess the performance of our solution, confirming its efficiency. In all cases, our strategies significantly improve time while maintaining asymptotically optimal spread and agent losses.