{"ID":2843390,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.08222","arxiv_id":"2511.08222","title":"Gathering in Vertex- and Edge-Transitive Graphs without Multiplicity Detection under Round Robin","abstract":"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.","short_abstract":"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 accomplis...","url_abs":"https://arxiv.org/abs/2511.08222","url_pdf":"https://arxiv.org/pdf/2511.08222v1","authors":"[\"Serafino Cicerone\",\"Alessia Di Fonso\",\"Gabriele Di Stefano\",\"Alfredo Navarra\"]","published":"2025-11-11T13:25:47Z","proceeding":"cs.DC","tasks":"[\"cs.DC\"]","methods":"[]","has_code":false}