More agents may decrease global work: A case in butterfly decontamination

This paper is a contribution to network decontamination with a view inherited from parallel processing. At the beginning some or all the vertices may be contaminated. The network is visited by a group of decontaminating agents. When a decontaminated vertex is left by the agents, it can be re-contaminated only if the number of infected neighbors exceeds a certain immunity threshold m. The main goal of the studies in this line is to minimize the number A of agents needed to do the job and, for a minimum team, to minimize the number M of agent moves. Instead of M we consider the number T of steps (i. e. parallel moves) as a measure of time, and evaluate the quality of a protocol on the basis of its work W = A T. Taking butterfly networks as an example, we compare different protocols and show that, for some values of m, a larger team of agents may require smaller work.

Authors

• Fabrizio Luccio
• Linda Pagli

Keywords

• Network decontamination
• Distributed protocol
• Agent
• Work
• Butterfly
• Graph search