Abstract
We consider a fixed communication network where (software) agents can move freely from node to node along the edges. A black hole is a faulty or malicious node in the network such that if an agent enters this node, then it immediately “dies.” We are interested in designing an efficient communication algorithm for the agents to identify all black holes. We assume that we have k agents starting from the same node s and knowing the topology of the whole network. The agents move through the network in synchronous steps and can communicate only when they meet in a node. At the end of the exploration of the network, at least one agent must survive and must know the exact locations of the black holes. If the network has n nodes and b black holes, then any exploration algorithm needs Ω(n/k + D b ) steps in the worst-case, where D b is the worst case diameter of the network with at most b nodes deleted. We give a general algorithm which completes exploration in O((n/k)logn/loglogn + bD b ) steps for arbitrary networks, if b≤k/2. In the case when b≤k/2, \(bD_b=O(\sqrt{n})\) and \(k = O(\sqrt{n})\), we give a refined algorithm which completes exploration in asymptotically optimal O(n/k) steps.
Research supported in part by Royal Society Grant ESEP 16244, COST Action TIST 293 (GRAAL), and a visiting fellowship from LaBRI/ENSEIRB for Colin Cooper.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Czyzowicz, J., Kowalski, D.R., Markou, E., Pelc, A.: Searching for a black hole in tree networks. In: Higashino, T. (ed.) OPODIS 2004. LNCS, vol. 3544, pp. 67–80. Springer, Heidelberg (2005); Also appeared as: Searching for a Black Hole in Synchronous Tree Networks. In: Combinatorics, Probability and Computing
Czyzowicz, J., Kowalski, D., Markou, E., Pelc, A.: Complexity of searching for a black hole. Fundamenta Informaticae 71(2-3), 229–242 (2006)
Dobrev, S., Flocchini, P., Kràlovic, R., Prencipe, G., Ruzicka, P., Santoro, N.: Black hole search in common interconnection networks. Networks (to appear); Preliminary version under the title Black Hole Search by Mobile Agents in Hypercubes and Related Networks. In: Proc. 6th Int. Conf. on Principles of Distributed Systems (OPODIS 2002) pp. 169–180 (2002)
Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Mobile search for a black hole in an anonymous ring. In: Welch, J.L. (ed.) DISC 2001. LNCS, vol. 2180, pp. 166–179. Springer, Heidelberg (2001)
Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Searching for a black hole in arbitrary networks: Optimal mobile agents protocols. Distributed Computing (to appear); Preliminary version. In: Proc. 21st ACM Symposium on Principles of Distributed Computing (PODC 2002), pp. 153–161 (2002)
Hohl, F.: Time limited blackbox security: Protecting mobile agents from malicious hosts. In: Vigna, G. (ed.) Mobile Agents and Security. LNCS, vol. 1419, pp. 92–111. Springer, Heidelberg (1998)
Hohl, F.: A framework to protect mobile agents by using reference states. In: Proc. 20th Int. Conf. on Distributed Computing Systems (ICDCS 2000), pp. 410–417 (2000)
Klasing, R., Markou, E., Radzik, T., Sarracco, F.: Approximation bounds for black hole search problems. In: Anderson, J.H., Prencipe, G., Wattenhofer, R. (eds.) OPODIS 2005. LNCS, vol. 3974, pp. 261–274. Springer, Heidelberg (2006)
Klasing, R., Markou, E., Radzik, T., Sarracco, F.: Hardness and approximation results for black hole search in arbitrary graphs. In: Pelc, A., Raynal, M. (eds.) SIROCCO 2005. LNCS, vol. 3499, pp. 200–215. Springer, Heidelberg (2005); Also: Theoretical Computer Science (to appear)
Ng, S., Cheung, K.: Protecting mobile agents against malicious hosts by intention of spreading. In: Arabnia, H. (ed.) Proc. Int. Conf. on Parallel and Distributed Processing and Applications (PDPTA 1999), vol. II, pp. 725–729 (1999)
Sander, T., Tschudin, C.F.: Protecting mobile agents against malicious hosts. In: Vigna, G. (ed.) Mobile Agents and Security. LNCS, vol. 1419, pp. 44–60. Springer, Heidelberg (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cooper, C., Klasing, R., Radzik, T. (2006). Searching for Black-Hole Faults in a Network Using Multiple Agents. In: Shvartsman, M.M.A.A. (eds) Principles of Distributed Systems. OPODIS 2006. Lecture Notes in Computer Science, vol 4305. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11945529_23
Download citation
DOI: https://doi.org/10.1007/11945529_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49990-9
Online ISBN: 978-3-540-49991-6
eBook Packages: Computer ScienceComputer Science (R0)