Abstract
We consider a swarm of mobile robots evolving in a bidimensional Euclidean space. We study the stronger variant of crash-tolerant gathering: if no robot crashes, robots have to meet at the same arbitrary location, not known beforehand, in finite time; if one or several robots crash at the same location, the remaining correct robots gather at the crash location to rescue them. Motivated by impossibility results in the semi-synchronous setting, we present the first solution to the problem for the fully synchronous setting that operates in the vanilla Look-Compute-Move model with no additional hypotheses: robots are oblivious, disoriented, have no multiplicity detection capacity, and may start from arbitrary positions (including those with multiplicity points). We furthermore show that robots gather in a time that is proportional to the initial maximum distance between robots.
This work was partially funded by the ANR project SAPPORO, ref. 2019-CE25-0005-1.
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
Similar content being viewed by others
Notes
- 1.
A configuration is bivalent if all robots are evenly spread on exactly two distinct locations.
References
Agmon, N., Peleg, D.: Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM J. Comput. 36(1), 56–82 (2006)
Balabonski, T., Delga, A., Rieg, L., Tixeuil, S., Urbain, X.: Synchronous gathering without multiplicity detection: a certified algorithm. Theory Comput. Syst. 63(2), 200–218 (2019)
Bhagat, S., Gan Chaudhuri, S., Mukhopadhyaya, K.: Fault-tolerant gathering of asynchronous oblivious mobile robots under one-axis agreement. In: Rahman, M.S., Tomita, E. (eds.) WALCOM 2015. LNCS, vol. 8973, pp. 149–160. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-15612-5_14
Bouzid, Z., Das, S., Tixeuil, S.: Gathering of mobile robots tolerating multiple crash faults. In: Proceedings of 33rd IEEE International Conference on Distributed Computing Systems (ICDCS), pp. 337–346, July 2013
Bramas, Q., Lamani, A., Tixeuil, S.: Stand up indulgent rendezvous. In: Devismes, S., Mittal, N. (eds.) SSS 2020. LNCS, vol. 12514, pp. 45–59. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64348-5_4
Bramas, Q., Tixeuil, S.: Wait-free gathering without chirality. In: Scheideler, C. (ed.) SIROCCO 2014. LNCS, vol. 9439, pp. 313–327. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-25258-2_22
Cohen, R., Peleg, D.: Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM J. Comput. 34(6), 1516–1528 (2005)
Courtieu, P., Rieg, L., Tixeuil, S., Urbain, X.: Impossibility of gathering, a certification. Inf. Process. Lett. 115(3), 447–452 (2015)
Défago, X., Gradinariu, M., Messika, S., Raipin-Parvédy, P.: Fault-tolerant and self-stabilizing mobile robots gathering. In: Dolev, S. (ed.) DISC 2006. LNCS, vol. 4167, pp. 46–60. Springer, Heidelberg (2006). https://doi.org/10.1007/11864219_4
Défago, X., Potop-Butucaru, M., Parvédy, P.R.: Self-stabilizing gathering of mobile robots under crash or byzantine faults. Distrib. Comput. 33(5), 393–421 (2020)
Dolev, S.: Self-stabilization. MIT Press, Cambridge (2000)
Flocchini, P., Prencipe, G., Santoro, N. (eds.): Distributed Computing by Mobile Entities-Current Research in Moving and Computing. Lecture Notes in Computer Science, vol. 11340. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-11072-7
Prencipe, G.: Impossibility of gathering by a set of autonomous mobile robots. Theor. Comput. Sci. 384(2–3), 222–231 (2007)
Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347–1363 (1999)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Bramas, Q., Lamani, A., Tixeuil, S. (2021). Stand up Indulgent Gathering. In: Gąsieniec, L., Klasing, R., Radzik, T. (eds) Algorithms for Sensor Systems. ALGOSENSORS 2021. Lecture Notes in Computer Science(), vol 12961. Springer, Cham. https://doi.org/10.1007/978-3-030-89240-1_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-89240-1_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-89239-5
Online ISBN: 978-3-030-89240-1
eBook Packages: Computer ScienceComputer Science (R0)