Searching for a black hole in arbitrary networks: optimal mobile agents protocols | Distributed Computing
Skip to main content
Springer Nature Link
Log in

Searching for a black hole in arbitrary networks: optimal mobile agents protocols

  • Original Article
  • Published:
Distributed Computing Aims and scope Submit manuscript

Abstract

Consider a networked environment, supporting mobile agents, where there is a black hole: a harmful host that disposes of visiting agents upon their arrival, leaving no observable trace of such a destruction. The black hole search problem is the one of assembling a team of asynchronous mobile agents, executing the same protocol and communicating by means of whiteboards, to successfully identify the location of the black hole; we are concerned with solutions that are generic (i.e., topology-independent). We establish tight bounds on the size of the team (i.e., the number of agents), and the cost (i.e., the number of moves) of a size-optimal solution protocol. These bounds depend on the a priori knowledge the agents have about the network, and on the consistency of the local labelings. In particular, we prove that: with topological ignorance Δ+1 agents are needed and suffice, and the cost is Θ(n 2), where Δ is the maximal degree of a node and n is the number of nodes in the network; with topological ignorance but in presence of sense of direction only two agents suffice and the cost is Θ(n 2); and with complete topological knowledge only two agents suffice and the cost is Θ(n log n). All the upper-bound proofs are constructive.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM J. Comput. 29, 1164–1188 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  2. Alpern, S., Baston, V., Essegaier, S.: Rendezvous search on a graph. J. Appl. Probab. 36(1), 223–231 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  3. Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous. Kluwer (2003)

  4. Averbakh, I., Berman, O.: A heuristic with worst-case analysis for minimax routing of two traveling salesmen on a tree. Discrete Appl. Math. 68, 17–32 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  5. Awerbuch, B., Betke, M., Singh, M.: Piecemeal graph learning by a mobile robot. Inf. Comput. 152, 155–172 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  6. Barrière, L., Flocchini, P., Fraigniaud, P., Santoro, N.: Rendezvous and election of mobile agents: impact of sense of direction. Theory Comput. Syst. (in press)

  7. Barrière, L., Flocchini, P., Fraigniaud, P., Santoro, N.: Capture of an intruder by mobile agents. In: Proceedings of the 14th ACM Symposium on Parallel Algorithms and Architectures (SPAA'02), pp. 324–332 (2002)

  8. Barrière, L., Flocchini, P., Fraigniaud, P., Santoro, N.: Can we elect if we cannot compare? In: Proceedings of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA'03), pp. 200–209 (2003)

  9. Bender, M., Fernandez, A., Ron, D., Sahai, A., Vadhan, S.: The power of a pebble: Exploring and mapping directed graphs. In: Proceedings of the 30th ACM Symposium on Theory of Computing (STOC'98), pp. 269–287 (1998)

  10. Bender, M., Slonim, D.K.: The power of team exploration: two robots can learn unlabeled directed graphs. In: Proceedings of the 35th Symposium on Foundations of Computer Science (FOCS'94), pp. 75–85 (1994)

  11. Blum, A., Raghavan, P., Schieber, B.: Navigating in unfamiliar geometric terrain. SIAM J. Comput. 26, 110–137 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  12. Blum, M., Kozen, D.: On the power of the compass (or, why mazes are easier to search than graphs). In: Proceedings of the 19th Symposium on Foundations of Computer Science (FOCS'78), pp. 132–142 (1978)

  13. Chess, D.M.: Security issues in mobile code systems. In: Proceedings of the Conference on Mobile Agent Security, LNCS 1419, pp. 1–14 (1998)

  14. Deng, X., Kameda, T., Papadimitriou, C.H.: How to learn an unknown environment i: The rectilinear case. J. ACM 45, 215–245 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  15. Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. J. Graph Theory 32(3), 265–297 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  16. Dessmark, A., Fraigniaud, P., Pelc, A.: Deterministic rendezvous in graphs. In: Proceedings of the 11th European Symposium on Algorithms (ESA'03), pp. 184–195 (2003)

  17. Dessmark, A., Pelc, A.: Optimal graph exploration without good maps. In: Proceedings of the 10th European Symposium on Algorithms (ESA'02), pp. 374–386 (2002)

  18. Deugo, D.: Mobile agents for electing a leader. In: Proceedings of the 4th International Symposium on Autonomous Decentralized System, pp. 324–324 (1999)

  19. Diks, K., Fraigniaud, P., Kranakis, E., Pelc, A.: Tree exploration with little memory. J. Algorith. 51, 38–63 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  20. Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Mobile search for a black hole in an anonymous ring. Algorithmica (in press)

  21. Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Finding a black hole in an arbitrary network: optimal mobile agents protocols. In: Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC'02), pp. 153–162 (2002)

  22. Dudek, G., Jenkin, M., Milios, E., Wilkes, D.: Robotic exploration as graph construction. Trans. Robot. Autom. 7(6), 859–865 (1991)

    Article  Google Scholar 

  23. Esparza, O., Soriano, M., Munoz, J.J., Forne, J.: Host revocation authority: A way of protecting mobile agents from malicious hosts. In: Proceedings of the International Conference onWeb Engineering (ICWE'03), LNCS 2722 (2003)

  24. Flocchini, P., Mans, B., Santoro, N.: Sense of direction: definition, properties and classes. Networks 32(3), 165–180 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  25. Flocchini, P., Mans, B., Santoro, N.: Sense of direction in distributed computing. Theor. Comput. Sci. (291), 29–53 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  26. Flocchini, P., Roncato, A., Santoro, N.: Backward consistency and sense of direction in advanced distributed systems. SIAM J. Comput. 32(2), 281–306 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  27. Fraigniaud, P., Gasieniec, L., Kowalski, D., Pelc, A.: Collective tree exploration. In: Proceedings of the 6th Latin American Theoretical Informatics Symposium (LATIN'04), pp. 141–151 (2004)

  28. Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. In: Proceedings of the 29th Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 451–462 (2004)

  29. Frederickson, G.N., Hecht, M.S., Kim, C.E.: Approximation algorithms for some routing problems. SIAM J. Comput. 7, 178–193 (1978)

    Article  MathSciNet  Google Scholar 

  30. Greenberg, M.S., Byington, J.C., Harper, D.G.: Mobile agents and security. IEEE Commun. Mag. 36(7), 76–85 (1998)

    Article  Google Scholar 

  31. Gyuri, E.: On division of graphs to connected subgraphs. In: Proceedings of the 5th Hungarian Combinatorial Colloquium (1976)

  32. Hohl, F.: Time limited blackbox security: Protecting mobile agents from malicious hosts. In: Proceedings of the Conference on Mobile Agent Security, LNCS 1419, pp. 92–113 (1998)

  33. Hohl, F.: A framework to protect mobile agents by using reference states. In Proceedings of the 20th International Conference on Distributed Computing Systems (ICDCS 2000) (2000)

  34. Jennings, N.R.: On agent-based software engineering. Artif. Intell. 117(2), 277–296 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  35. Kozen, D.: Automata and planar graphs. In: Proceedings of the Fundations Computatial Theory (FCT'79), pp. 243–254 (1979)

  36. Kranakis, E., Krizanc, D., Santoro, N., Sawchuk, C.: Mobile agent rendezvous in a ring. In: Proceedings of the International Conference on Distibuted Computing Systems (ICDCS'03), pp. 592–599 (2003)

  37. Lovàsz, L.: A homology theory for spanning trees of a graph. Acta Mathematica Academiae Scientiarum Hungaricae 30(3,4), 241–251 (1977)

    Article  MathSciNet  Google Scholar 

  38. Muller, H.: Automata catching labyrinths with at most three components. Elektronische Informationsverarbeitung und Kybernetic 15(1), 3–9 (1979)

    Google Scholar 

  39. Ng, S.K., Cheung, K.W.: Protecting mobile agents against malicious hosts by intention spreading. In: Proceedings of the 1999 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'99), pp. 725–729 (1999)

  40. Oppliger, R.: Security issues related to mobile code and agent-based systems. Comput. Commun. 22(12), 1165–1170 (1999)

    Article  Google Scholar 

  41. Panaite, P., Pelc, A.: Exploring unknown undirected graphs. J. Algorith. 33, 281–295 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  42. Rabin, M.O.: Maze threading automata. Technical Report Seminar Talk, University of California at Berkeley (1967)

  43. Rollik, H.A.: Automaten in planaren graphen. Acta Inform. 13, 287–298 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  44. Roo, N., Hareti, S., Shi, W., Iyengar, S.: Robot navigation in unknown terrains: Introductory survey of length,non-heuristic algorithms. Technical Report ORNL/TM12410, Oak Ridge National Lab. (1993)

  45. Sander, T., Tschudin, C.F.: Protecting mobile agents against malicious hosts. In: Proceedings of the Conference on Mobile Agent Security, LNCS 1419, pp. 44–60 (1998)

  46. Schelderup, K., Ones, J.: Mobile agent security–issues and directions. In: Proceedings of the 6th International Conference on Intelligence and Services in Networks, LNCS 1597, pp. 155–167 (1999)

  47. Shannon, CL.E.: Presentation of a maze-solving machine. In: Proceedings of the 8th Conference of the Josiah Macy Jr. Found. (Cybernetics), pp. 173–180 (1951)

  48. Vitek, J., Castagna, G.: Mobile computations and hostile hosts. In: Tsichritzis, D. (ed.). Mobile Objects, pp. 241–261. University of Geneva (1999)

  49. Yu, X., Yung, M.: Agent rendezvous: A dynamic symmetry-breaking problem. In: Proceedings of the International Colloquium on Automata Languages and Programming (ICALP'96), pp. 610–621 (1996)

Download references

Author information

Authors and Affiliations

  1. School of Information Technology and Engineering, University of Ottawa, Ottawa, Canada

    Stefan Dobrev & Paola Flocchini

  2. Dipartimento di Informatica, Università di Pisa, Italy

    Giuseppe Prencipe

  3. School of Computer Science, Carleton University, Ottawa, Ontario, Canada

    Nicola Santoro

Authors
  1. Stefan Dobrev
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paola Flocchini
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Giuseppe Prencipe
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Nicola Santoro
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Stefan Dobrev.

Additional information

A preliminary version of this paper appeared in the Proceedings of the 21st ACM Symposium on Principles of Distributed Computing [21].

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dobrev, S., Flocchini, P., Prencipe, G. et al. Searching for a black hole in arbitrary networks: optimal mobile agents protocols. Distrib. Comput. 19, 1–99999 (2006). https://doi.org/10.1007/s00446-006-0154-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00446-006-0154-y

Keywords

Search

Navigation