Abstract
Censor-Hillel, Cohen, Gelles, and Sela (PODC 2022 & Distributed Computing 2023) studied fully-defective asynchronous networks, where communication channels may suffer an extreme form of alteration errors, rendering messages completely corrupted. The model is equivalent to content-oblivious computation, where nodes communicate solely via pulses. They showed that if the network is 2-edge-connected, then any algorithm for a noiseless setting can be simulated in the fully-defective setting; otherwise, no non-trivial computation is possible in the fully-defective setting. However, their simulation requires a predesignated leader, which they conjectured to be necessary for any non-trivial content-oblivious task. Recently, Frei, Gelles, Ghazy, and Nolin (DISC 2024) refuted this conjecture for the special case of oriented ring topology. They designed two asynchronous content-oblivious leader election algorithms with message complexity \(O(n \cdot \mathsf {ID_{\max }})\), where n is the number of nodes and \(\mathsf {ID_{\max }}\) is the maximum \(\textsf{ID}\). The first algorithm stabilizes in unoriented rings without termination detection. The second algorithm quiescently terminates in oriented rings, thus enabling the execution of the simulation algorithm after leader election. In this work, we present two results:
-
General 2-edge-connected topologies:
First, we show an asynchronous content-oblivious leader election algorithm that quiescently terminates in any 2-edge-connected network with message complexity \(O(m \cdot N \cdot \mathsf {ID_{\min }})\), where m is the number of edges, N is a known upper bound on the number of nodes, and \(\mathsf {ID_{\min }}\) is the smallest \(\textsf{ID}\). Combined with the above simulation, this result shows that whenever a size bound N is known, any noiseless algorithm can be simulated in the fully-defective model without a preselected leader, fully refuting the conjecture.
-
Unoriented rings:
We then show that the knowledge of N can be dropped in unoriented ring topologies by presenting a quiescently terminating election algorithm with message complexity \(O(n \cdot \textsf{ID}_{\max })\) that matches the previous bound. Consequently, this result constitutes a strict improvement over the previous state of the art and shows that, on rings, fully-defective and noiseless communication are computationally equivalent, with no additional assumptions.
Data Availability
No datasets were generated or analysed during the current study.
Notes
An \(\alpha \)-synchronizer is a mechanism for simulating a synchronous distributed algorithm in an asynchronous network. The simulation proceeds in logical rounds: after a node sends all messages for a simulated round, it informs its neighbors that it is safe, and it advances to the next round only after receiving such notifications from all neighbors. This guarantees that every node receives all messages from the current simulated round before starting the next one, thereby preserving the behavior of the original synchronous algorithm.
References
Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18(4), 235–253 (2006)
Alistarh, D., Rybicki, J., Voitovych, S.: Near-optimal leader election in population protocols on graphs. In: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC), pp. 246–256. (2022)
Attiya, H., Welch, J.: Distributed computing: fundamentals, simulations, and advanced topics. John Wiley & Sons, (2004)
Awerbuch, B.: Complexity of network synchronization. J. ACM (JACM) 32(4), 804–823 (1985)
Barborak, M., Dahbura, A., Malek, M.: The consensus problem in fault-tolerant computing. ACM Comput. Surv. (CSur) 25(2), 171–220 (1993)
Berenbrink, P., Giakkoupis, G., Kling, P.: Optimal time and space leader election in population protocols. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 119–129. (2020)
Censor-Hillel, K., Cohen, S., Gelles, R., Sela, G.: Distributed computations in fully-defective networks. Distrib. Comput. 36(4), 501–528 (2023)
Czumaj, A., Davies, P.: Leader election in multi-hop radio networks. Theor. Comput. Sci. 792(C):2–11. (2019). https://doi.org/10.1016/j.tcs.2019.02.027
Czumaj, A., Davies, P.: Exploiting spontaneous transmissions for broadcasting and leader election in radio networks. J. ACM (JACM) 68(2), 1–22 (2021)
Censor-Hillel, K., Gelles, R., Haeupler, B.: Making asynchronous distributed computations robust to noise. Distrib. Comput. 32, 405–421 (2019)
Chlamtac, I., Kutten, S.: On broadcasting in radio networks-problem analysis and protocol design. IEEE Trans. Commun. 33(12), 1240–1246 (2003)
Cornejo, A., Kuhn, F.: Deploying wireless networks with beeps. In: Proceedings of the 24th International Conference on Distributed Computing, DISC’10, 148–162, Cambridge, MA. Springer-Verlag. isbn: 3642157629. (2010)
Chang, Y.-J., Kopelowitz, T., Pettie, S., Wang, R., Zhan, W.: Exponential separations in the energy complexity of leader election. ACM Trans. Algorithms (2019). https://doi.org/10.1145/3341111
Dufoulon, F., Burman, J., Beauquier, J.: Beeping a deterministic time-optimal leader election. In: 32nd International Symposium on Distributed Computing (DISC 2018), 20–1. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, (2018)
Dolev, D.: The byzantine generals strike again. J. Algorithms 3(1), 14–30 (1982)
Doty, D., Soloveichik, D.: Stable leader election in population protocols requires linear time. Distrib. Comput. 31(4), 257–271 (2018)
Dubrova, E.: Fault-Tolerant Design. Springer, Berlin, (2013). https://doi.org/10.1007/978-1-4614-2113-9
Emek, Y., Keren, E.: A thin self-stabilizing asynchronous unison algorithm with applications to fault tolerant biological networks. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC), pp. 93–102. (2021)
Emek, Y., Wattenhofer, R.: Stone age distributed computing. In: Proceedings of the 2013 ACM symposium on Principles of distributed computing (PODC), pp. 137–146. (2013)
Frei, F., Gelles, R., Ghazy, A., Nolin, A.: Content-Oblivious Leader Election on Rings. In: Alistarh, D. (ed) 38th International Symposium on Distributed Computing (DISC 2024), volume319 of Leibniz International Proceedings in Informatics (LIPIcs), 26:1–26:20, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, (2024). isbn: 978-3-95977-352-2. https://doi.org/10.4230/LIPIcs.DISC.2024.26
Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM (JACM) 32(2), 374–382 (1985)
Fischer, O., Parter, M.: Distributed CONGEST algorithms against mobile adversaries. In: Oshman, R., Nolin, A., Halldórsson, M.M., Balliu, A. (eds) Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (PODC), 262–273. ACM, (2023). https://doi.org/10.1145/3583668.3594578
Förster, K.-T., Seidel, J., Wattenhofer, R.: Deterministic leader election in multi-hop beeping networks. In: Proceedings of 28th International Symposium on Distributed Computing (DISC), pp. 212–226. Springer (2014)
Gelles, R.: Coding for interactive communication: a survey. Found. Trends® Theor. Comput. Sci. 13, 1–157 (2017)
Ghaffari, M., Haeupler, B.: Near optimal leader election in multi-hop radio networks. In: Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms (SODA), pp. 748–766. SIAM (2013)
Hitron, Y., Parter, M.: Broadcast CONGEST algorithms against adversarial edges. In: Gilbert, S. (ed) Proceedings of the 35th International Symposium on Distributed Computing (DISC), vol 209 of LIPIcs, 23:1–23:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, (2021). https://doi.org/10.4230/LIPICS.DISC.2021.23
Hitron, Y., Parter, M.: General CONGEST compilers against adversarial edges. In: Gilbert, S. (ed) Proceedings of the 35th International Symposium on Distributed Computing (DISC), volume209 of LIPIcs, 24:1–24:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, (2021). https://doi.org/10.4230/LIPICS.DISC.2021.24
Hitron, Y., Parter, M., Yogev, E.: Broadcast CONGEST algorithms against eavesdroppers. In: Scheideler, C. (ed) Proceedings of the 36th International Symposium on Distributed Computing (DISC), vol 246 of LIPIcs, 27:1–27:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.DISC.2022.27
Hitron, Y., Parter, M., Yogev, E.: Secure distributed network optimization against eavesdroppers. In: Kalai, Y.T. (ed) Proceedings of the 14th Innovations in Theoretical Computer Science Conference (ITCS), vol 251 of LIPIcs, 71:1–71:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, (2023). https://doi.org/10.4230/LIPIcs.ITCS.2023.71
Jain, A., Kalai, Y.T., Lewko, A.B.: Interactive coding for multiparty protocols. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (ITCS), pp. 1–10. (2015)
Koren, I., Mani Krishna, C. (eds.): Fault-Tolerant Systems. Morgan Kaufmann, San Francisco, 2ndedition, (2020). https://doi.org/10.1016/B978-0-12-818105-8
Parter, M.: A graph theoretic approach for resilient distributed algorithms. In: Milani, A., Woelfel, P. (eds) Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), 324. ACM, (2022). https://doi.org/10.1145/3519270.3538453
Pelc, A.: Reliable communication in networks with byzantine link failures. Networks 22(5), 441–459 (1992)
Parter, M., Yogev, E.: Distributed algorithms made secure: a graph theoretic approach. In: Chan, T.M. (ed) Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1693–1710. SIAM, (2019). https://doi.org/10.1137/1.9781611975482.102
Parter, M., Yogev, E.: Secure distributed computing made (nearly) optimal. In: Robinson, P., Ellen, F. (eds) Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC), 107–116. ACM, (2019). https://doi.org/10.1145/3293611.3331620
Raynal, M.: Fault-Tolerant Message-Passing Distributed Systems: An Algorithmic Approach. Springer, Cham, (2018). https://doi.org/10.1007/978-3-319-94141-7
Herbert Ellis Robbins: A theorem on graphs, with an application to a problem of traffic control. Am. Math. Mon. 46(5), 281–283 (1939)
Rajagopalan, S., Schulman, L.: A coding theorem for distributed computation. In: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing (STOC), pp. 790–799. (1994)
Schulman, L.J.: Communication on noisy channels: a coding theorem for computation. In: Proceedings 33rd Annual Symposium on Foundations of Computer Science, pp. 724–733. IEEE Computer Society (1992)
Schulman, L.J.: Deterministic coding for interactive communication. In: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing (STOC), 747–756. (1993)
Schulman, L.J.: Coding for interactive communication. IEEE Trans. Inf. Theory 42(6), 1745–1756 (1996). https://doi.org/10.1109/18.556671
Sudo, Y., Masuzawa, T.: Leader election requires logarithmic time in population protocols. Parallel Process. Lett. 30(01), 2050005 (2020)
Santoro, N., Widmayer, P.: Time is not a healer. In: STACS 1989, vol 349 of Lecture Notes in Comput. Sci. Springer, pp. 304-313 (1989)
Vacus, R., Ziccardi, I.: Minimalist leader election under weak communication. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 406–416. (2025)
Funding
This work has been partially supported by ANR project DUCAT (ANR-20-CE48-0006),
by the Ministry of Education, Singapore, under its Academic Research Fund Tier 1 (24-1323-A0001),
and by the Italian MUR National Recovery and Resilience Plan funded by the European Union - NextGenerationEU through projects SERICS (PE00000014).
Author information
Authors and Affiliations
Contributions
All authors contributed equally to the writing and reviewing of the manuscript. Names are in alphabetical order following the convention of TCS.
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Chalopin, J., Chang, YJ., Chen, L. et al. Non-uniform content-oblivious leader election in 2-edge-connected networks. Distrib. Comput. 39, 25 (2026). https://doi.org/10.1007/s00446-026-00517-y
Received:
Accepted:
Published:
Version of record:
DOI: https://doi.org/10.1007/s00446-026-00517-y