文章基本信息

标题：Gathering and Election by Mobile Robots in a Continuous Cycle
本地全文：下载
作者：Paola Flocchini ; Ryan Killick ; Evangelos Kranakis 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：149
页码：1-19
DOI：10.4230/LIPIcs.ISAAC.2019.8
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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