Gathering in Vertex- and Edge-Transitive Graphs without Multiplicity Detection under Round Robin
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909898225221632 |
|---|---|
| author | Cicerone, Serafino Di Fonso, Alessia Di Stefano, Gabriele Navarra, Alfredo |
| author_facet | Cicerone, Serafino Di Fonso, Alessia Di Stefano, Gabriele Navarra, Alfredo |
| contents | In the field of swarm robotics, one of the most studied problem is Gathering. It asks for a distributed algorithm that brings the robots to a common location, not known in advance. We consider the case of robots constrained to move along the edges of a graph under the well-known OBLOT model. Gathering is then accomplished once all the robots occupy a same vertex. Differently from classical settings, we assume: i) the initial configuration may contain multiplicities, i.e. more than one robot may occupy the same vertex; ii) robots cannot detect multiplicities; iii) robots move along the edges of vertex- and edge-transitive graphs, i.e. graphs where all the vertices (and the edges, resp.) belong to a same class of equivalence. To balance somehow such a `hostile' setting, as a scheduler for the activation of the robots, we consider the round-robin, where robots are cyclically activated one at a time.
We provide some basic impossibility results and we design two different algorithms approaching the Gathering for robots moving on two specific topologies belonging to edge- and vertex-transitive graphs: infinite grids and hypercubes. The two algorithms are both time-optimal and heavily exploit the properties of the underlying topologies. Because of this, we conjecture that no general algorithm can exist for all the solvable cases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_08222 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Gathering in Vertex- and Edge-Transitive Graphs without Multiplicity Detection under Round Robin Cicerone, Serafino Di Fonso, Alessia Di Stefano, Gabriele Navarra, Alfredo Distributed, Parallel, and Cluster Computing In the field of swarm robotics, one of the most studied problem is Gathering. It asks for a distributed algorithm that brings the robots to a common location, not known in advance. We consider the case of robots constrained to move along the edges of a graph under the well-known OBLOT model. Gathering is then accomplished once all the robots occupy a same vertex. Differently from classical settings, we assume: i) the initial configuration may contain multiplicities, i.e. more than one robot may occupy the same vertex; ii) robots cannot detect multiplicities; iii) robots move along the edges of vertex- and edge-transitive graphs, i.e. graphs where all the vertices (and the edges, resp.) belong to a same class of equivalence. To balance somehow such a `hostile' setting, as a scheduler for the activation of the robots, we consider the round-robin, where robots are cyclically activated one at a time. We provide some basic impossibility results and we design two different algorithms approaching the Gathering for robots moving on two specific topologies belonging to edge- and vertex-transitive graphs: infinite grids and hypercubes. The two algorithms are both time-optimal and heavily exploit the properties of the underlying topologies. Because of this, we conjecture that no general algorithm can exist for all the solvable cases. |
| title | Gathering in Vertex- and Edge-Transitive Graphs without Multiplicity Detection under Round Robin |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2511.08222 |