Network decontamination is studied on a k-dimensional torus (n1 times ldrldrldr times nk), with k ges 1 and 2 les n1 lesldrldrldrles 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+1 n1 n2 ldrldrldr 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.
A General Approach to Toroidal Mesh Decontamination with Local Immunity
LUCCIO, FABRIZIO;PAGLI, LINDA
2009-01-01
Abstract
Network decontamination is studied on a k-dimensional torus (n1 times ldrldrldr times nk), with k ges 1 and 2 les n1 lesldrldrldrles 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+1 n1 n2 ldrldrldr 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.