Abstract
Population protocols are a model of distributed computation intended for the study of networks of independent computing agents with dynamic communication structure. Each agent has a finite number of states, and communication opportunities occur nondeterministically, allowing the agents involved to change their states based on each other’s states. Population protocols are often studied in terms of reaching a consensus on whether the input configuration satisfied some predicate.
A desirable property of a computation model is modularity, the ability to combine existing simpler computations in a straightforward way. In the present paper we present a more general notion of functionality implemented by a population protocol in terms of multisets of inputs and outputs. This notion allows to design multiphase protocols as combinations of independently defined phases. The additional generality also increases the range of behaviours that can be captured in applications (e.g. maintaining the role distribution in a fleet of servers).
We show that composition of protocols can be performed in a uniform mechanical way, and that the expressive power is essentially semilinear, similar to the predicate expressive power in the original population protocol setting.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Angluin, D., Aspnes, J., Chan, M., Fischer, M.J., Jiang, H., Peralta, R.: Stably computable properties of network graphs. In: International Conference on Distributed Computing in Sensor Systems (2005). https://api.semanticscholar.org/CorpusID:16310485
Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. In: Chaudhuri, S., Kutten, S. (eds.) PODC, pp. 290–299. ACM (2004). https://doi.org/10.1145/1011767.1011810
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)
Angluin, D., Aspnes, J., Eisenstat, D.: Fast computation by population protocols with a leader. In: Dolev, S. (ed.) In Distributed Computing: 20th International Symposium, DISC 2006. Lecture Notes in Computer Science, vol. 4167, pp. 61–75. Springer (2006)
Angluin, D., Aspnes, J., Eisenstat, D., Ruppert, E.: The computational power of population protocols. Distrib. Comput. 20(4), 279–304 (2007). https://arxiv.org/abs/cs/0608084
Angluin, D., Aspnes, J., Fischer, M.J., Jiang, H.: Self-stabilizing population protocols. In: TAAS (2005). https://api.semanticscholar.org/CorpusID:63153
Austin, M.A., Johnson, J.: Compositional approach to distributed system behavior modeling and formal validation of infrastructure operations with finite state automata: application to viewpoint-driven verification of functionality in waterways. Syst. 6, 2 (2018). https://api.semanticscholar.org/CorpusID:4786185
Blondin, M., Esparza, J., Genest, B., Helfrich, M., Jaax, S.: Succinct population protocols for Presburger arithmetic. In submission (2019). http://arxiv.org/abs/1910.04600
Blondin, M., Esparza, J., Jaax, S., Meyer, P.J.: Towards efficient verification of population protocols. In: Schiller, E.M., Schwarzmann, A.A. (eds.) PODC, pp. 423–430. ACM (2017)
Czerner, P., Guttenberg, R., Helfrich, M., Esparza, J.: Fast and succinct population protocols for Presburger arithmetic. J. Comput. Syst. Sci. 140, 103481 (2024). https://doi.org/10.1016/j.jcss.2023.103481
Czerwiński, W., Lasota, S., Lazić, R., Leroux, J., Mazowiecki, F.: The reachability problem for Petri nets is not elementary. In: Proc. \(51^{st}\) Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 24–33 (2019). https://doi.org/10.1145/3313276.3316369
Delporte-Gallet, C., Devismes, S., Fauconnier, H.: Robust stabilizing leader election. In: Safety-critical Systems Symposium (2007). https://api.semanticscholar.org/CorpusID:2179550
Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Commun. ACM 17, 643–644 (1974). https://api.semanticscholar.org/CorpusID:11101426
Dolev, S., Israeli, A., Moran, S.: Self-stabilization of dynamic systems assuming only read/write atomicity. Distrib. Comput. 7(1), 3–16 (1993). https://doi.org/10.1007/BF02278851
Doty, D., Soloveichik, D.: Stable leader election in population protocols requires linear time. In: Moses, Y. (ed.) DISC. LNCS, vol. 9363, pp. 602–616. Springer, Cham (2015). https://arxiv.org/abs/1502.04246
Esparza, J., Ganty, P., Leroux, J., Majumdar, R.: Verification of population protocols. In: Aceto, L., de Frutos Escrig, D. (eds.) 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), vol. 42, pp. 470–482. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl (2015). https://doi.org/10.4230/LIPIcs.CONCUR.2015.470, http://drops.dagstuhl.de/opus/volltexte/2015/5377
Esparza, J., Ganty, P., Leroux, J., Majumdar, R.: Model checking population protocols. In: Lal, A., Akshay, S., Saurabh, S., Sen, S. (eds.) 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 65, pp. 27:1–27:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl (2016). https://doi.org/10.4230/LIPIcs.FSTTCS.2016.27, http://drops.dagstuhl.de/opus/volltexte/2016/6862
Esparza, J., Jaax, S., Raskin, M.A., Weil-Kennedy, C.: The complexity of verifying population protocols. Distrib. Comput. 34(2), 133–177 (2021). https://doi.org/10.1007/s00446-021-00390-x
Esparza, J., Raskin, M., Weil-Kennedy, C.: Parameterized analysis of immediate observation petri nets (2019). http://arxiv.org/abs/1902.03025
Gasieniec, L., Hamilton, D.D., Martin, R., Spirakis, P.G., Stachowiak, G.: Deterministic population protocols for exact majority and plurality. In: Fatourou, P., Jiménez, E., Pedone, F. (eds.) 20th International Conference on Principles of Distributed Systems, OPODIS 2016, 13–16 December 2016, Madrid, Spain. LIPIcs, vol. 70, pp. 14:1–14:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016). https://doi.org/10.4230/LIPICS.OPODIS.2016.14
Gouda, M., Herman, T.: Adaptive programming. IEEE Trans. Software Eng. 17(9), 911–921 (1991). https://doi.org/10.1109/32.92911
Huang, P., et al.: Gray failure. In: Proceedings of the 16th Workshop on Hot Topics in Operating Systems - HotOS 2017. ACM Press (2017). https://doi.org/10.1145/3102980.3103005
Leroux, J.: Vector addition system reversible reachability problem. Log. Methods Comput. Sci. 9(1) (2013). https://doi.org/10.2168/LMCS-9(1:5)2013
Raskin, M.: Modular population protocols. CoRR (2024). https://arxiv.org/abs/2111.11983v3
Viroli, M., Audrito, G., Beal, J., Damiani, F., Pianini, D.: Engineering resilient collective adaptive systems by self-stabilisation. ACM Trans. Model. Comput. Simul. (TOMACS) 28, 1–28 (2017). https://api.semanticscholar.org/CorpusID:4302945
Acknowledgements
I would like to thank Javier Esparza, Roland Guttenberg, Jérôme Leroux and Chana Weil-Kennedy for useful discussions. I am also grateful to the anonymous reviewers of this and previous versions for their valuable feedback and advice on presentation.
The project has been supported by a European Research Council (ERC) project under the European Union’s Horizon 2020 research and innovation programme grant agreement No 787367 (PaVeS) This work has been supported by France National Research Agency (ANR) grant ANR-23-CE48-0005 (PaVeDyS).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Ethics declarations
Disclosure of Interests
The author(s) have no competing interests to declare that are relevant to the content of this article.
Rights and permissions
Copyright information
© 2025 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Raskin, M. (2025). Modular Population Protocols. In: Bramas, Q., Casteigts, A., Meeks, K. (eds) Algorithmics of Wireless Networks. ALGOWIN 2024. Lecture Notes in Computer Science, vol 15026. Springer, Cham. https://doi.org/10.1007/978-3-031-74580-5_13
Download citation
DOI: https://doi.org/10.1007/978-3-031-74580-5_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-74579-9
Online ISBN: 978-3-031-74580-5
eBook Packages: Computer ScienceComputer Science (R0)