Complexity of Searching for a Black Hole

• Autorzy: Czyzowicz J. , Kowalski D. , Markou E. , Pelc A.
• Języki publikacji: EN

Abstrakty

EN

A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node, without leaving any trace. We consider the task of locating a black hole in a (partially) synchronous network, assuming an upper bound on the time of any edge traversal by an agent. The minimum number of agents capable to identify a black hole is two. For a given graph and given starting node we are interested in the fastest possible black hole search by two agents, under the general scenario in which some subset of nodes is safe and the black hole can be located in one of the remaining nodes. We show that the problem of finding the fastest possible black hole search scheme by two agents is NP-hard, and we give a 9.3-approximation for it.

Słowa kluczowe

EN

approximation algorithms; black hole; graph mobile agent; NP-hard problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 71, nr 2,3
• Strony: 229--242
• Opis fizyczny: bibliogr. 14 poz.

Twórcy

autor

Czyzowicz J.

autor

Kowalski D.

autor

Markou E.

autor

Pelc A.

• Département d'informatique, Université du Québec en Qutaouais, Gatineau, Québec J8X 3X7, Canada,

Bibliografia

• [1] J. Czyzowicz, D. Kowalski, E. Markou, A. Pelc, Searching for a black hole in tree networks, Proc. 8th International Conference on Principles of Distributed Systems (OPODIS'2004), LNCS 3544, 67-80.
• [2] S. Dobrev, P. Flocchini, R. Kralovic, G. Prencipe, P. Ruzicka, N. Santoro, Black hole search by mobile agents in hypercubes and related networks, Proc. of Symposium on Principles of Distributed Systems (OPODIS 2002), 171-182.
• [3] S. Dobrev, P. Flocchini, G. Prencipe, N. Santoro, Mobile agents searching for a black hole in an anonymous ring, Proc. of 15th International Symposium on Distributed Computing, (DISC 2001), 166-179.
• [4] S. Dobrev, P. Flocchini, G. Prencipe, N. Santoro, Searching for a black hole in arbitrary networks: Optimal Mobile Agents Protocols, Proc. 21st ACM Symposium on Principles of Distributed Computing (PODC 2002), 153-161.
• [5] S. Dobrev, P. Flocchini, G. Prencipe, N. Santoro, Multiple agents rendezvous on a ring in spite of a black hole, Proc. Symposium on Principles of Distributed Systems (OPODIS 2003), 34-46.
• [6] M. Halldórsson, S. Ueno, H. Nakao, Y. Kajitani, Approximating Steiner trees in graphs with restricted weights. Networks 31 (1998) 283-292.
• [7] F. Hohl, Time limited black box security: Protecting mobile agents from malicious hosts, Proc. Conf. On Mobile Agent Security (1998), LNCS 1419, 92-113.
• [8] F. Hohl, A framework to protect mobile agents by using reference states, Proc. 20th Int. Conf. on Distributed Computing Systems (ICDCS 2000), 410-417.
• [9] Minimum Steiner Tree. In http://nada.kth.se/~viggo/wwwcompendium/node78.html
• [10] S. Ng, K. Cheung, Protecting mobile agents against malicious hosts by intention of spreading, Proc. Int. Conf. on Parallel and Distributed Processing and Applications (PDPTA'99), 725-729.
• [11] G. Robins, A. Zelikovsky, Improved steiner tree approximation in graphs. Proc. 10th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA'2000), 770-779.
• [12] T. Sander, C.F. Tschudin, Protecting mobile agents against malicious hosts, Proc. Conf. on Mobile Agent Security (1998), LNCS 1419, 44-60.
• [13] K. Schelderup, J. Ines, Mobile agent security - issues and directions, Proc. 6th Int. Conf. on Intelligence and Services in Networks, LNCS 1597 (1999), 155-167.
• [14] J. Vitek, G. Castagna, Mobile computations and hostile hosts, in: Mobile Objects, D. Tsichritzis, Ed., University of Geneva, 1999, 241-261.