We consider the problem of decontaminating an infected network using as few mobile cleaning agents as possible and avoiding recontamination. After a cleaning agent has left a vertex v, this vertex will become recontaminated if m or more of its neighbors are infected, where m≥1 is a threshold parameter of the system indicating the local immunity level of the network. This network decontamination problem, also called monotone connected graph search and intruder capture, has been extensively studied in the literature when m=1 (no immunity). In this paper, we extend these investigations and consider for the first time the network decontamination problem when the parameter m is an arbitrary integer value m≥1. We direct our study to widely used interconnection networks, namely meshes, tori, and trees. For each of these classes of networks, we present decontamination algorithms with threshold m; these algorithms work even in asynchronous setting, either directly or with a simple modification requiring one additional agent. We also establish general lower bounds on the number of agents necessary for decontamination with immunity m; these bounds are tight in the case of trees, while large gaps still exist in the case of meshes and tori.

Network decontamination under m-immunity

LUCCIO, FABRIZIO;PAGLI, LINDA;
2016-01-01

Abstract

We consider the problem of decontaminating an infected network using as few mobile cleaning agents as possible and avoiding recontamination. After a cleaning agent has left a vertex v, this vertex will become recontaminated if m or more of its neighbors are infected, where m≥1 is a threshold parameter of the system indicating the local immunity level of the network. This network decontamination problem, also called monotone connected graph search and intruder capture, has been extensively studied in the literature when m=1 (no immunity). In this paper, we extend these investigations and consider for the first time the network decontamination problem when the parameter m is an arbitrary integer value m≥1. We direct our study to widely used interconnection networks, namely meshes, tori, and trees. For each of these classes of networks, we present decontamination algorithms with threshold m; these algorithms work even in asynchronous setting, either directly or with a simple modification requiring one additional agent. We also establish general lower bounds on the number of agents necessary for decontamination with immunity m; these bounds are tight in the case of trees, while large gaps still exist in the case of meshes and tori.
2016
Flocchini, Paola; Luccio, Fabrizio; Pagli, Linda; Santoro, Nicola
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/840701
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 2
social impact