Black virus decontamination of synchronous ring networks by initially scattered mobile agents

Abstract

We study the Black Virus Decontamination problem in ring topologies for initially scattered mobile agents. In this problem a number of mobile agents operate in a network where one of its nodes u is hostile (contaminated) in the following way: when u is visited by an agent, it is decontaminated, the agent vanishes without leaving any trace, and all adjacent nodes of u which are unoccupied by agents are now contaminated. The goal is to find the minimum number of agents that can decontaminate a given network with a black virus at an unknown location and design a fast distributed algorithm for a certain (preferably weak) model of mobile agents. The problem has been introduced by J., Cai et al in 2014 and combines details from two widely studied problems: the Black Hole Search problem and the Intruder Capture problem. We study here the problem for initially scattered mobile agents in synchronous ring topologies. We prove that ten initially scattered agents with a common chirality (i.e., agreement in a global sense of orientation) are necessary and sufficient to solve the problem. If the agents do not have a common chirality then twelve scattered agents with distinct identities are necessary and sufficient, while for anonymous agents the problem is unsolvable. To the best of our knowledge these are the first results concerning the problem for initially scattered agents. © Springer Nature Switzerland AG 2020.