Black Virus Disinfection in Chordal Rings

Abstract

The topic of this thesis is black virus disinfection using mobile agents. The black virus is a faulty node that destroys any visiting agent without leaving a trace; moreover, once the black virus is triggered by an agent, it clones itself and spreads to neighbouring nodes. These viruses can only be destroyed if they move to nodes that have been occupied by agents. In this thesis, we consider the black virus disinfection problem in chordal rings. Initially, the system contains a single black virus that resides at an unknown location. We propose a solution that involves deploying a team of mobile agents to locate the original black virus and to prevent further damage once it has been triggered. Our protocol is divided into two phases: 1) searching the graph until the black virus is found and triggered and 2) sending agents to occupy the neighbouring nodes of the black virus in order to trigger and destroy all the black viruses at once. Our solutions are monotone, meaning that once a node has been explored it is protected from re-infection. In order to measure the efficiency of our protocol we consider the total number of agents required for disinfection, the overall number of black viruses and the number of moves required by the agents. We then analyze the cost of all our solutions, providing optimal bounds for some classes of chordal rings.