A general approach to toroidal mesh decontamination with local immunity
Fabrizio Luccio, Linda Pagli · 2009
Network decontamination is studied on a k-dimensional torus (n1times ldrldrldr times nk), with k ges 1 and 2 les n1lesldrldrldrles nk. The decontamination is done by a set of agents moving on the net according to a new cleaning model. After an agent leaves from a vertex, this vertex remains uncontaminated as long asmneighbors are uncontaminated. We propose algorithms valid for any m les 2k (i.e., up to the vertex degree), proving that A(k, m) synchronous agents suffice, with: A(k, 0) = 1; A(k, m) = 2m-1, for 1 les m les k + 1; A(k, m) = 22k-m+1n1n2ldrldrldr nm-k-1, for k + 2 les m les 2k. We also study the total number M(k, m) of agent moves, and prove matching lower bounds on A(k, m) and M(k, m) valid form = 3 and any k, and for all m ges k+1. Our study can be simply extended to asynchronous functioning.