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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/202806
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 3
social impact