Special Issue: Advances in Parallel and Distributed Computational ModelsNo Access

DECONTAMINATING CHORDAL RINGS AND TORI USING MOBILE AGENTS

PAOLA FLOCCHINI

SITE, University of Ottawa, Canada

Search for more papers by this author

MIAO JUN HUANG

SITE, University of Ottawa, Canada

Search for more papers by this author

, and

FLAMINIA L. LUCCIO

Dip. di Matematica e Informatica, University of Trieste, Italy

Search for more papers by this author

https://doi.org/10.1142/S0129054107004838Cited by:30 (Source: Crossref)

Abstract

In this paper we consider a network where an intruder is moving "contaminating" the nodes it passes by, and we focus on the problem of decontaminating such a network by a team of mobile agents.

The contamination/decontamination process has the following asynchronous dynamics: when the team is deployed all nodes are assumed to be contaminated, when an agent transits on a node, it will clean the node, when the node is left with no agent, the node will be recontaminated as soon as at least one of its neighbours is contaminated.

We study the problem in asynchronous chordal ring networks and in tori. We consider two variations of the model: one where agents have only local knowledge, the other in which they have "visibility", i.e., they can "see" the state of their neighbouring nodes.

We first derive lower bounds on the minimum number of agents necessary for the decontamination. In the case of chordal rings we show that the number of agents necessary to perform the cleaning does not depend on the size of the network; in fact it is linear in the length of the longest chord (provided that it is not too long). In the case of a torus, the minimum number of agents is equal to 2 · h, where h is the smallest dimension.

We then propose optimal strategies for decontamination and we analyse the number of moves and the time complexity of the decontamination algorithms, showing that the visibility assumption allows us to decrease substantially both complexity measures. Another advantage of the "visibility model" is that agents move independently and autonomously without requiring any coordination.

References

M. Asaka et al. , A method of tracing intruders by use of mobile agents , Proceedings of the 9th Annual Conference of the Internet Society (INET) ( 1999 ) . Google Scholar
H. Attiyaet al., Algorithmica 4, 437 (1989), DOI: 10.1007/BF01553900. Crossref, Web of Science, Google Scholar
L. Barrièreet al., Capture of an intruder by mobile agents, Proceedings of the 14-th ACM Symposium on Parallel Algorithms and Architectures (SPAA) (2002) pp. 200–209. Google Scholar
L. Barrièreet al., Searching is not jumping, Proceedings of the 29th International Workshop on Graph Theoretic Concepts in Computer Science (WG), Lecture Notes in Computer Science 2880 (Springer Verlag, 2003) pp. 34–45. Google Scholar
J.-C. Bermond, F. Comellas and D. F. Hsu, Journal of Parallel and Distributed Computing 24, 2 (1995), DOI: 10.1006/jpdc.1995.1002. Crossref, Web of Science, Google Scholar
L. Blinet al., Distributed Chasing of Network Intruders by Mobile Agents, Proceedings of the 13th International Colloquium on Structural Information and Communication Complexity (SIROCCO) (2006) pp. 70–84. Google Scholar
R. Breish, Southwestern cavers VI(5), 72 (1967). Google Scholar
J. A. Ellis, I. H. Sudborough and J. S. Turner, Information and Computation 113, 50 (1994), DOI: 10.1006/inco.1994.1064. Crossref, Web of Science, Google Scholar
P. Flocchini , M. J. Huang and F. L. Luccio , Contiguous search in the hypercube for capturing an intruder , Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS) . Google Scholar
P. Flocchini, F. L. Luccio and L. X. Song, Size Optimal Strategies for Capturing an Intruder in Mesh Networks, Proceedings of the International Conference on Communications in Computing (CIC) (2005) pp. 200–206. Google Scholar
P. Flocchini, A. Nayak and A. Shulz, Cleaning an arbitrary regular network with mobile agents, Proceedings of the 2nd International Conference on Distributed Computing & Internet Technology (ICDCIT) (2005) pp. 132–142. Google Scholar
F. V. Fomin, D. M. Thilikos and I. Todinca, Connected graph searching in outer-planar graphs, Proceedings of the 7th Int. Colloquium on Graph Theory (ICGT), Electronic Notes in Discrete Mathematics 22 (2005) pp. 213–216. Google Scholar
N. Foukia , J. G. Hulaas and J. Harms , Intrusion Detection with Mobile Agents , 11th Annual Internet Society Conference (INET) ( 2001 ) . Google Scholar
L. M. Kirousis and C. H. Papadimitriou, Theoretical Computer Science 47, 205 (1986), DOI: 10.1016/0304-3975(86)90146-5. Crossref, Web of Science, Google Scholar
D. Krizanc and F. L. Luccio , Boolean Routing on Chordal Rings , Proceedings of the 2nd Colloquium on Structural Information and Communication Complexity (SIROCCO) ( 1995 ) . Google Scholar
A. Lapaugh, Journal of the ACM 40(2), 224 (1993), DOI: 10.1145/151261.151263. Crossref, Web of Science, Google Scholar
B. Mans, Journal of Parallel and Distributed Computing 46(1), 80 (1997), DOI: 10.1006/jpdc.1997.1389. Crossref, Web of Science, Google Scholar
N. Megiddoet al., Journal of the ACM 35(1), 18 (1988), DOI: 10.1145/42267.42268. Crossref, Web of Science, Google Scholar
B. Monien and I. H. Sudborough, Theoretical Computer Science 58, 209 (1988), DOI: 10.1016/0304-3975(88)90028-X. Crossref, Web of Science, Google Scholar
T. Parson, Theory and applications in graphs, Lecture Notes in Mathematics (Springer-Verlag, 1976) pp. 426–441. Google Scholar
T. Parson, The search number of a connected graph, 9-th Southeastern Conference on Combinatorics, Graph Theory and Computing (Utilitas Mathematica, 1978) pp. 549–554. Google Scholar
S. Penget al., Algorithmica 27, 395 (2000). Crossref, Web of Science, Google Scholar
E. H. Spafford and D. Zamboni, Computer Networks 34(4), 547 (2000), DOI: 10.1016/S1389-1286(00)00136-5. Crossref, Web of Science, Google Scholar
P. Yospanya et al. , Detecting and cleaning intruders in sensor networks , Proceedings of the 8th National Computer Science and Engineering Conference ( 2004 ) . Google Scholar