Contamination and Decontamination in Majority-Based Systems
Paola Flocchini
The dynamics of majority voting has always been of interest in the area of discrete dynamical systems. In recent years, there has been a growing interest on this process also in the distributed computing field, due to its links to fault-tolerance, reliability, and virus disinfection. In fact, local voting mechanisms are often employed in distributed systems and networks as a decision tool for a variety of applications.
In presence of faults, these schemes can trigger a dynamics of contamination: a non-faulty node will exhibit a faulty behavior if the majority of its neighbors is faulty. Some distributed and networked systems employ mechanisms to mend the faults; in these cases a decontamination dynamics is present and interacts with the contamination process. Depending on whether the decontamination is carried out by the majority-voting mechanism already in place or by the use of a team of mobile agents, the decontamination process is called internal or external, respectively.
In this paper we focus on the contamination and decontamination processes in majority based systems and we survey the recent results in presence of both internal and external decontamination.
Keywords: Majority voting, majority rule, dynamic monopolies, dynamos, decontamination.