Abstract
The gathering of two or more agents in a graph is an important problem in the area of distributed computing and has been extensively studied especially for the fault free scenario. In this paper we consider the mobile agents gathering problem in the presence of an adversarial malicious agent which by occupying an empty node might prevent honest agents from entering this node. The honest agents move in synchronous rounds and at each round an agent can move to an adjacent node only if this node is not occupied by the malicious agent. We model the honest agents as identical finite state automata moving in an anonymous oriented grid topology and having no information about the size of the graph, while the malicious agent is assumed to be arbitrarily fast and to have full knowledge of the locations and the strategy of the honest agents at all times. The agents cannot leave messages at nodes or communicate with each-other unless they meet at a node. Previous studies consider the problem for ring networks and for asynchronous grids, where rendezvous was solved only for the special case of agents starting already in connected configurations. In this paper, we study the problem for synchronous agents in anonymous oriented grid networks for any number of agents starting in distinct locations. We first show that rendezvous is impossible for 2 agents even when the agents can see the locations of each-other at all times, while 3 agents can gather if they have global visibility. We then present a universal deterministic algorithm that solves the problem for 4 or more agents having only local visibility and constant memory, in any oriented grid with a malicious mobile adversary.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsNotes
- 1.
We notice that since an agent has only constant memory, it cannot simultaneously store in its memory the states of more than a constant number of agents.
- 2.
We remind the reader, that as we have noticed in the beginning of the section, the agents can assign to themselves distinct identities and therefore they can perform distinct moves.
References
Agmon, N., Peleg, D.: Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM J. Comput. 36(1), 56–82 (2006)
Bampas, E., Leonardos, N., Markou, E., Pagourtzis, A., Petrolia, M.: Improved periodic data retrieval in asynchronous rings with a faulty host. Theoret. Comput. Sci. 608, 231–254 (2015)
Bouzid, Z., Das, S., Tixeuil, S.: Gathering of mobile robots tolerating multiple crash faults. In: ICDCS 2013, pp. 337–346 (2013)
Chalopin, J., Dieudonne, Y., Labourel, A., Pelc, A.: Rendezvous in networks in spite of delay faults. Distrib. Comput. 29, 187–205 (2016)
Chuangpishit, H., Czyzowicz, J., Kranakis, E., Krizanc, D.: Rendezvous on a line by location-aware robots despite the presence of byzantine faults. In: Fernández Anta, A., Jurdzinski, T., Mosteiro, M.A., Zhang, Y. (eds.) ALGOSENSORS 2017. LNCS, vol. 10718, pp. 70–83. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-72751-6_6
Czyzowicz, J., Killick, R., Kranakis, E., Krizanc, D., Morale-Ponce, O.: Gathering in the plane of location-aware robots in the presence of spies. In: Lotker, Z., Patt-Shamir, B. (eds.) SIROCCO 2018, pp. 361–376. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-01325-7_30
Das, S., Focardi, R., Luccio, F.L., Markou, E., Moro, D., Squarcina, M.: Gathering of robots in a ring with mobile faults. In: 17th Italian Conference on Theoretical Computer Science (ICTCS 2016), Lecce, Italy. CEUR, vol. 1720, pp. 122–135, 7–9 September 2016
Das, S., Focardi, R., Luccio, F.L., Markou, E., Squarcina, M.: Gathering of robots in a ring with mobile faults. Theor. Comput. Sci. (in press). https://doi.org/10.1016/j.tcs.2018.05.002
Das, S., Luccio, F.L., Markou, E.: Mobile agents rendezvous in spite of a malicious agent. In: Bose, P., Gąsieniec, L.A., Römer, K., Wattenhofer, R. (eds.) ALGOSENSORS 2015. LNCS, vol. 9536, pp. 211–224. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-28472-9_16
Di Luna, G.A., Flocchini, P., Pagli, L., Prencipe, G., Santoro, N., Viglietta, G.: Gathering in dynamic rings. Theor. Comput. Sci. (in press). http://www.sciencedirect.com/science/article/pii/S030439751830639X
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). https://doi.org/10.1007/978-3-540-27860-3_6
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., Santoro, N.: Distributed security algorithms for mobile agents. In: Cao, J., Das, S.K. (eds.) Mobile Agents in Networking and Distributed Computing, pp. 41–70. Wiley, Hoboken (2012). Chap. 3
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)
Lin, J., Morse, A.S., Anderson, B.D.O.: The multi-agent rendezvous problem. An extended summary. In: Kumar, V., Leonard, N., Morse, A.S. (eds.) Cooperative Control, vol. 309, pp. 257–289. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-31595-7_15
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)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Das, S., Giachoudis, N., Luccio, F.L., Markou, E. (2019). Gathering of Robots in a Grid with Mobile Faults. In: Catania, B., Královič, R., Nawrocki, J., Pighizzini, G. (eds) SOFSEM 2019: Theory and Practice of Computer Science. SOFSEM 2019. Lecture Notes in Computer Science(), vol 11376. Springer, Cham. https://doi.org/10.1007/978-3-030-10801-4_14
Download citation
DOI: https://doi.org/10.1007/978-3-030-10801-4_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-10800-7
Online ISBN: 978-3-030-10801-4
eBook Packages: Computer ScienceComputer Science (R0)