Document Open Access Logo

Simulating Population Protocols in Sub-Constant Time per Interaction

Authors Petra Berenbrink, David Hammer , Dominik Kaaser , Ulrich Meyer, Manuel Penschuck, Hung Tran

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.16.pdf
  • Filesize: 0.73 MB
  • 22 pages

Document Identifiers

Author Details

Petra Berenbrink
  • Universität Hamburg, Germany
David Hammer
  • University of Southern Denmark, Odense, Denmark
  • Goethe University Frankfurt, Germany
Dominik Kaaser
  • Universität Hamburg, Germany
Ulrich Meyer
  • Goethe University Frankfurt, Germany
Manuel Penschuck
  • Goethe University Frankfurt, Germany
Hung Tran
  • Goethe University Frankfurt, Germany

Funding

This work was partially supported by the Deutsche Forschungsgemeinschaft (DFG) under grants ME 2088/3-2, ME 2088/4-2, and ME 2088/5-1.

Acknowledgements

This project was initiated on a workshop of the DFG FOR 2975/1. We thank the anonymous reviewers for their insightful comments and pointers, as well as the Center for Scientific Computing, University of Frankfurt, for making their HPC facilities available.

Cite AsGet BibTex

Petra Berenbrink, David Hammer, Dominik Kaaser, Ulrich Meyer, Manuel Penschuck, and Hung Tran. Simulating Population Protocols in Sub-Constant Time per Interaction. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 16:1-16:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.16

Abstract

