Document Open Access Logo

On the Hierarchy of Distributed Majority Protocols

Authors Petra Berenbrink , Amin Coja-Oghlan , Oliver Gebhard , Max Hahn-Klimroth , Dominik Kaaser , Malin Rau

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2022.23.pdf
  • Filesize: 0.86 MB
  • 19 pages

Document Identifiers

Author Details

Petra Berenbrink
  • Universität Hamburg, Germany
Amin Coja-Oghlan
  • TU Dortmund University, Germany
Oliver Gebhard
  • TU Dortmund University, Germany
Max Hahn-Klimroth
  • TU Dortmund University, Germany
Dominik Kaaser
  • TU Hamburg, Germany
Malin Rau
  • Universität Hamburg, Germany

Funding

  • Berenbrink, Petra: DFG FOR 2975
  • Coja-Oghlan, Amin: DFG FOR 2975
  • Gebhard, Oliver: DFG CO 646/3
  • Hahn-Klimroth, Max: DFG FOR 2975
  • Rau, Malin: DFG FOR 2975

Cite AsGet BibTex

Petra Berenbrink, Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser, and Malin Rau. On the Hierarchy of Distributed Majority Protocols. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.OPODIS.2022.23

Abstract

We study the consensus problem among n agents, defined as follows. Initially, each agent holds one of two possible opinions. The goal is to reach a consensus configuration in which every agent shares the same opinion. To this end, agents randomly sample other agents and update their opinion according to a simple update function depending on the sampled opinions. We consider two communication models: the gossip model and a variant of the population model. In the gossip model, agents are activated in parallel, synchronous rounds. In the population model, one agent is activated after the other in a sequence of discrete time steps. For both models we analyze the following natural family of majority processes called j-Majority: when activated, every agent samples j other agents uniformly at random (with replacement) and adopts the majority opinion among the sample (breaking ties uniformly at random). As our main result we show a hierarchy among majority protocols: (j+1)-Majority (for j > 1) converges stochastically faster than j-Majority for any initial opinion configuration. In our analysis we use Strassen’s Theorem to prove the existence of a coupling. This gives an affirmative answer for the case of two opinions to an open question asked by Berenbrink et al. [PODC 2017].

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Theory of computation → Random walks and Markov chains
  • Mathematics of computing → Stochastic processes
Keywords
  • Consensus
  • Majority
  • Hierarchy
  • Stochastic Dominance
  • Population Protocols
  • Gossip Model
  • Strassen’s Theorem

Metrics

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

Related Versions

