文章基本信息

标题：Decontaminating a Network from a Black Virus
其他标题：Decontaminating a Network from a Black Virus
本地全文：下载
作者：Jie Cai ; Paola Flocchini ; Nicola Santoro 等
期刊名称：International Journal of Networking and Computing
印刷版ISSN：2185-2847
出版年度：2014
卷号：4
期号：1
页码：151-173
语种：English
出版社：International Journal of Networking and Computing
摘要：In this paper, we consider the problem of decontaminating a network from a black virus (BV) using a team of mobile system agents. The BV is a harmful process which, like the extensively studied black hole (BH), destroys any agent arriving at the network site where it resides; when that occurs, unlike a black hole which is static by definition, a BV moves, spreading to all the neighbouring sites, thus increasing its presence in the network. If however one of these sites contains a system agent, that clone of the BV is destroyed (i.e., removed permanently from the system). The initial location of the BV is unknown a priori. The objective is to permanently remove any presence of the BV from the network with minimum number of site infections (and thus casualties). The main cost measure is the total number of agents needed to solve the problem. This problem integrates in its definition both the harmful aspects of the classical black hole search problem (where however the dangerous elements are static) with the mobility aspects of the classical intruder capture or network decontamination problem (where however there is no danger for the agents). Thus, it is the first attempt to model mobile intruders harmful not only for the sites but also for the agents. We start the study of this problem by focusing on some important classes of interconnection networks: grids, tori, and hypercubes. For each class we present solution protocols and strategies for the team of agents, analyze their worst case complexity, and prove their optimality.Â
关键词：Network decontamination; Dangerous graphs; Mobile Entities; Distributed Computing