Population Protocols for Exact Plurality Consensus: How a small chance of failure helps to eliminate insignificant opinions
Authors: 
Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer, Hamed Hosseinpour, Dominik Kaaser, 
Peter KlingAuthors Info & Claims
Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer, Hamed Hosseinpour, Dominik Kaaser, Peter KlingAuthors Info & ClaimsPages 224 - 234
Abstract
We consider the plurality consensus problem for population protocols. Here, n anonymous agents start each with one of k opinions. Their goal is to agree on the initially most frequent opinion (the plurality opinion) via random, pairwise interactions. Exact plurality consensus refers to the requirement that the plurality opinion must be identified even if the bias (difference between the most and second most frequent opinion) is only 1.
The case of k = 2 opinions is known as the majority problem. Recent breakthroughs led to an always correct, exact majority population protocol that is both time- and space-optimal, needing O(logn) states per agent and, with high probability, O(logn) time [Doty, Eftekhari, Gasieniec, Severson, Uznanski, and Stachowiak; 2021]. Meanwhile, results for general plurality consensus are rare and far from optimal. We know that any always correct protocol requires Ω(k2) states, while the currently best protocol needs O(k11) states [Natale and Ramezani; 2019]. For ordered opinions, this can be improved to O(k6) [Gasieniec, Hamilton, Martin, Spirakis, and Stachowiak; 2016].
References
[1]
Dan Alistarh, James Aspnes, and Rati Gelashvili. 2018. Space- Optimal Majority in Population Protocols. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, 2221--2239. 75031.144.
[2]
Dan Alistarh, Rati Gelashvili, and Milan Vojnovic. 2015. Fast and Exact Majority in Population Protocols. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, 47--56.
[3]
Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. 2006. Computation in networks of passively mobile finite-state sensors. Distributed Comput., 18, 4, 235--253.
[4]
Dana Angluin, James Aspnes, and David Eisenstat. 2008. A simple population protocol for fast robust approximate majority. Distributed Comput., 21, 2, 87--102. 0446-008-0059-z.
[5]
Dana Angluin, James Aspnes, and David Eisenstat. 2008. Fast computation by population protocols with a leader. Distributed Comput., 21, 3, 183--199. 67-z.
[6]
Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. 2007. The computational power of population protocols. Distributed Comput., 20, 4, 279--304. -0040--2.
[7]
Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer, Hamed Hosseinpour, Dominik Kaaser, and Peter Kling. 2022. Fast Consensus via the Unconstrained Undecided State Dynamics. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, 3417--3429.
[8]
Stav Ben-Nun, Tsvi Kopelowitz, Matan Kraus, and Ely Porat. 2020. An O(log3/2) Parallel Time Population Protocol for Majority with O(log) States. In PODC '20: ACM Symposium on Principles of Distributed Computing, Virtual Event, 191-- 199.
[9]
Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. 2018. A Population Protocol for Exact Majority with O(log5/3) Stabilization Time and (log) States. In 32nd International Symposium on Distributed Computing, DISC 2018, 10:1--10:18. 0/LIPIcs.DISC.2018.10.
[10]
Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. 2021. Time-space trade-offs in population protocols for the majority problem. Distributed Comput., 34, 2, 91--111. 00385-0.
[11]
Petra Berenbrink, Tom Friedetzky, Dominik Kaaser, and Peter Kling. 2019. Tight & Simple Load Balancing. In 2019 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2019, 718--726.
[12]
Petra Berenbrink, George Giakkoupis, and Peter 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 2020, 119--129.
[13]
James M. Bower and Hamid Bolouri, (Eds.) 2001. Computational modeling of genetic and biochemical networks. MIT Press.
[14]
Ho-Lin Chen, Rachel Cummings, David Doty, and David Soloveichik. 2017. Speed faults in computation by chemical reaction networks. Distributed Comput., 30, 5, 373--390.
[15]
Anne Condon, Monir Hajiaghayi, David G. Kirkpatrick, and Ján Manuch. 2020. Approximate majority analyses using trimolecular chemical reaction networks. Nat. Comput., 19, 1, 249--270.
[16]
Zoë Diamadi and Michael J. Fischer. 2001. A simple game for the study of trust in distributed systems. Wuhan University Journal of Natural Sciences, 6, 1--2, 72--82. 160228.
[17]
David Doty. 2014. Timing in chemical reaction networks. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, 772--784.
[18]
David Doty, Mahsa Eftekhari, Leszek Gasieniec, Eric E. Severson, Przemyslaw Uznanski, and Grzegorz Stachowiak. 2021. A time and space optimal stable population protocol solving exact majority. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, 1044--1055. 9/FOCS52979.2021.00104.
[19]
Leszek Gasieniec, David D. Hamilton, Russell Martin, Paul G. Spirakis, and Grzegorz Stachowiak. 2016. Deterministic Population Protocols for Exact Majority and Plurality. In 20th International Conference on Principles of Distributed Systems, OPODIS 2016, 14:1--14:14. .14.
[20]
Leszek Gasieniec and Grzegorz Stachowiak. 2021. Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election. J. ACM, 68, 1, 2:1--2:21.
[21]
Adrian Kosowski and Przemyslaw Uznanski. 2018. Brief Announcement: Population Protocols Are Fast. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, 475--477.
[22]
David Levin and Yuval Peres. 2017. Markov Chains and Mixing Times. (2nd ed.). American Mathematical Society.
[23]
Yves Mocquard, Frédérique Robin, Bruno Sericola, and Emmanuelle Anceaume. 2021. Stochastic analysis of averagebased distributed algorithms. J. Appl. Probab., 58, 2, 394--410.
[24]
Emanuele Natale and Iliad Ramezani. 2019. On the Necessary Memory to Compute the Plurality in Multi-agent Systems. In Algorithms and Complexity - 11th International Conference, CIAC 2019, 323--338.
[25]
V. Volterra. 1928. Variations and Fluctuations of the Number of Individuals in Animal Species living together. ICES Journal of Marine Science, 3, 1, (April 1928), 3--51. ms/3.1.3.
Index Terms
- Population Protocols for Exact Plurality Consensus: How a small chance of failure helps to eliminate insignificant opinions
Recommendations
Near-Optimal Leader Election in Population Protocols on Graphs
PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed ComputingIn the stochastic population protocol model, we are given a connected graph with n nodes, and in every time step, a scheduler samples an edge of the graph uniformly at random and the nodes connected by this edge interact. A fundamental task in this ...
Optimal time and space leader election in population protocols
STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of ComputingPopulation protocols are a model of distributed computing, where n agents with limited computational power and memory perform randomly scheduled pairwise interactions. A fundamental problem in this setting is that of leader election, where all agents ...
Fast and Exact Majority in Population Protocols
PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed ComputingPopulation protocols, roughly defined as systems consisting of large numbers of simple identical agents, interacting at random and updating their state following simple rules, are an important research topic at the intersection of distributed computing ...
Comments
Information & Contributors
Information
Published In
July 2022
509 pages
Copyright © 2022 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 21 July 2022
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
Acceptance Rates
Overall Acceptance Rate 740 of 2,477 submissions, 30%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 182Total Downloads
- Downloads (Last 12 months)26
- Downloads (Last 6 weeks)3
Reflects downloads up to 07 Nov 2024
Other Metrics
Citations
Cited By
View allView Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in