References

  1. Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest. Time-Space Trade-offs in Population Protocols. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, 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 Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 2221-2239. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.144.
  3. Dan Alistarh, Rati Gelashvili, and Milan Vojnovic. Fast and Exact Majority in Population Protocols. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, pages 47-56. ACM, 2015. URL: https://doi.org/10.1145/2767386.2767429.
  4. 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.
  5. 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.
  6. Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer, Hamed Hosseinpour, Dominik Kaaser, and Peter Kling. Fast Consensus via the Unconstrained Undecided State Dynamics. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 3417-3429. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977073.135.
  7. Gregor Bankhamer, Robert Elsässer, Dominik Kaaser, and Matjaz Krnc. Positive Aging Admits Fast Asynchronous Plurality Consensus. In PODC '20: ACM Symposium on Principles of Distributed Computing, pages 385-394. ACM, 2020. URL: https://doi.org/10.1145/3382734.3406506.
  8. Luca Becchetti, Andrea E. F. Clementi, and Emanuele Natale. Consensus Dynamics: An Overview. SIGACT News, 51(1):58-104, 2020. URL: https://doi.org/10.1145/3388392.3388403.
  9. Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, and Riccardo Silvestri. Plurality Consensus in the Gossip Model. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pages 371-390. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.27.
  10. Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, and Luca Trevisan. Simple dynamics for plurality consensus. Distributed Comput., 30(4):293-306, 2017. URL: https://doi.org/10.1007/s00446-016-0289-4.
  11. Stav Ben-Nun, Tsvi Kopelowitz, Matan Kraus, and Ely Porat. An O(log^3/2 n) Parallel Time Population Protocol for Majority with O(log n) States. In PODC '20: ACM Symposium on Principles of Distributed Computing, pages 191-199. ACM, 2020. URL: https://doi.org/10.1145/3382734.3405747.
  12. Petra Berenbrink, Andrea E. F. Clementi, Robert Elsässer, Peter Kling, Frederik Mallmann-Trenn, and Emanuele Natale. Ignore or Comply?: On Breaking Symmetry in Consensus. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, pages 335-344. ACM, 2017. URL: https://doi.org/10.1145/3087801.3087817.
  13. Petra Berenbrink, Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser, and Malin Rau. On the Hierarchy of Distributed Majority Protocols. CoRR, abs/2205.08203, 2022. URL: https://doi.org/10.48550/arXiv.2205.08203.
  14. Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. A Population Protocol for Exact Majority with O(log^5/3 n) Stabilization Time and Θ(log n) States. In 32nd International Symposium on Distributed Computing, DISC 2018, pages 10:1-10:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.10.
  15. Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. Time-space trade-offs in population protocols for the majority problem. Distributed Comput., 34(2):91-111, 2021. URL: https://doi.org/10.1007/s00446-020-00385-0.
  16. Petra Berenbrink, Tom Friedetzky, George Giakkoupis, and Peter Kling. Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, pages 136:1-136:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.136.
  17. Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec, and Frederik Mallmann-Trenn. Bounds on the Voter Model in Dynamic Networks. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, pages 146:1-146:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.146.
  18. 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 Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, pages 451-453. ACM, 2017. URL: https://doi.org/10.1145/3087801.3087858.
  19. Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, and Petar Maymounkov. Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, pages 961-970. ACM, 2012. URL: https://doi.org/10.1145/2213977.2214064.
  20. Andrea E. F. Clementi, Mohsen Ghaffari, Luciano Gualà, Emanuele Natale, Francesco Pasquale, and Giacomo Scornavacca. A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors. In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, pages 28:1-28:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.28.
  21. Anne Condon, Monir Hajiaghayi, David G. Kirkpatrick, and Ján Manuch. Approximate majority analyses using tri-molecular chemical reaction networks. Nat. Comput., 19(1):249-270, 2020. URL: https://doi.org/10.1007/s11047-019-09756-4.
  22. Colin Cooper, Robert Elsässer, Hirotaka Ono, and Tomasz Radzik. Coalescing random walks and voting on graphs. In ACM Symposium on Principles of Distributed Computing, PODC '12, pages 47-56. ACM, 2012. URL: https://doi.org/10.1145/2332432.2332440.
  23. Colin Cooper, Robert Elsässer, and Tomasz Radzik. The Power of Two Choices in Distributed Voting. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, pages 435-446. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43951-7_37.
  24. Colin Cooper, Robert Elsässer, Tomasz Radzik, Nicolas Rivera, and Takeharu Shiraga. Fast Consensus for Voting on General Expander Graphs. In Distributed Computing - 29th International Symposium, DISC 2015, pages 248-262. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48653-5_17.
  25. Colin Cooper, Tomasz Radzik, Nicolas Rivera, and Takeharu Shiraga. Fast Plurality Consensus in Regular Expanders. In 31st International Symposium on Distributed Computing, DISC 2017, pages 13:1-13:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.13.
  26. Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, and Christian Scheideler. Stabilizing consensus with the power of two choices. In SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, pages 149-158. ACM, 2011. URL: https://doi.org/10.1145/1989493.1989516.
  27. David Doty and Mahsa Eftekhari. 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 2019, pages 34-42. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331627.
  28. David Doty, Mahsa Eftekhari, Leszek Gasieniec, Eric E. Severson, Przemyslaw Uznanski, and Grzegorz Stachowiak. A time and space optimal stable population protocol solving exact majority. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pages 1044-1055. IEEE, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00104.
  29. David Doty and David Soloveichik. Stable leader election in population protocols requires linear time. Distributed Comput., 31(4):257-271, 2018. URL: https://doi.org/10.1007/s00446-016-0281-z.
  30. Moez Draief and Milan Vojnovic. Convergence Speed of Binary Interval Consensus. SIAM J. Control. Optim., 50(3):1087-1109, 2012. URL: https://doi.org/10.1137/110823018.
  31. Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Frederik Mallmann-Trenn, and Horst Trinker. Brief Announcement: Rapid Asynchronous Plurality Consensus. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, pages 363-365. ACM, 2017. URL: https://doi.org/10.1145/3087801.3087860.
  32. William Feller. An Introduction to Probability Theory and Its Applications, volume 1. Wiley, 3rd edition, 2008. Google Scholar
  33. Pierre Fraigniaud and Emanuele Natale. Noisy rumor spreading and plurality consensus. Distributed Comput., 32(4):257-276, 2019. URL: https://doi.org/10.1007/s00446-018-0335-5.
  34. Leszek Gasieniec, David D. Hamilton, Russell Martin, Paul G. Spirakis, and Grzegorz Stachowiak. Deterministic Population Protocols for Exact Majority and Plurality. In 20th International Conference on Principles of Distributed Systems, OPODIS 2016, pages 14:1-14:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2016.14.
  35. Mohsen Ghaffari and Johannes Lengler. Nearly-Tight Analysis for 2-Choice and 3-Majority Consensus Dynamics. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, pages 305-313. ACM, 2018. URL: https://doi.org/10.1145/3212734.3212738.
  36. Mohsen Ghaffari and Merav Parter. A Polylogarithmic Gossip Algorithm for Plurality Consensus. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, pages 117-126. ACM, 2016. URL: https://doi.org/10.1145/2933057.2933097.
  37. Yehuda Hassin and David Peleg. Distributed Probabilistic Polling and Applications to Proportionate Agreement. Inf. Comput., 171(2):248-268, 2001. URL: https://doi.org/10.1006/inco.2001.3088.
  38. Varun Kanade, Frederik Mallmann-Trenn, and Thomas Sauerwald. On coalescence time in graphs: When is coalescing as fast as meeting?: Extended Abstract. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 956-965. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.59.
  39. Adrian Kosowski and Przemyslaw Uznanski. Brief Announcement: Population Protocols Are Fast. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, pages 475-477. ACM, 2018. URL: https://doi.org/10.1145/3212734.3212788.
  40. Johannes Lengler. Drift Analysis. In Benjamin Doerr and Frank Neumann, editors, Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pages 89-131. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-29414-4_2.
  41. 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 Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, pages 871-882. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_72.
  42. Yves Mocquard, Emmanuelle Anceaume, James Aspnes, Yann Busnel, and Bruno Sericola. Counting with Population Protocols. In 14th IEEE International Symposium on Network Computing and Applications, NCA 2015, pages 35-42. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/NCA.2015.35.
  43. Toshio Nakata, Hiroshi Imahayashi, and Masafumi Yamashita. A probabilistic local majority polling game on weighted directed graphs with an application to the distributed agreement problem. Networks, 35(4):266-273, 2000. URL: https://doi.org/10.1002/1097-0037(200007)35:4<266::AID-NET5>3.0.CO;2-4.
  44. Emanuele Natale and Iliad Ramezani. On the Necessary Memory to Compute the Plurality in Multi-agent Systems. In Algorithms and Complexity - 11th International Conference, CIAC 2019, pages 323-338. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-17402-6_27.
  45. Grant Schoenebeck and Fang-Yi Yu. Consensus of Interacting Particle Systems on Erdös-Rényi Graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 1945-1964. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.127.
  46. Volker Strassen. The existence of probability measures with given marginals. The Annals of Mathematical Statistics, 36(2):423-439, 1965. Google Scholar
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