Abstract
We examine the problem of rendezvous, i.e., having multiple mobile agents gather in a single node of the network. Unlike previous studies, we need to achieve rendezvous in presence of a very powerful adversary, a malicious agent that moves through the network and tries to block the honest agents and prevents them from gathering. The malicious agent can be thought of as a mobile fault in the network. The malicious agent is assumed to be arbitrarily fast, has full knowledge of the network and it cannot be exterminated by the honest agents. On the other hand, the honest agents are assumed to be quite weak: They are asynchronous and anonymous, they have only finite memory, they have no prior knowledge of the network and they can communicate with the other agents only when they meet at a node. Can the honest agents achieve rendezvous starting from an arbitrary configuration in spite of the malicious agent? We present some necessary conditions for solving rendezvous in spite of the malicious agent in arbitrary networks. We then focus on the ring and mesh topologies and provide algorithms to solve rendezvous. For ring networks, our algorithms solve rendezvous in all feasible instances of the problem, while we show that rendezvous is impossible for an even number of agents in unoriented rings. For the oriented mesh networks, we prove that the problem can be solved when the honest agents initially form a connected configuration without holes if and only if they can see which are the occupied nodes within a two-hops distance. To the best of our knowledge, this is the first attempt to study such a powerful and mobile fault model, in the context of mobile agents. Our model lies between the more powerful but static fault model of black holes (which can even destroy the agents), and the less powerful but mobile fault model of Byzantine agents (which can only imitate the honest agents but can neither harm nor stop them).
S. Das—This work has been partially supported by the ANR - MACARON project (anr-13-js02-0002).
F.L. Luccio—This work has been partially supported by the PRIN 2010 Project Security Horizons.
E. Markou—Part of this work has been done while this author was visiting Università Ca’ Foscari Venezia. This research has been co-financed by the European Union (European Social Fund – ESF) and Greek national funds through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework (NSRF) — Research Funding Program: THALIS-NTUA (MIS 379414).
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
Notes
- 1.
We select as searcher the second agent that arrives at node v.
References
Agmon, N., Peleg, D.: Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM J. Comput. 36(1), 56–82 (2006)
Alpern, S., Gal, S.: Searching for an agent who may or may not want to be found. Oper. Res. 50(2), 311–323 (2002)
Bampas, E., Leonardos, N., Markou, E., Pagourtzis, A., Petrolia, M.: Improved periodic data retrieval in asynchronous rings with a faulty host. In: Halldórsson, M.M. (ed.) SIROCCO 2014. LNCS, vol. 8576, pp. 355–370. Springer, Heidelberg (2014)
Barriere, L., Flocchini, P., Fomin, F.V., Fraigniaud, P., Nisse, N., Santoro, N., Thilikos, D.: Connected graph searching. Inf. Comput. 219, 1–16 (2012)
Bouzid, Z., Das, S., Tixeuil, S.: Gathering of mobile robots tolerating multiple crash faults. In: IEEE 33rd International Conference on Distributed Computing Systems, ICDCS 2013, 8–11 July 2013, Philadelphia, Pennsylvania, USA, pp. 337–346 (2013)
Chalopin, J., Das, S.: Rendezvous of mobile agents without agreement on local orientation. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6199, pp. 515–526. Springer, Heidelberg (2010)
Chalopin, J., Das, S., Santoro, N.: Rendezvous of mobile agents in unknown graphs with faulty links. In: Pelc, A. (ed.) DISC 2007. LNCS, vol. 4731, pp. 108–122. Springer, Heidelberg (2007)
Chalopin, J., Dieudonné, Y., Labourel, A., Pelc, A.: Fault-tolerant rendezvous in networks. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 411–422. Springer, Heidelberg (2014)
Cohen, R., Peleg, D.: Convergence of autonomous mobile robots with inaccurate sensors and movements. SIAM J. Comput. 38, 276–302 (2008)
Czyzowicz, J., Labourel, A., Pelc, A.: How to meet asynchronously (almost) everywhere. In: Proceedings of 21st Annual ACM-SIAM Symposium on Discrete Algorithms (2010)
Das, S., Mihalák, M., Šrámek, R., Vicari, E., Widmayer, P.: Rendezvous of mobile agents when tokens fail anytime. In: Baker, T.P., Bui, A., Tixeuil, S. (eds.) OPODIS 2008. LNCS, vol. 5401, pp. 463–480. Springer, Heidelberg (2008)
Dieudonne, Y., Pelc, A., Peleg, D.: Gathering despite mischief. ACM Trans. Algorithms 11(1), 1 (2014)
Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Multiple agents rendezvous in a ring in spite of a black hole. In: Papatriantafilou, M., Hunel, P. (eds.) OPODIS 2003. LNCS, vol. 3144, pp. 34–46. Springer, Heidelberg (2004)
Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Mobile search for a black hole in an anonymous ring. Algorithmica 48(1), 67–90 (2007)
Flocchini, P., Huang, M.J., Luccio, F.L.: Decontamination of chordal rings and tori using mobile agents. Int. J. Found. Comput. Sci. 3(18), 547–564 (2007)
Flocchini, P., Huang, M.J., Luccio, F.L.: Decontamination of hypercubes by mobile agents. Networks 3(52), 167–178 (2008)
Flocchini, P., Ilcinkas, D., Santoro, N.: Ping pong in dangerous graphs: optimal black hole search with pebbles. Algorithmica 62(3–4), 1006–1033 (2012)
Flocchini, P., Santoro, N.: Distributed security algorithms for mobile agents. In: Cao, J., Das, S.K. (eds.) Mobile Agents in Networking and Distributed Computing, Chap. 3, pp. 41–70. Wiley, Hoboken (2012)
Klasing, R., Markou, E., Radzik, T., Sarracco, F.: Hardness and approximation results for black hole search in arbitrary graphs. TCS 384(2–3), 201–221 (2007)
Královič, R., Miklík, S.: Periodic data retrieval problem in rings containing a malicious host. In: Patt-Shamir, B., Ekim, T. (eds.) SIROCCO 2010. LNCS, vol. 6058, pp. 157–167. Springer, Heidelberg (2010)
Kranakis, E., Krizanc, D., Markou, E.: The Mobile Agent Rendezvous Problem in the Ring. Synthesis Lectures on Distributed Computing Theory. Morgan and Claypool Publishers, San Rafael (2010)
Luccio, F.L.: Contiguous search problem in sierpinski graphs. Theory Comput. Syst. 44, 186–204 (2009)
Yamauchi, Y., Izumi, T., Kamei, S.: Mobile agent rendezvous on a probabilistic edge evolving ring. In: ICNC, pp. 103–112 (2012)
Yu, X., Yung, M.: Agent rendezvous: a dynamic symmetry-breaking problem. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol. 1099, pp. 610–621. Springer, Heidelberg (1996)
Zeng, Y., Hu, X., Shin, K.: Detection of botnets using combined host- and network-level information. In: IEEE/IFIP DSN 2010, pp. 291–300, June 2010
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Das, S., Luccio, F.L., Markou, E. (2015). Mobile Agents Rendezvous in Spite of a Malicious Agent. In: Bose, P., Gąsieniec, L., Römer, K., Wattenhofer, R. (eds) Algorithms for Sensor Systems. ALGOSENSORS 2015. Lecture Notes in Computer Science(), vol 9536. Springer, Cham. https://doi.org/10.1007/978-3-319-28472-9_16
Download citation
DOI: https://doi.org/10.1007/978-3-319-28472-9_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-28471-2
Online ISBN: 978-3-319-28472-9
eBook Packages: Computer ScienceComputer Science (R0)