Dynamic Size Counting in the Population Protocol Model
Pages 50 - 60
Abstract
The population protocol model describes collections of distributed agents that interact in pairs to solve a common task. We consider a dynamic variant of this prominent model, where we assume that an adversary may change the population size at an arbitrary point in time. In this model we tackle the problem of counting the population size: in the dynamic size counting problem the goal is to design an algorithm that computes an approximation of log n. This estimate can be used to turn static, non-uniform population protocols, i.e., protocols that depend on the population size n, into dynamic and loosely-stabilizing protocols.
Our contributions in this paper are three-fold. Starting from an arbitrary initial configuration, we first prove that the agents converge quickly to a valid configuration where each agent has a constant-factor approximation of log n, and once the agents reach such a valid configuration, they stay in it for a polynomial number of time steps. Second, we show how to use our protocol to define a uniform and loosely-stabilizing phase clock for the population protocol model. Finally, we support our theoretical findings by empirical simulations that show that our protocols work well in practice.
References
[1]
D. Alistarh, J. Aspnes, D. Eisenstat, R. Gelashvili, and R. L. Rivest. 2017. Time-space trade-offs in population protocols. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2560--2579.
[2]
D. Alistarh, J. Aspnes, and R. Gelashvili. 2018. Space-optimal majority in population protocols. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2221--2239. 44.
[3]
D. Alistarh, B. Dudek, A. Kosowski, D. Soloveichik, and P. Uznanski. 2017. Robust detection in leak-prone population protocols. In DNA Computing and Molecular Programming - 23rd International Conference, DNA, 155--171.
[4]
D. Angluin, J. Aspnes, Z. Diamadi, M. J. Fischer, and R. Peralta. 2006. Computation in networks of passively mobile finite-state sensors. Distributed Comput., 18, 235--253.
[5]
D. Angluin, J. Aspnes, and D. Eisenstat. 2008. Fast computation by population protocols with a leader. Distributed Comput., 21, 183--199.
[6]
A. Arora, S. Dolev, and M. G. Gouda. 1991. Maintaining digital clocks in step. Parallel Process. Lett., 1, 11--18.
[7]
G. Bankhamer, P. Berenbrink, F. Biermeier, R. Elsässer, H. Hosseinpour, D. Kaaser, and P. Kling. 2022. Fast consensus via the unconstrained undecided state dynamics. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA, 3417--3429.
[8]
G. Bankhamer, P. Berenbrink, F. Biermeier, R. Elsässer, H. Hosseinpour, D. Kaaser, and P. Kling. 2022. Population protocols for exact plurality consensus: how a small chance of failure helps to eliminate insignificant opinions. In PODC '22: ACM Symposium on Principles of Distributed Computing, 224--234.
[9]
P. Berenbrink, F. Biermeier, C. Hahn, and D. Kaaser. 2022. Loosely-stabilizing phase clocks and the adaptive majority problem. In 1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND, 7:1--7:17. .SAND.2022.7.
[10]
P. Berenbrink, R. Elsässer, T. Friedetzky, D. Kaaser, P. Kling, and T. Radzik. 2018. A population protocol for exact majority with o(log5/3 n) stabilization time and theta(log n) states. In 32nd International Symposium on Distributed Computing, DISC, 10:1--10:18.
[11]
P. Berenbrink, R. Elsässer, T. Friedetzky, D. Kaaser, P. Kling, and T. Radzik. 2021. Time-space trade-offs in population protocols for the majority problem. Distributed Comput., 34, 2, 91--111.
[12]
P. Berenbrink, G. Giakkoupis, and P. Kling. 2020. Optimal time and space leader election in population protocols. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC, 119--129. 7713.3384312.
[13]
P. Berenbrink, D. Hammer, D. Kaaser, U. Meyer, M. Penschuck, and H. Tran. 2020. Simulating population protocols in sub-constant time per interaction. In 28th Annual European Symposium on Algorithms, ESA, 16:1--16:22.
[14]
P. Berenbrink, D. Kaaser, P. Kling, and L. Otterbach. 2018. Simple and efficient leader election. In 1st Symposium on Simplicity in Algorithms, SOSA, 9:1--9:11.
[15]
P. Berenbrink, D. Kaaser, and T. Radzik. 2019. On counting the population size. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC, 43--52.
[16]
A. Bilke, C. Cooper, R. Elsässer, and T. Radzik. 2017. Brief announcement: population protocols for leader election and exact majority with O(log2 n) states and O(log2 n) convergence time. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC, 451--453. 087858.
[17]
L. Cardelli and A. Csikász-Nagy. 2012. The cell cycle switch computes approximate majority. Scientific reports, 2, 656.
[18]
Y.-J. Chen, N. Dalchau, N. Srinivas, A. Phillips, L. Cardelli, D. Soloveichik, and G. Seelig. 2013. Programmable chemical controllers made from dna. Nature nanotechnology, 8, 10, 755.
[19]
C. Delporte-Gallet, H. Fauconnier, R. Guerraoui, and E. Ruppert. 2006. When birds die: making population protocols fault-tolerant. In Distributed Computing in Sensor Systems, Second IEEE International Conference, DCOSS, 51--66.
[20]
S. Dolev and J. L. Welch. 2004. Self-stabilizing clock synchronization in the presence of byzantine faults. J. ACM, 51, 5, 780--799. 463.
[21]
D. Doty and M. Eftekhari. 2021. A survey of size counting in population protocols. Theor. Comput. Sci., 894, 91--102.
[22]
D. Doty and M. Eftekhari. 2022. Dynamic size counting in population protocols. In 1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND, 13:1--13:18.
[23]
D. Doty and M. Eftekhari. 2019. Efficient size estimation and impossibility of termination in uniform dense population protocols. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC, 34--42.
[24]
D. Doty, M. Eftekhari, L. Gasieniec, E. E. Severson, P. Uznanski, and G. Stachowiak. 2021. A time and space optimal stable population protocol solving exact majority. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS, 1044--1055.
[25]
D. Doty and E. E. Severson. 2021. Ppsim: A software package for efficiently simulating and visualizing population protocols. In Computational Methods in Systems Biology - 19th International Conference, CMSB, 245--253. 78-3-030-85633-5_16.
[26]
L. Gasieniec and G. Stachowiak. 2021. Enhanced phase clocks, population protocols, and fast space optimal leader election. J. ACM, 68, 1, 2:1--2:21.
[27]
L. Gasieniec and G. Stachowiak. 2018. Fast space optimal leader election in population protocols. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2653--2667. 75031.169.
[28]
F. James and L. Moneta. 2020. Review of high-quality random number generators. Computing and Software for Big Science, 4, 2. 4-3.
[29]
D. Kaaser and M. Lohmann. 2024. Dynamic size counting in the population protocol model. Full version of this paper. arXiv: 2405.05137 [cs.DC].
[30]
T. M. Liggett. 1985. Interacting Particle Systems.
[31]
M. Lüscher. 1994. A portable high-quality random number generator for lattice field theory simulations. Computer Physics Communications, 79, 100--110.
[32]
D. Soloveichik, M. Cook, E. Winfree, and J. Bruck. 2008. Computation with finite stochastic chemical reaction networks. Nat. Comput., 7, 4, 615--633.
[33]
Y. Sudo, R. Eguchi, T. Izumi, and T. Masuzawa. 2021. Time-optimal loosely-stabilizing leader election in population protocols. In 35th International Symposium on Distributed Computing, DISC, 40:1--40:17. 1.40.
[34]
Y. Sudo, J. Nakamura, Y. Yamauchi, F. Ooshita, H. Kakugawa, and T. Masuzawa. 2012. Loosely-stabilizing leader election in a population protocol model. Theor. Comput. Sci., 444, 100--112.
[35]
Y. Sudo, F. Ooshita, T. Izumi, H. Kakugawa, and T. Masuzawa. 2019. Logarithmic expected-time leader election in population protocol model. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC, 60--62.
Index Terms
- Dynamic Size Counting in the Population Protocol Model
Recommendations
On Counting the Population Size
PODC '19: Proceedings of the 2019 ACM Symposium on Principles of Distributed ComputingWe consider the problem of counting the population size in the population model. In this model, we are given a distributed system of n identical agents which interact in pairs with the goal to solve a common task. In each time step, the two interacting ...
Population Stability: Regulating Size in the Presence of an Adversary
PODC '18: Proceedings of the 2018 ACM Symposium on Principles of Distributed ComputingWe introduce a new coordination problem in distributed computing that we call the population stability problem. A system of agents each with limited memory and communication, as well as the ability to replicate and self-destruct, is subjected to attacks ...
Population size reduction for the differential evolution algorithm
This paper studies the efficiency of a recently defined population-based direct global optimization method called Differential Evolution with self-adaptive control parameters. The original version uses fixed population size but a method for gradually ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2024
570 pages
ISBN:9798400706684
DOI:10.1145/3662158
- Chair:
- Ran Gelles,
- Proceedings Chair:
- Dennis Olivetti,
- Program Chair:
- Petr Kuznetsov
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 17 June 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Austrian Federal Ministry for Digital and Economic Affairs, National Foundation for Research, Technology and Development, Christian Doppler Research Association
Conference
Acceptance Rates
Overall Acceptance Rate 740 of 2,477 submissions, 30%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 80Total Downloads
- Downloads (Last 12 months)80
- Downloads (Last 6 weeks)21
Reflects downloads up to 20 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in