Document Open Access Logo

Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time

Authors Petra Berenbrink, Tom Friedetzky, George Giakkoupis, Peter Kling

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.136.pdf
  • Filesize: 0.61 MB
  • 14 pages

Document Identifiers

Author Details

Petra Berenbrink
Tom Friedetzky
George Giakkoupis
Peter Kling

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 136:1-136:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.136

Abstract

Plurality consensus considers a network of n nodes, each having one of k opinions. Nodes execute a (randomized) distributed protocol with the goal that all nodes adopt the plurality (the opinion initially supported by the most nodes). Communication is realized via the Gossip (or random phone call) model. A major open question has been whether there is a protocol for the complete graph that converges (w.h.p.) in polylogarithmic time and uses only polylogarithmic memory per node (local memory). We answer this question affirmatively.

We propose two protocols that need only mild assumptions on the bias in favor of the plurality. As an example of our results, consider the complete graph and an arbitrarily small constant multiplicative bias in favor of the plurality. Our first protocol achieves plurality consensus in O(log(k)*log(log(n))) rounds using log(k) + Theta(log(log(k))) bits of local memory. Our second protocol achieves plurality consensus in O(log(n)*log(log(n))) rounds using only log(k) + 4 bits of local memory. This disproves a conjecture by Becchetti et al. (SODA'15) implying that any protocol with local memory log(k)+O(1) has worst-case runtime Omega(k). We provide similar bounds for much weaker bias assumptions. At the heart of our protocols lies an undecided state, an idea introduced by Angluin et al. (Distributed Computing'08).

Subject Classification

Keywords
  • plurality consensus
  • voting
  • majority
  • distributed
  • gossip

Metrics

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

References

  1. Mohammed Amin Abdullah and Moez Draief. Majority consensus on random graphs of a given degree sequence. CoRR, abs/1209.5025, 2012. URL: http://arxiv.org/abs/1209.5025.
  2. 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), pages 47-56, 2015. URL: http://dx.doi.org/10.1145/2767386.2767429.
  3. Dana Angluin, James Aspnes, and David Eisenstat. A simple population protocol for fast robust approximate majority. Distributed Computing, 21(2):87-102, 2008. URL: http://dx.doi.org/10.1007/s00446-008-0059-z.
  4. Arta Babaee and Moez Draief. Distributed multivalued consensus. The Computer Journal, 57(8):1132-1140, 2014. URL: http://dx.doi.org/10.1093/comjnl/bxt026.
  5. Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, and Riccardo Silvestri. Plurality consensus in the gossip model. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 371-390, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.27.
  6. Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan. Stabilizing consensus with many opinions. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 620-635, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch46.
  7. P. Berenbrink, T. Friedetzky, P. Kling, F. Mallmann-Trenn, and C. Wastell. Plurality Consensus via Shuffling: Lessons Learned from Load Balancing. ArXiv e-prints, February 2016. URL: http://arxiv.org/abs/1602.01342.
  8. Colin Cooper, Robert Elsässer, Hirotaka Ono, and Tomasz Radzik. Coalescing random walks and voting on graphs. In Proceedings of the 31st ACM Symposium on Principles of Distributed Computing (PODC), pages 47-56, 2012. URL: http://dx.doi.org/10.1145/2332432.2332440.
  9. Colin Cooper, Robert Elsässer, and Tomasz Radzik. The power of two choices in distributed voting. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), pages 435-446, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43951-7_37.
  10. Colin Cooper, Tomasz Radzik, Nicolas Rivera, and Takeharu Shiraga. Coalescing walks on rotor-router systems. In Proceedings of the 22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 444-458, 2015. URL: http://dx.doi.org/10.1007/978-3-319-25258-2_31.
  11. Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, and Christian Scheideler. Stabilizing consensus with the power of two choices. In Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 149-158, 2011. URL: http://dx.doi.org/10.1145/1989493.1989516.
  12. Moez Draief and Milan Vojnović. Convergence speed of binary interval consensus. SIAM Journal on Control and Optimisation, 50(3):1087-1109, 2012. Google Scholar
  13. Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Frederik Mallmann-Trenn, and Horst Trinker. Efficient k-party voting with two choices. CoRR, abs/1602.04667, 2016. URL: http://arxiv.org/abs/1602.04667.
  14. Mohsen Ghaffari and Merav Parter. A polylogarithmic gossip algorithm for plurality consensus. In Proceedings of the 35th ACM Symposium on Principles of Distributed Computing (PODC), 2016. to appear. Google Scholar
  15. Y. Hassin and D. Peleg. Distributed probabilistic polling and applications to proportionate agreement. Information and Computation, 171(2):248-268, 2001. URL: http://dx.doi.org/10.1006/inco.2001.3088.
  16. R. Holley and T. Liggett. Ergodic theorems for weakly interacting infinite systems and the voter model. The Annals of Probability, 3(4):643-663, 1975. URL: http://www.jstor.org/stable/2959329.
  17. K. Jung, B. Y. Kim, and M. Vojnovic. Distributed ranking in networks with limited memory and communication. In Proc. of the 2012 IEEE Int'l Symposium on Information Theory Proceedings (ISIT), pages 980-984, 2012. URL: http://dx.doi.org/10.1109/ISIT.2012.6284710.
  18. Richard M. Karp, Christian Schindelhauer, Scott Shenker, and Berthold Vöcking. Randomized rumor spreading. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), pages 565-574, 2000. URL: http://dx.doi.org/10.1109/SFCS.2000.892324.
  19. Etienne Perron, Dinkar Vasudevan, and Milan Vojnovic. Using three states for binary consensus on complete graphs. In Proceedings of the 28th IEEE International Conference on Computer Communications (INFOCOM), pages 2527-2535, 2009. URL: http://dx.doi.org/10.1109/INFCOM.2009.5062181.
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 About DROPS Imprint Privacy Contact