Near-Optimal Leader Election in Population Protocols on Graphs

DOI10.1145/3519270.3538435MaRDI QIDQ6202165zbMATH OpenFDO

Authors Dan Alistarh, Joel Rybicki

Publication date 26 March 2024

Published in Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.12597

zbMATH Keywords

graph algorithmsleader electionlower boundspopulation protocolsrandomized algorithms

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: In the stochastic population protocol model, we are given a connected graph with $n$ nodes, and in every time step, a scheduler samples an edge of the graph uniformly at random and the nodes connected by this edge interact. A fundamental task in this model is stable leader election, in which all nodes start in an identical state and the aim is to reach a configuration in which (1) exactly one node is elected as leader and (2) this node remains as the unique leader no matter what sequence of interactions follows. On cliques, the complexity of this problem has recently been settled: time-optimal protocols stabilize in $Theta(nlogn)$ expected steps using $Theta(loglogn)$ states, whereas protocols that use $O(1)$ states require $Theta(n^2)$ expected steps. In this work, we investigate the complexity of stable leader election on general graphs. We provide the first non-trivial time lower bounds for leader election on general graphs, showing that, when moving beyond cliques, the complexity landscape of leader election becomes very diverse: the time required to elect a leader can range from $O(1)$ to $Theta(n^3)$ expected steps. On the upper bound side, we first observe that there exists a protocol that is time-optimal on many graph families, but uses polynomially-many states. In contrast, we give a near-time-optimal protocol that uses only $O(lo{g}^{2}n)$ states that is at most a factor $logn$ slower. Finally, we show that the constant-state protocol of Beauquier et al. [OPODIS 2013] is at most a factor $nlogn$ slower than the fast polynomial-state protocol. Moreover, among constant-state protocols, this protocol has near-optimal average case complexity on dense random graphs.

Cited in

(2)

• Near-optimal leader election in population protocols on graphs
• Complete graph identification in population protocols

This page was built for publication: Near-Optimal Leader Election in Population Protocols on Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202165)