article published yes Dan-Adrian Alistarh author 4A899BFC-F248-11E8-B48F-1D18A9856A870000-0003-3650-940X Joel Rybicki author 334EFD2E-F248-11E8-B48F-1D18A9856A870000-0002-6432-6646 Sasha Voitovych author DaAl department Elastic Coordination for Scalable Machine Learning project 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 (n log n) expected steps using (log log n) states, whereas protocols that use O(1) states require (n2) expected steps. In this work, we investigate the complexity of stable leader election on graphs. We provide the first non-trivial time lower bounds on general graphs, showing that, when moving beyond cliques, the complexity of stable leader election can range from O(1) to (n3) expected steps. We describe 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(log2 n) states that is at most a factor O(log n) slower. Finally, we observe that for many graphs the constant-state protocol of Beauquier et al. [OPODIS 2013] is at most a factor O(n log n) slower than the fast polynomial-state protocol, and among constant-state protocols, this protocol has near-optimal average case complexity on dense random graphs. https://research-explorer.ista.ac.at/download/19969/20900/2025_DistributedComp_Alistarh.pdf application/pdfno https://creativecommons.org/licenses/by/4.0/ Springer Nature2025 eng 0178-2770 1432-0452 2205.12597 00151830040000110.1007/s00446-025-00487-7 38207-245 https://research-explorer.ista.ac.at/record/11844 Alistarh, Dan-Adrian, et al. “Near-Optimal Leader Election in Population Protocols on Graphs.” <i>Distributed Computing</i>, vol. 38, Springer Nature, 2025, pp. 207–45, doi:<a href="https://doi.org/10.1007/s00446-025-00487-7">10.1007/s00446-025-00487-7</a>. Alistarh, D.-A., Rybicki, J., &#38; Voitovych, S. (2025). Near-optimal leader election in population protocols on graphs. <i>Distributed Computing</i>. Springer Nature. <a href="https://doi.org/10.1007/s00446-025-00487-7">https://doi.org/10.1007/s00446-025-00487-7</a> Alistarh D-A, Rybicki J, Voitovych S. 2025. Near-optimal leader election in population protocols on graphs. Distributed Computing. 38, 207–245. Alistarh D-A, Rybicki J, Voitovych S. Near-optimal leader election in population protocols on graphs. <i>Distributed Computing</i>. 2025;38:207-245. doi:<a href="https://doi.org/10.1007/s00446-025-00487-7">10.1007/s00446-025-00487-7</a> Alistarh, Dan-Adrian, Joel Rybicki, and Sasha Voitovych. “Near-Optimal Leader Election in Population Protocols on Graphs.” <i>Distributed Computing</i>. Springer Nature, 2025. <a href="https://doi.org/10.1007/s00446-025-00487-7">https://doi.org/10.1007/s00446-025-00487-7</a>. D.-A. Alistarh, J. Rybicki, and S. Voitovych, “Near-optimal leader election in population protocols on graphs,” <i>Distributed Computing</i>, vol. 38. Springer Nature, pp. 207–245, 2025. D.-A. Alistarh, J. Rybicki, S. Voitovych, Distributed Computing 38 (2025) 207–245. 199692025-07-06T22:01:24Z2025-12-30T09:04:18Z