Abstract
We address the problem of mobile agents searching a ring network for a highly harmful item, a black hole, a stationary process destroying visiting agents upon their arrival.No observable trace of such a destruction will be evident.The location of the black hole is not known; the task is to unambiguously determine and report the location of the black hole.W e answer some natural computational questions: How many agents are needed to locate the black hole in the ring ? How many suffice? What a-priori knowledge is required? as well as complexity questions, such as: With how many moves can the agents do it ? How long does it take ?
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
L. Barrière, P. Flocchini, P. Fraigniaud, and N. Santoro. Gathering of mobile agents with incomparable labels. Tech.Rep. ECHO-01, Center for e-Computing, 2001.
M.A. Bender and D. Slonim. The power of team exploration: Two robots can learn unlabeled directed graphs.In FOCS’ 94, pages 75–85, 1994.
B. Brewington, R. Gray, and K. Moizumi. Mobile agents in distributed information retieval. Intelligent Information Agents, pages 355–395, 1999.
W. Chen, C. Leng, and Y. Lien. A novel mobile agent search algorithm. Information Sciences, 122(2-4):227–240, 2000.
K. Diks, A. Malinowski, and A. Pelc. Reliable token dispersal with random faults. Parallel Processing Letters, 4:417–427, 1994.
K. Diks, A. Malinowski, and A. Pelc. Token transfer in a faulty network. Theoretical Informatics and Applications, 29:383–400, 1995.
K. Diks and A. Pelc. Fault-tolerant linear broadcasting. Nordic Journal of Computing, 3:188–201, 1996.
S. Dobrev, P. Flocchini, G. Prencipe, and N. Santoro. Finding a black hole in an arbitrary network.Tech.Rep. ECHO-03, Center for e-Computing, 2001.
O. Goldreich and L. Shrira. Electing a leader in a ring with link failures. Acta Informatica, 24:79–91, 1987.
O. Goldreich and L. Shrira. On the complexity of computation in the presence of link failures: The case of a ring. Distr. Computing, 5:121–131, 1991.
J. Hammer and J. Fiedler. Using mobile crawlers to search the web efficiently. International Journal of Computer and Information Systems.To appear.
F. Hohl.A framework to protect mobile agents by using reference states.In ICDCS 2000, 2000.
N.R. Jennings. On agent-based software engineering. Art. Intelligence, 117(2):277–296, 2000.
L.M. Kirousis, E. Kranakis, D. Krizanc, and Y.C. Stamatiou. Locating information with uncertainty in fully interconnected networks.In DISC’ 00, pages 283–296, 2000.
K. Moizumi and G. Cybenko. The travelling agent problem. Mathematics of Control, Signal and Systems, 1998.
D. Rus, R. Gray, and D. Kotz. Autonomous and adaptive agents that gather information.In AAAI’ 96, pages 107–116, 1996.
T. Sander and C.F. Tschudin. Protecting mobile agents against malicious hosts. In Mobile Agents and Security, LNCS 1419, pages 44–60, 1998.
K. Schelderup and J. Ines. Mobile agent security-issues and directions. In 6th Int. Conf. on Intell. and Services in Networks, LNCS 1597, pages 155–167, 1999.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N. (2001). Mobile Search for a Black Hole in an Anonymous Ring. In: Welch, J. (eds) Distributed Computing. DISC 2001. Lecture Notes in Computer Science, vol 2180. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45414-4_12
Download citation
DOI: https://doi.org/10.1007/3-540-45414-4_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42605-9
Online ISBN: 978-3-540-45414-4
eBook Packages: Springer Book Archive