文章基本信息

标题：Selecting a Leader in a Network of Finite State Machines
本地全文：下载
作者：Yehuda Afek ; Yuval Emek ; Noa Kolikant 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：121
页码：1-17
DOI：10.4230/LIPIcs.DISC.2018.4
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：This paper studies a variant of the leader election problem under the stone age model (Emek and Wattenhofer, PODC 2013) that considers a network of n randomized finite automata with very weak communication capabilities (a multi-frequency asynchronous generalization of the beeping model's communication scheme). Since solving the classic leader election problem is impossible even in more powerful models, we consider a relaxed variant, referred to as k-leader selection, in which a leader should be selected out of at most k initial candidates. Our main contribution is an algorithm that solves k-leader selection for bounded k in the aforementioned stone age model. On (general topology) graphs of diameter D, this algorithm runs in O~(D) time and succeeds with high probability. The assumption that k is bounded turns out to be unavoidable: we prove that if k = omega (1), then no algorithm in this model can solve k-leader selection with a (positive) constant probability.
关键词：stone age model; beeping communication scheme; leader election; k-leader selection; randomized finite state machines; asynchronous scheduler