2026-08-16T23:22:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9793 2024-03-06T10:44:56Z ddc:004 open_access

Selecting a Leader in a Network of Finite State Machines Afek, Yehuda Emek, Yuval Kolikant, Noa stone age model beeping communication scheme leader election k-leader selection randomized finite state machines asynchronous scheduler 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yehuda Afek and Yuval Emek and Noa Kolikant 2018 Is Part Of LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2018.4 urn:nbn:de:0030-drops-97933 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.4 eng https://creativecommons.org/licenses/by/3.0/legalcode