2026-07-22T13:39:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11504 2024-03-06T10:48:10Z ddc:004 open_access

Gathering and Election by Mobile Robots in a Continuous Cycle Flocchini, Paola Killick, Ryan Kranakis, Evangelos Santoro, Nicola Yamashita, Masafumi Cycle Election Gathering Las Vegas Monte Carlo Randomized Algorithm Consider a set of n mobile computational entities, called robots, located and operating on a continuous cycle C (e.g., the perimeter of a closed region of R^2) of arbitrary length l. The robots are identical, can only see their current location, have no location awareness, and cannot communicate at a distance. In this weak setting, we study the classical problems of gathering (GATHER), requiring all robots to meet at a same location; and election (ELECT), requiring all robots to agree on a single one as the "leader". We investigate how to solve the problems depending on the amount of knowledge (exact, upper bound, none) the robots have about their number n and about the length of the cycle l. Cost of the algorithms is analyzed with respect to time and number of random bits. We establish a variety of new results specific to the continuous cycle - a geometric domain never explored before for GATHER and ELECT in a mobile robot setting; compare Monte Carlo and Las Vegas algorithms; and obtain several optimal bounds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paola Flocchini and Ryan Killick and Evangelos Kranakis and Nicola Santoro and Masafumi Yamashita 2019 Is Part Of LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2019.8 urn:nbn:de:0030-drops-115044 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.8 eng https://creativecommons.org/licenses/by/3.0/legalcode