摘要：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.
关键词：Cycle; Election; Gathering; Las Vegas; Monte Carlo; Randomized Algorithm
