Gathering and election by mobile robots in a continuous cycle
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.
|Keywords||Cycle, Election, Gathering, Las Vegas, Monte Carlo, Randomized Algorithm|
|Conference||30th International Symposium on Algorithms and Computation, ISAAC 2019|
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