Document Open Access Logo

Asynchronous Gathering in a Torus

Authors Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, Sébastien Tixeuil, Koichi Wada

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2021.9.pdf
  • Filesize: 1.09 MB
  • 17 pages

Document Identifiers

Author Details

Sayaka Kamei
  • Hiroshima University, Japan
Anissa Lamani
  • Strasbourg University, CNRS, ICUBE, France
Fukuhito Ooshita
  • Nara Institute of Science and Technology, Japan
Sébastien Tixeuil
  • Sorbonne University, CNRS, LIP6, France
Koichi Wada
  • Hosei University, Tokyo, Japan

Funding

This work was partially funded by the ANR project ESTATE, ref. ANR-16-CE25-0009-03, the ANR project SAPPORO, ref. 2019-CE25-0005-1, JSPS KAKENHI No. 19K11828, 20H04140, 20K11685, and 21K11748, and by JST SICORP (Grant#JPMJSC1806).

Cite AsGet BibTex

Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, Sébastien Tixeuil, and Koichi Wada. Asynchronous Gathering in a Torus. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.OPODIS.2021.9

Abstract

We consider the gathering problem for asynchronous and oblivious robots that cannot communicate explicitly with each other but are endowed with visibility sensors that allow them to see the positions of the other robots. Most investigations on the gathering problem on the discrete universe are done on ring shaped networks due to the number of symmetric configurations. We extend in this paper the study of the gathering problem on torus shaped networks assuming robots endowed with local weak multiplicity detection. That is, robots cannot make the difference between nodes occupied by only one robot from those occupied by more than one robot unless it is their current node. Consequently, solutions based on creating a single multiplicity node as a landmark for the gathering cannot be used. We present in this paper a deterministic algorithm that solves the gathering problem starting from any rigid configuration on an asymmetric unoriented torus shaped network.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Autonomous distributed systems
  • Robots gathering
  • Torus

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. François Bonnet, Maria Potop-Butucaru, and Sébastien Tixeuil. Asynchronous gathering in rings with 4 robots. In Ad-hoc, Mobile, and Wireless Networks - 15th International Conference, ADHOC-NOW 2016, Lille, France, July 4-6, 2016, Proceedings, volume 9724 of Lecture Notes in Computer Science, pages 311-324. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-40509-4_22.
  2. Kaustav Bose, Manash Kumar Kundu, Ranendu Adhikary, and Buddhadeb Sau. Optimal gathering by asynchronous oblivious robots in hypercubes. In Algorithms for Sensor Systems - 14th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2018, Helsinki, Finland, August 23-24, 2018, Revised Selected Papers, volume 11410 of Lecture Notes in Computer Science, pages 102-117. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-14094-6_7.
  3. Jannik Castenow, Matthias Fischer, Jonas Harbig, Daniel Jung, and Friedhelm Meyer auf der Heide. Gathering anonymous, oblivious robots on a grid. Theoretical Computer Science, 815:289-309, 2020. URL: https://doi.org/10.1016/j.tcs.2020.02.018.
  4. Serafino Cicerone, Gabriele Di Stefano, and Alfredo Navarra. Asynchronous robots on graphs: Gathering. In Distributed Computing by Mobile Entities, Current Research in Moving and Computing, volume 11340 of Lecture Notes in Computer Science, pages 184-217. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-11072-7_8.
  5. Serafino Cicerone, Gabriele Di Stefano, and Alfredo Navarra. Gathering robots in graphs: The central role of synchronicity. Theoretical Computer Science, 849:99-120, 2021. URL: https://doi.org/10.1016/j.tcs.2020.10.011.
  6. Gianlorenzo D'Angelo, Alfredo Navarra, and Nicolas Nisse. A unified approach for gathering and exclusive searching on rings under weak assumptions. Distributed Computing, 30(1):17-48, 2017. URL: https://doi.org/10.1007/s00446-016-0274-y.
  7. Gianlorenzo D'Angelo, Gabriele Di Stefano, Ralf Klasing, and Alfredo Navarra. Gathering of robots on anonymous grids and trees without multiplicity detection. Theoretical Computer Science, 610:158-168, 2016. URL: https://doi.org/10.1016/j.tcs.2014.06.045.
  8. Shantanu Das, Nikos Giachoudis, Flaminia L. Luccio, and Euripides Markou. Gathering of robots in a grid with mobile faults. In SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 27-30, 2019, Proceedings, volume 11376 of Lecture Notes in Computer Science, pages 164-178. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-10801-4_14.
  9. Stéphane Devismes, Anissa Lamani, Franck Petit, and Sébastien Tixeuil. Optimal torus exploration by oblivious robots. Computing, 101(9):1241-1264, 2019. URL: https://doi.org/10.1007/s00607-018-0595-8.
  10. Durjoy Dutta, Tandrima Dey, and Sruti Gan Chaudhuri. Gathering multiple robots in a ring and an infinite grid. In Distributed Computing and Internet Technology - 13th International Conference, ICDCIT 2017, Bhubaneswar, India, January 13-16, 2017, Proceedings, volume 10109 of Lecture Notes in Computer Science, pages 15-26. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-50472-8_2.
  11. Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro, editors. Distributed Computing by Mobile Entities, Current Research in Moving and Computing, volume 11340 of Lecture Notes in Computer Science. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-11072-7.
  12. Samuel Guilbault and Andrzej Pelc. Gathering asynchronous oblivious agents with local vision in regular bipartite graphs. Theoretical Computer Science, 509:86-96, 2013. URL: https://doi.org/10.1016/j.tcs.2012.07.004.
  13. David Ilcinkas. Oblivious robots on graphs: Exploration. In Distributed Computing by Mobile Entities, Current Research in Moving and Computing, volume 11340 of Lecture Notes in Computer Science, pages 218-233. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-11072-7_9.
  14. Tomoko Izumi, Taisuke Izumi, Sayaka Kamei, and Fukuhito Ooshita. Time-optimal gathering algorithm of mobile robots with local weak multiplicity detection in rings. IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, 96-A(6):1072-1080, 2013. URL: https://doi.org/10.1587/transfun.E96.A.1072.
  15. Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, and Sébastien Tixeuil. Gathering an even number of robots in an odd ring without global multiplicity detection. In Mathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings, volume 7464 of Lecture Notes in Computer Science, pages 542-553. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-32589-2_48.
  16. Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, Sébastien Tixeuil, and Koichi Wada. Gathering on rings for myopic asynchronous robots with lights. In 23rd International Conference on Principles of Distributed Systems, OPODIS 2019, December 17-19, 2019, Neuchâtel, Switzerland, volume 153 of LIPIcs, pages 27:1-27:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2019.27.
  17. Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, Sébastien Tixeuil, and Koichi Wada. Asynchronous gathering in a torus. CoRR, abs/2101.05421, 2021. URL: http://arxiv.org/abs/2101.05421.
  18. Ralf Klasing, Adrian Kosowski, and Alfredo Navarra. Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring. Theoretical Computer Science, 411(34-36):3235-3246, 2010. URL: https://doi.org/10.1016/j.tcs.2010.05.020.
  19. Laure Millet, Maria Potop-Butucaru, Nathalie Sznajder, and Sébastien Tixeuil. On the synthesis of mobile robots algorithms: The case of ring gathering. In Stabilization, Safety, and Security of Distributed Systems - 16th International Symposium, SSS 2014, Paderborn, Germany, September 28 - October 1, 2014. Proceedings, volume 8756 of Lecture Notes in Computer Science, pages 237-251. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-11764-5_17.
  20. Gabriele Di Stefano and Alfredo Navarra. Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings. Distributed Computing, 30(2):75-86, 2017. URL: https://doi.org/10.1007/s00446-016-0278-7.
  21. Ichiro Suzuki and Masafumi Yamashita. Distributed anonymous mobile robots: Formation of geometric patterns. SIAM Journal on Computing, 28(4):1347-1363, 1999. URL: https://doi.org/10.1137/S009753979628292X.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact