A general approach to toroidal mesh decontamination with local immunity

Network decontamination is studied on a k-dimensional torus (n₁ times ldrldrldr times n_k), with k ges 1 and 2 les n₁ lesldrldrldrles n_k. 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) = 2^m-1, for 1 les m les k + 1; A(k, m) = 2^2k-m+1 n₁ n₂ ldrldrldr n_m-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.