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 R2) of arbitrary length `. 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 `. 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.

Cycle, Election, Gathering, Las Vegas, Monte Carlo, Randomized Algorithm
30th International Symposium on Algorithms and Computation, ISAAC 2019
School of Computer Science

Flocchini, P. (Paola), Killick, R. (Ryan), Kranakis, E, Santoro, N, & Yamashita, M. (Masafumi). (2019). Gathering and election by mobile robots in a continuous cycle. In Leibniz International Proceedings in Informatics, LIPIcs. doi:10.4230/LIPIcs.ISAAC.2019.8