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.

Existing Global Data Computation (GDC) protocols for asynchronous systems are designed for fully connected networks. In this paper, we discuss GDC in a dedicated asynchronous chordal ring, a type of un-fully connected networks. The virtual links approach, which constructs t+1 (t<n) process-disjoint paths for each pair of processes without direct connection to tolerate failures (where t is the maximum number of processes that may crash and n is the total number of processes), can be applied to solve the GDC problem in the chordal but the virtual links approach incurs high message complexity. To reduce the high communication cost, we propose a non round-based GDC protocol for the asynchronous chordal ring with perfect failure detectors. The main advantage of our approach is that there is no notion of round, processes only send messages via direct connections and the implementation of failure detectors does not require process-disjoint paths. Analysis and comparison with the virtual links approach shows that our protocol reduces the message complexity significantly. / Singapore-MIT Alliance (SMA)

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.