×

Stand-up indulgent gathering on lines. (English) Zbl 07921856

Summary: We consider a variant of the crash-fault gathering problem called stand-up indulgent gathering (SUIG). In this problem, a group of mobile robots must eventually gather at a single location, which is not known in advance. If no robots crash, they must all meet at the same location. However, if one or more robots crash at a single location, all non-crashed robots must eventually gather at that location. The SUIG problem was first introduced for robots operating in a two-dimensional continuous Euclidean space, with most solutions relying on the ability of robots to move a prescribed (real) distance at each time instant. In this paper, we investigate the SUIG problem for robots operating in a discrete universe (i.e., a graph) where they can only move one unit of distance (i.e., to an adjacent node) at each time instant. Specifically, we focus on line-shaped networks and characterize the solvability of the SUIG problem for oblivious robots without multiplicity detection.

MSC:

68Qxx Theory of computing

References:

[1] Bramas, Q.; Kamei, S.; Lamani, A.; Tixeuil, S., Stand-up indulgent gathering on lines, (Dolev, S.; Schieber, B., Stabilization, Safety, and Security of Distributed Systems (SSS). Stabilization, Safety, and Security of Distributed Systems (SSS), Lecture Notes in Computer Science, vol. 14310, 2023, Springer), 451-465
[2] (Flocchini, P.; Prencipe, G.; Santoro, N., Distributed Computing by Mobile Entities, Current Researchin Moving and Computing. Distributed Computing by Mobile Entities, Current Researchin Moving and Computing, Lecture Notes in Computer Science, vol. 11340, 2019, Springer)
[3] Suzuki, I.; Yamashita, M., Distributed anonymous mobile robots: formation of geometric patterns, SIAM J. Comput., 28, 4, 1347-1363, 1999 · Zbl 0940.68145
[4] Agmon, N.; Peleg, D., Fault-tolerant gathering algorithms for autonomous mobile robots, SIAM J. Comput., 36, 1, 56-82, 2006 · Zbl 1111.68136
[5] Bouzid, Z.; Das, S.; Tixeuil, S., Gathering of mobile robots tolerating multiple crash faults, (IEEE 33rd International Conference on Distributed Computing Systems (ICDCS), 2013), 337-346
[6] Bramas, Q.; Tixeuil, S., Wait-free gathering without chirality, (22nd Structural Information and Communication Complexity (SIROCCO). 22nd Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science, vol. 9439, 2015), 313-327 · Zbl 1471.68028
[7] Défago, X.; Potop-Butucaru, M.; Raipin-Parvédy, P., Self-stabilizing gathering of mobile robots under crash or byzantine faults, Distrib. Comput., 33, 393-421, 2020 · Zbl 1460.68015
[8] Bramas, Q.; Lamani, A.; Tixeuil, S., Stand up indulgent rendezvous, (Stabilization, Safety, and Security of Distributed Systems. Stabilization, Safety, and Security of Distributed Systems, SSS 2020. Stabilization, Safety, and Security of Distributed Systems. Stabilization, Safety, and Security of Distributed Systems, SSS 2020, Lecture Notes in Computer Science, 2020), 45-59 · Zbl 1518.68398
[9] Bramas, Q.; Lamani, A.; Tixeuil, S., Stand up indulgent gathering, (Algorithms for Sensor Systems. ALGOSENSORS 2021. Algorithms for Sensor Systems. ALGOSENSORS 2021, Lecture Notes in Computer Science, vol. 12961, 2021), 17-28 · Zbl 1498.68327
[10] Balabonski, T.; Courtieu, P.; Pelle, R.; Rieg, L.; Tixeuil, S.; Urbain, X., Continuous vs. discrete asynchronous moves: a certified approach for mobile robots, (Networked Systems - 7th International Conference. Networked Systems - 7th International Conference, NETYS 2019, Marrakech, Morocco, June 19-21, 2019, vol. 11704, 2019, Springer), 93-109, Revised Selected Papers
[11] Klasing, R.; Markou, E.; Pelc, A., Gathering asynchronous oblivious mobile robots in a ring, Theor. Comput. Sci., 390, 1, 27-39, 2008 · Zbl 1134.68013
[12] Klasing, R.; Kosowski, A.; Navarra, A., Taking advantage of symmetries: gathering of many asynchronous oblivious robots on a ring, Theor. Comput. Sci., 411, 34-36, 3235-3246, 2010 · Zbl 1195.68099
[13] Kamei, S.; Lamani, A.; Ooshita, F.; Tixeuil, S., Asynchronous mobile robot gathering from symmetric configurations without global multiplicity detection, (Structural Information and Communication Complexity. Structural Information and Communication Complexity, SIROCCO 2011. Structural Information and Communication Complexity. Structural Information and Communication Complexity, SIROCCO 2011, Lecture Notes in Computer Science, vol. 6796, 2011), 150-161
[14] Kamei, S.; Lamani, A.; Ooshita, F.; Tixeuil, S., Gathering an even number of robots in an odd ring without global multiplicity detection, (Mathematical Foundations of Computer Science 2012. Mathematical Foundations of Computer Science 2012, MFCS 2012. Mathematical Foundations of Computer Science 2012. Mathematical Foundations of Computer Science 2012, MFCS 2012, Lecture Notes in Computer Science, vol. 7464, 2012), 542-553 · Zbl 1365.68421
[15] Izumi, T.; Izumi, T.; Kamei, S.; Ooshita, F., Time-optimal gathering algorithm of mobile robots with local weak multiplicity detection in rings, IEICE Trans., 96-A, 6, 1072-1080, 2013
[16] D’Angelo, G.; Stefano, G. D.; Navarra, Alfredo, Gathering on rings under the look-compute-move model, Distrib. Comput., 27, 4, 255-285, 2014 · Zbl 1320.68046
[17] D’Angelo, G.; Navarra, A.; Nisse, N., A unified approach for gathering and exclusive searching on rings under weak assumptions, Distrib. Comput., 30, 1, 17-48, 2017 · Zbl 1404.68018
[18] D’Angelo, G.; Stefano, G. D.; Klasing, R.; Navarra, A., Gathering of robots on anonymous grids and trees without multiplicity detection, Theor. Comput. Sci., 610, 158-168, 2016 · Zbl 1332.68167
[19] Kamei, S.; Lamani, A.; Ooshita, F.; Tixeuil, S.; Wada, K., Asynchronous gathering in a torus, (25th International Conference on Principles of Distributed Systems (OPODIS 2021), vol. 217, 2021), Article 9 pp.
[20] Cicerone, S.; DiStefano, G.; Navarra, A., Gathering robots in graphs: the central role of synchronicity, Theor. Comput. Sci., 849, 99-120, 2021 · Zbl 1464.68440
[21] Castenow, J.; Fischer, M.; Harbig, J.; Jung, D.; auf der Heide, F. M., Gathering anonymous, oblivious robots on a grid, Theor. Comput. Sci., 815, 289-309, 2020 · Zbl 1433.68597
[22] Ooshita, F.; Tixeuil, S., On the self-stabilization of mobile oblivious robots in uniform rings, Theor. Comput. Sci., 568, 84-96, 2015 · Zbl 1312.68196
[23] Castaneda, A.; Rajsbaum, S.; Alcántara, M.; Flores-Penaloza, D., Fault-tolerant robot gathering problems on graphs with arbitrary appearing times, (2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2017), 493-502
[24] Bramas, Q.; Kamei, S.; Lamani, A.; Tixeuil, S., Stand-up indulgent gathering on rings, (Structural Information and Communication Complexity - 31st International Colloquium, Proceedings. Structural Information and Communication Complexity - 31st International Colloquium, Proceedings, SIROCCO 2024, Vietri Sul Mare, Salerno, Italy, May 27th - May 29th, 2024. Structural Information and Communication Complexity - 31st International Colloquium, Proceedings. Structural Information and Communication Complexity - 31st International Colloquium, Proceedings, SIROCCO 2024, Vietri Sul Mare, Salerno, Italy, May 27th - May 29th, 2024, Lecture Notes in Computer Science, 2024, Springer), 119-137
[25] Bramas, Q.; Kakugawa, H.; Kamei, S.; Lamani, A.; Ooshita, F.; Shibata, M.; Tixeuil, S., Stand-up indulgent gathering on lines for myopic luminous robots, (Proc. 38th International Conference on Advanced Information Networking and Applications (AINA-2024), 2024), 110-121
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.