We consider the efficient simulation of population protocols. In the population model, we are given a system of n agents modeled as identical finite-state machines. In each step, two agents are selected uniformly at random to interact by updating their states according to a common transition function. We empirically and analytically analyze two classes of simulators for this model. First, we consider sequential simulators executing one interaction after the other. Key to the performance of these simulators is the data structure storing the agents' states. For our analysis, we consider plain arrays, binary search trees, and a novel Dynamic Alias Table data structure. Secondly, we consider batch processing to efficiently update the states of multiple independent agents in one step. For many protocols considered in literature, our simulator requires amortized sub-constant time per interaction and is fast in practice: given a fixed time budget, the implementation of our batched simulator is able to simulate population protocols several orders of magnitude larger compared to the sequential competitors, and can carry out 2^50 interactions among the same number of agents in less than 400s.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Agent / discrete models
Keywords
  • Population Protocols
  • Simulation
  • Random Sampling
  • Dynamic Alias Table

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest. Time-space trade-offs in population protocols. In SODA, pages 2560-2579. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.169.
  2. Dan Alistarh, James Aspnes, and Rati Gelashvili. Space-optimal majority in population protocols. In SODA. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.144.
  3. Dan Alistarh and Rati Gelashvili. Polylogarithmic-time leader election in population protocols. In ICALP (2), volume 9135 of LNCS, pages 479-491. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-47666-6_38.
  4. Dan Alistarh, Rati Gelashvili, and Milan Vojnovic. Fast and exact majority in population protocols. In PODC, pages 47-56. ACM, 2015. URL: https://doi.org/10.1145/2767386.2767429.
  5. Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Comput., 18(4):235-253, 2006. URL: https://doi.org/10.1007/s00446-005-0138-3.
  6. Dana Angluin, James Aspnes, and David Eisenstat. Stably computable predicates are semilinear. In PODC, pages 292-299. ACM, 2006. URL: https://doi.org/10.1145/1146381.1146425.
  7. Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by population protocols with a leader. Distributed Comput., 21(3):183-199, 2008. URL: https://doi.org/10.1007/s00446-008-0067-z.
  8. Dana Angluin, James Aspnes, and David Eisenstat. A simple population protocol for fast robust approximate majority. Distributed Comput., 21(2):87-102, 2008. URL: https://doi.org/10.1007/s00446-008-0059-z.
  9. Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Comput., 20(4):279-304, 2007. URL: https://doi.org/10.1007/s00446-007-0040-2.
  10. Anish Arora, Shlomi Dolev, and Mohamed G. Gouda. Maintaining digital clocks in step. Parallel Process. Lett., 1:11-18, 1991. Google Scholar
  11. Richard Arratia, Skip Garibaldi, and Joe Kilian. Asymptotic distribution for the birthday problem with multiple coincidences, via an embedding of the collision process. Random Struct. Algorithms, 48(3):480-502, 2016. URL: https://doi.org/10.1002/rsa.20591.
  12. James Aspnes and Eric Ruppert. An introduction to population protocols. Bull. EATCS, 93:98-117, 2007. Google Scholar
  13. Stav Ben-Nun, Tsvi Kopelowitz, Matan Kraus, and Ely Porat. An O(log^3/2n) parallel time population protocol for majority with O(log n) states. In PODC, page to appear, 2020. Google Scholar
  14. Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. Majority & stabilization in population protocols. CoRR, abs/1805.04586, 2018. URL: http://arxiv.org/abs/1805.04586.
  15. Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. A population protocol for exact majority with o(log5/3 n) stabilization time and theta(log n) states. In DISC, volume 121 of LIPIcs, pages 10:1-10:18. Schloss Dagstuhl, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.10.
  16. Petra Berenbrink, George Giakkoupis, and Peter Kling. Optimal time and space leader election in population protocols. In STOC, pages 119-129, 2020. Google Scholar
  17. Petra Berenbrink, David Hammer, Dominik Kaaser, Ulrich Meyer, Manuel Penschuck, and Hung Tran. Simulating population protocols in sub-constant time per interaction. CoRR, 2020. URL: http://arxiv.org/abs/2005.03584.
  18. Petra Berenbrink, Dominik Kaaser, Peter Kling, and Lena Otterbach. Simple and efficient leader election. In SOSA@SODA, volume 61 of OASICS, pages 9:1-9:11. Schloss Dagstuhl, 2018. URL: https://doi.org/10.4230/OASIcs.SOSA.2018.9.
  19. Andreas Bilke, Colin Cooper, Robert Elsässer, and Tomasz Radzik. Brief announcement: Population protocols for leader election and exact majority with O(log² n) states and O(log² n) convergence time. In PODC. ACM, 2017. URL: https://doi.org/10.1145/3087801.3087858.
  20. Paul Bratley, Bennett L. Fox, and Linus Schrage. A guide to simulation, 2nd Edition. Springer, 1987. Google Scholar
  21. Luca Cardelli and Attila Csikász-Nagy. The cell cycle switch computes approximate majority. Scientific reports, 2:656, 2012. URL: https://doi.org/10.1038/srep00656.
  22. Yuan-Jyue Chen, Neil Dalchau, Niranjan Srinivas, Andrew Phillips, Luca Cardelli, David Soloveichik, and Georg Seelig. Programmable chemical controllers made from DNA. Nature nanotechnology, 8(10):755, 2013. URL: https://doi.org/10.1038/nnano.2013.189.
  23. Luc Devroye. Non-Uniform Random Variate Generation. Springer, 1986. URL: https://doi.org/10.1007/978-1-4613-8643-8.
  24. David Doty and David Soloveichik. Stable leader election in population protocols requires linear time. In DISC, volume 9363 of LNCS, pages 602-616. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48653-5_40.
  25. Moez Draief and Milan Vojnovic. Convergence speed of binary interval consensus. SIAM J. Control and Optimization, 50(3):1087-1109, 2012. URL: https://doi.org/10.1137/110823018.
  26. Robert Elsässer and Tomasz Radzik. Recent results in population protocols for exact majority and leader election. Bull. EATCS, 126, 2018. URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/549/546.
  27. Bennett L. Fox. Generating markov-chain transitions quickly: I. INFORMS J. Comput., 2(2):126-135, 1990. Google Scholar
  28. Leszek Gasieniec and Grzegorz Stachowiak. Fast space optimal leader election in population protocols. In SODA. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.169.
  29. Leszek Gasieniec, Grzegorz Stachowiak, and Przemyslaw Uznanski. Almost logarithmic-time space optimal leader election in population protocols. In SPAA, pages 93-102. ACM, 2019. URL: https://doi.org/10.1145/3323165.3323178.
  30. Torben Hagerup, Kurt Mehlhorn, and J. Ian Munro. Maintaining discrete probability distributions optimally. In ICALP, volume 700 of LNCS, pages 253-264. Springer, 1993. Google Scholar
  31. Lorenz Hübschle-Schneider and Peter Sanders. Parallel weighted random sampling. In ESA, volume 144 of LIPIcs, pages 59:1-59:24. Schloss Dagstuhl, 2019. Google Scholar
  32. Fabian Kuhn and René Struik. Random walks revisited: Extensions of pollard’s rho algorithm for computing multiple discrete logarithms. In Selected Areas in Cryptography, volume 2259 of LNCS, pages 212-229. Springer, 2001. URL: https://doi.org/10.1007/3-540-45537-X_17.
  33. Yossi Matias, Jeffrey Scott Vitter, and Wen-Chun Ni. Dynamic generation of discrete random variates. In SODA, pages 361-370. ACM/SIAM, 1993. Google Scholar
  34. George B. Mertzios, Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, and Paul G. Spirakis. Determining majority in networks with local interactions and very small local memory. In ICALP (1), volume 8572 of LNCS, pages 871-882. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_72.
  35. Yves Mocquard, Emmanuelle Anceaume, James Aspnes, Yann Busnel, and Bruno Sericola. Counting with population protocols. In NCA, pages 35-42. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/NCA.2015.35.
  36. Sanguthevar Rajasekaran and Keith W. Ross. Fast algorithms for generating discrete random variates with changing distributions. ACM Trans. Mod. Comp. Sim., 3(1), 1993. Google Scholar
  37. Peter Sanders and Sebastian Winkel. Super scalar sample sort. In ESA, volume 3221 of LNCS, pages 784-796. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-30140-0_69.
  38. David Soloveichik, Matthew Cook, Erik Winfree, and Jehoshua Bruck. Computation with finite stochastic chemical reaction networks. Nat. Comput., 7(4):615-633, 2008. URL: https://doi.org/10.1007/s11047-008-9067-y.
  39. Ernst Stadlober. Ratio of uniforms as a convenient method for sampling from classical discrete distributions. In Winter Simulation Conference, pages 484-489. ACM Press, 1989. URL: https://doi.org/10.1145/76738.76801.
  40. Michael D. Vose. A linear algorithm for generating random numbers with a given distribution. IEEE Trans. Software Eng., 17(9):972-975, 1991. URL: https://doi.org/10.1109/32.92917.
  41. Alastair J. Walker. An efficient method for generating discrete random variables with general distributions. ACM Math. Soft., 3(3), 1977. URL: https://doi.org/10.1145/355744.355749.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact