Abstract
Broadcast consensus protocols (BCPs) are a model of computation, in which anonymous, identical, finite-state agents compute by sending/receiving global broadcasts. BCPs are known to compute all number predicates in \(\mathsf {NL}=\mathsf {NSPACE}(\log n)\) where n is the number of agents. They can be considered an extension of the well-established model of population protocols. This paper investigates execution time characteristics of BCPs. We show that every predicate computable by population protocols is computable by a BCP with expected \(\mathcal {O}(n \log n)\) interactions, which is asymptotically optimal. We further show that every log-space, randomized Turing machine can be simulated by a BCP with \(\mathcal {O}(n \log n \cdot T)\) interactions in expectation, where T is the expected runtime of the Turing machine. This allows us to characterise polynomial-time BCPs as computing exactly the number predicates in \(\mathsf {ZPL}\), i.e. predicates decidable by log-space, randomised Turing machine with zero-error in expected polynomial time where the input is encoded as unary.
This work was supported by an ERC Advanced Grant (787367: PaVeS) and by the Research Training Network of the Deutsche Forschungsgemeinschaft (DFG) (378803395: ConVeY).
The full version of this paper can be found at https://arxiv.org/abs/2101.03780 .
Chapter PDF
Similar content being viewed by others
References
Alistarh, D., Aspnes, J., Eisenstat, D., Gelashvili, R., Rivest, R.L.: Time-space trade-offs in population protocols. In: Proceedings of the twenty-eighth annual ACM-SIAM symposium on discrete algorithms. pp. 2560–2579. SIAM (2017)
Alistarh, D., Aspnes, J., Gelashvili, R.: Space-optimal majority in population protocols. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 2221–2239. SIAM (2018)
Alistarh, D., Gelashvili, R.: Recent algorithmic advances in population protocols. ACM SIGACT News 49(3), 63–73 (2018)
Alistarh, D., Gelashvili, R., Vojnović, M.: Fast and exact majority in population protocols. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing. pp. 47–56 (2015)
Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distributed computing 18(4), 235–253 (2006), https://www.cs.yale.edu/homes/aspnes/papers/podc04passive-dc.pdf
Angluin, D., Aspnes, J., Eisenstat, D.: Stably computable predicates are semilinear. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing. pp. 292–299. PODC ’06, ACM, New York, NY, USA (2006). https://doi.org/10.1145/1146381.1146425
Angluin, D., Aspnes, J., Eisenstat, D.: Fast computation by population protocols with a leader. Distributed Computing 21(3), 183–199 (2008), https://www.cs.yale.edu/homes/aspnes/papers/disc2006-journal.pdf
Aspnes, J.: Clocked population protocols. In: Proceedings of the 2017 ACM Symposium on Principles of Distributed Computing (PODC). pp. 431–440 (2017). https://doi.org/10.1145/3087801.3087836
Aspnes, J., Ruppert, E.: An introduction to population protocols. In: Middleware for Network Eccentric and Mobile Applications, pp. 97–120. Springer (2009)
Belleville, A., Doty, D., Soloveichik, D.: Hardness of computing and approximating predicates and functions with leaderless population protocols. In: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)
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. pp. 119–129 (2020)
Bertrand, N., Dewaskar, M., Genest, B., Gimbert, H.: Controlling a population. In: Proc. \(28^{\text{th}}\) International Conference on Concurrency Theory (CONCUR). vol. 85, pp. 12:1–12:16 (2017). https://doi.org/10.4230/LIPIcs.CONCUR.2017.12
Blondin, M., Esparza, J., Jaax, S.: Expressive Power of Broadcast Consensus Protocols. In: Proceedings of the 30th International Conference on Concurrency Theory (CONCUR). pp. 31:1–31:16 (2019). https://doi.org/10.4230/LIPIcs.CONCUR.2019.31, http://drops.dagstuhl.de/opus/volltexte/2019/10933
Blondin, M., Esparza, J., Jaax, S.: Expressive power of broadcast consensus protocols (2019), https://arxiv.org/abs/1902.01668.pdf
Delzanno, G., Raskin, J., Begin, L.V.: Towards the automated verification of multithreaded Java programs. In: Proc. \(8^{\rm th}\) International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS). pp. 173–187 (2002)
Doty, D., Soloveichik, D.: Stable leader election in population protocols requires linear time. Distributed Computing 31(4), 257–271 (2018)
Emerson, E.A., Namjoshi, K.S.: On model checking for non-deterministic infinite-state systems. In: Proc. Thirteenth Annual IEEE Symposium on Logic in Computer Science (LICS). pp. 70–80 (1998). https://doi.org/10.1109/LICS.1998.705644
Esparza, J., Finkel, A., Mayr, R.: On the verification of broadcast protocols. In: Proc. \(14^{\rm th}\) Annual IEEE Symposium on Logic in Computer Science (LICS). pp. 352–359 (1999). https://doi.org/10.1109/LICS.1999.782630
Finkel, A., Leroux, J.: How to compose Presburger-accelerations: Applications to broadcast protocols. In: Proc. 22nd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). pp. 145–156 (2002)
Flajolet, P., Gardy, D., Thimonier, L.: Birthday paradox, coupon collectors, caching algorithms and self-organizing search. Discrete Applied Mathematics 39(3), 207–229 (1992)
Gąsieniec, L., Staehowiak, G.: Fast space optimal leader election in population protocols. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 2653–2667. SIAM (2018)
Ginsburg, S., Spanier, E.H.: Semigroups, presburger formulas, and languages. Pacific J. Math. 16(2), 285–296 (1966), https://projecteuclid.org:443/euclid.pjm/1102994974
Janson, S.: Tail bounds for sums of geometric and exponential variables. Statistics & Probability Letters 135, 1–6 (2018), https://arxiv.org/pdf/1709.08157.pdf
Kosowski, A., Uznanski, P.: Brief announcement: Population protocols are fast. In: Newport, C., Keidar, I. (eds.) Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018. pp. 475–477. ACM (2018), https://dl.acm.org/citation.cfm?id=3212788
Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Mediated population protocols. Theoretical Computer Science 412(22), 2434–2450 (2011)
Michail, O., Spirakis, P.G.: Terminating population protocols via some minimal global knowledge assumptions. Journal of Parallel and Distributed Computing pp. 1–10 (2015). https://doi.org/10.1016/j.jpdc.2015.02.005
Nisan, N.: On read once vs. multiple access to randomness in logspace. Theoretical Computer Science 107(1), 135–144 (1993)
Schmitz, S., Schnoebelen, P.: The power of well-structured systems. In: Proc. \(24^{\rm th}\) International Conference on Concurrency Theory (CONCUR). pp. 5–24 (2013)
Sudo, Y., Masuzawa, T.: Leader election requires logarithmic time in population protocols. Parallel Processing Letters 30(01), 2050005 (2020)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2021 The Author(s)
About this paper
Cite this paper
Czerner, P., Jaax, S. (2021). Running Time Analysis of Broadcast Consensus Protocols. In: Kiefer, S., Tasson, C. (eds) Foundations of Software Science and Computation Structures. FOSSACS 2021. Lecture Notes in Computer Science(), vol 12650. Springer, Cham. https://doi.org/10.1007/978-3-030-71995-1_9
Download citation
DOI: https://doi.org/10.1007/978-3-030-71995-1_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-71994-4
Online ISBN: 978-3-030-71995-1
eBook Packages: Computer ScienceComputer Science (R0)