2018/05/15 by Yehuda Afek, Afek, Yehuda, Yuval Emek +3
Computer Science · #Algorithm #Computability, Logic, AI Algorithms #Computer science #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Finite-state machine #Parallel #Quantum Computing Algorithms and Architecture #State (computer science) #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.1805.05660
published in arXiv (Cornell University) (Cornell University) · To appear in DISC 2018
openalex publication_date 2018/05/15 · arxiv created 2018/07/24 · arxiv updated 2018/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 = ω(1), then no algorithm in this model can solve k-leader selection with a (positive) constant probability.