[{"day":"21","date_published":"2022-07-21T00:00:00Z","fulldoi":"https://doi.org/10.1145/3519270.3538435","file":[{"date_updated":"2022-08-16T08:05:15Z","checksum":"4c6b29172b8e355b4fbc364a2e0827b2","file_size":1593474,"creator":"cchlebak","success":1,"relation":"main_file","date_created":"2022-08-16T08:05:15Z","file_id":"11854","access_level":"open_access","content_type":"application/pdf","file_name":"2022_PODC_Alistarh.pdf"}],"isi":1,"language":[{"iso":"eng"}],"external_id":{"arxiv":["2205.12597"],"isi":["001031439100030"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"conference":{"name":"PODC: Symposium on Principles of Distributed Computing","start_date":"2022-07-25","location":"Salerno, Italy","end_date":"2022-07-29"},"file_date_updated":"2022-08-16T08:05:15Z","abstract":[{"lang":"eng","text":"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.\r\n\r\nIn 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."}],"title":"Near-optimal leader election in population protocols on graphs","date_updated":"2025-12-30T09:04:17Z","license":"https://creativecommons.org/licenses/by/4.0/","page":"246-256","type":"conference","project":[{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","grant_number":"805223"}],"status":"public","_id":"11844","doi":"10.1145/3519270.3538435","publisher":"Association for Computing Machinery","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","ddc":["000"],"publication_status":"published","author":[{"orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh"},{"last_name":"Rybicki","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","first_name":"Joel","orcid":"0000-0002-6432-6646","full_name":"Rybicki, Joel"},{"last_name":"Voitovych","first_name":"Sasha","full_name":"Voitovych, Sasha"}],"oa_version":"Published Version","month":"07","article_processing_charge":"Yes (via OA deal)","year":"2022","oa":1,"publication":"Proceedings of the Annual ACM Symposium on Principles of Distributed Computing","department":[{"_id":"DaAl"}],"scopus_import":"1","date_created":"2022-08-14T22:01:46Z","related_material":{"record":[{"relation":"later_version","status":"public","id":"19969"}]},"has_accepted_license":"1","corr_author":"1","citation":{"ista":"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.","ama":"Alistarh D-A, Rybicki J, Voitovych S. Near-optimal leader election in population protocols on graphs. In: <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2022:246-256. doi:<a href=\"https://doi.org/10.1145/3519270.3538435\">10.1145/3519270.3538435</a>","mla":"Alistarh, Dan-Adrian, et al. “Near-Optimal Leader Election in Population Protocols on Graphs.” <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2022, pp. 246–56, doi:<a href=\"https://doi.org/10.1145/3519270.3538435\">10.1145/3519270.3538435</a>.","short":"D.-A. Alistarh, J. Rybicki, S. Voitovych, in:, Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2022, pp. 246–256.","ieee":"D.-A. Alistarh, J. Rybicki, and S. Voitovych, “Near-optimal leader election in population protocols on graphs,” in <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>, Salerno, Italy, 2022, pp. 246–256.","apa":"Alistarh, D.-A., Rybicki, J., &#38; Voitovych, S. (2022). Near-optimal leader election in population protocols on graphs. In <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i> (pp. 246–256). Salerno, Italy: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3519270.3538435\">https://doi.org/10.1145/3519270.3538435</a>","chicago":"Alistarh, Dan-Adrian, Joel Rybicki, and Sasha Voitovych. “Near-Optimal Leader Election in Population Protocols on Graphs.” In <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>, 246–56. Association for Computing Machinery, 2022. <a href=\"https://doi.org/10.1145/3519270.3538435\">https://doi.org/10.1145/3519270.3538435</a>."},"quality_controlled":"1","arxiv":1,"publication_identifier":{"isbn":["9781450392624"]},"ec_funded":1,"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)."},{"fulldoi":"https://doi.org/10.1145/3519270.3538460","language":[{"iso":"eng"}],"external_id":{"arxiv":["2211.11352"]},"day":"21","date_published":"2022-07-21T00:00:00Z","doi":"10.1145/3519270.3538460","publisher":"Association for Computing Machinery","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","type":"conference","status":"public","_id":"22374","date_updated":"2026-07-24T12:48:29Z","page":"54-56","conference":{"end_date":"2022-07-29","name":"PODC: Symposium on Principles of Distrubuted Computing","start_date":"2022-07-25","location":"Salerno, Italy"},"abstract":[{"lang":"eng","text":"We study the broadcast problem on dynamic networks with n processes. The processes communicate in synchronous rounds along an arbitrary rooted tree. The sequence of trees is given by an adversary whose goal is to maximize the number of rounds until at least one process reaches all other processes. Previous research has shown a ⌈(3n-1)/(2)⌉-2 lower bound and an O(n log log n) upper bound. We show the first linear upper bound for this problem, namely ⌈(1 + √2) n-1⌉ ~2.4n. Our result follows from a detailed analysis of the evolution of the adjacency matrix of the network over time."}],"title":"Brief announcement: Broadcasting time in dynamic rooted trees is linear","article_processing_charge":"No","oa":1,"year":"2022","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1145/3519270.3538460"}],"oa_version":"Published Version","month":"07","publication_status":"published","author":[{"last_name":"El-Hayek","id":"888a098e-fcac-11ee-aff7-d347be57b725","full_name":"El-Hayek, Antoine","orcid":"0000-0003-4268-7368","first_name":"Antoine"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"}],"acknowledgement":"This project has received funding from the European Research\r\nCouncil (ERC) under the European Union’s Horizon 2020 research\r\nand innovation programme (grant agreement No. 101019564). This\r\nwork was further supported by the Austrian Science Fund (FWF)\r\nand netIDEE SCIENCE project P 33775-N, and by the Federal Ministry of Education and Research (BMBF, Germany), 6G-RIC under\r\nGrant 16KISK020K. We would like to thank Kyrill Winkler for his\r\ninputs and feedback on this paper.\r\n","OA_type":"green","arxiv":1,"quality_controlled":"1","OA_place":"publisher","publication_identifier":{"isbn":["9781450392624"]},"extern":"1","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"22281"}]},"citation":{"short":"A. El-Hayek, M. Henzinger, S. Schmid, in:, Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2022, pp. 54–56.","ieee":"A. El-Hayek, M. Henzinger, and S. Schmid, “Brief announcement: Broadcasting time in dynamic rooted trees is linear,” in <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Salerno, Italy, 2022, pp. 54–56.","apa":"El-Hayek, A., Henzinger, M., &#38; Schmid, S. (2022). Brief announcement: Broadcasting time in dynamic rooted trees is linear. In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i> (pp. 54–56). Salerno, Italy: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3519270.3538460\">https://doi.org/10.1145/3519270.3538460</a>","chicago":"El-Hayek, Antoine, Monika Henzinger, and Stefan Schmid. “Brief Announcement: Broadcasting Time in Dynamic Rooted Trees Is Linear.” In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, 54–56. Association for Computing Machinery, 2022. <a href=\"https://doi.org/10.1145/3519270.3538460\">https://doi.org/10.1145/3519270.3538460</a>.","ista":"El-Hayek A, Henzinger M, Schmid S. 2022. Brief announcement: Broadcasting time in dynamic rooted trees is linear. Proceedings of the ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distrubuted Computing, 54–56.","ama":"El-Hayek A, Henzinger M, Schmid S. Brief announcement: Broadcasting time in dynamic rooted trees is linear. In: <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2022:54-56. doi:<a href=\"https://doi.org/10.1145/3519270.3538460\">10.1145/3519270.3538460</a>","mla":"El-Hayek, Antoine, et al. “Brief Announcement: Broadcasting Time in Dynamic Rooted Trees Is Linear.” <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2022, pp. 54–56, doi:<a href=\"https://doi.org/10.1145/3519270.3538460\">10.1145/3519270.3538460</a>."},"publication":"Proceedings of the ACM Symposium on Principles of Distributed Computing","scopus_import":"1","date_created":"2026-07-20T11:46:26Z"}]