Near-optimal leader election in population protocols on graphs

Alistarh D-A, Rybicki J, Voitovych S. 2022. Near-optimal leader election in population protocols on graphs. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 246–256.

Download
OA 2022_PODC_Alistarh.pdf 1.59 MB

Conference Paper | Published | English

Scopus indexed
Author
Department
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 Θ(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 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 Θ(n3) 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(log2n) states that is at most a factor log n slower. Finally, we show that the constant-state protocol of Beauquier et al. [OPODIS 2013] is at most a factor n log n slower than the fast polynomial-state protocol. Moreover, among constant-state protocols, this protocol has near-optimal average case complexity on dense random graphs.
Publishing Year
Date Published
2022-07-21
Proceedings Title
Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
Acknowledgement
We thank the anonymous reviewers for their helpful comments. We gratefully acknowledge funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML).
Page
246-256
Conference
PODC: Symposium on Principles of Distributed Computing
Conference Location
Salerno, Italy
Conference Date
2022-07-25 – 2022-07-29
IST-REx-ID

Cite this

Alistarh D-A, Rybicki J, Voitovych S. Near-optimal leader election in population protocols on graphs. In: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. ; 2022:246-256. doi:10.1145/3519270.3538435
Alistarh, D.-A., Rybicki, J., & Voitovych, S. (2022). Near-optimal leader election in population protocols on graphs. In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing (pp. 246–256). Salerno, Italy. https://doi.org/10.1145/3519270.3538435
Alistarh, Dan-Adrian, Joel Rybicki, and Sasha Voitovych. “Near-Optimal Leader Election in Population Protocols on Graphs.” In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, 246–56, 2022. https://doi.org/10.1145/3519270.3538435.
D.-A. Alistarh, J. Rybicki, and S. Voitovych, “Near-optimal leader election in population protocols on graphs,” in Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Salerno, Italy, 2022, pp. 246–256.
Alistarh D-A, Rybicki J, Voitovych S. 2022. Near-optimal leader election in population protocols on graphs. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 246–256.
Alistarh, Dan-Adrian, et al. “Near-Optimal Leader Election in Population Protocols on Graphs.” Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, 2022, pp. 246–56, doi:10.1145/3519270.3538435.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2022-08-16
MD5 Checksum
4c6b29172b8e355b4fbc364a2e0827b2


Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2205.12597

Search this title in

Google Scholar
ISBN Search