License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2021.9
URN: urn:nbn:de:0030-drops-157845
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15784/
Go to the corresponding LIPIcs Volume Portal

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

Asynchronous Gathering in a Torus

pdf-format:
LIPIcs-OPODIS-2021-9.pdf (1 MB)

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.

BibTeX - Entry

@InProceedings{kamei_et_al:LIPIcs.OPODIS.2021.9,
  author =	{Kamei, Sayaka and Lamani, Anissa and Ooshita, Fukuhito and Tixeuil, S\'{e}bastien and Wada, Koichi},
  title =	{{Asynchronous Gathering in a Torus}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15784},
  URN =		{urn:nbn:de:0030-drops-157845},
  doi =		{10.4230/LIPIcs.OPODIS.2021.9},
  annote =	{Keywords: Autonomous distributed systems, Robots gathering, Torus}
}

Keywords: Autonomous distributed systems, Robots gathering, Torus
Collection: 25th International Conference on Principles of Distributed Systems (OPODIS 2021)
Issue Date: 2022
Date of publication: 28.02.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI