Document Open Access Logo

Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing

Authors Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, Chris Wastell

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.10.pdf
  • Filesize: 0.69 MB
  • 18 pages

Document Identifiers

Author Details

Petra Berenbrink
Tom Friedetzky
Peter Kling
Frederik Mallmann-Trenn
Chris Wastell

Cite As Get BibTex

Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, and Chris Wastell. Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.10

Abstract

We consider plurality consensus in networks of n nodes. Initially, each node has one of k opinions. The nodes execute a (randomized) distributed protocol to agree on the plurality opinion (the opinion initially supported by the most nodes). In certain types of networks the nodes can be quite cheap and simple, and hence one seeks protocols that are not only time efficient but also simple and space efficient. Typically, protocols depend heavily on the employed communication mechanism, which ranges from sequential (only one pair of nodes communicates at any time) to fully parallel (all nodes communicate with all their neighbors at once) and everything in-between.

We propose a framework to design protocols for a multitude of communication mechanisms. We introduce protocols that solve the plurality consensus problem and are, with probability 1-o(1), both time and space efficient. Our protocols are based on an interesting relationship between plurality consensus and distributed load balancing. This relationship allows us to design protocols that generalize the state of the art for a large range of problem parameters.

Subject Classification

Keywords
  • Plurality Consensus
  • Distributed Computing
  • Load Balancing

Metrics

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

References

  1. D. Aldous and J. Fill. Reversible markov chains and random walks on graphs, 2002. Unpublished. URL: http://www.stat.berkeley.edu/~aldous/RWG/book.html.
  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. Google Scholar
  3. Dana Angluin, James Aspnes, and David Eisenstat. A simple population protocol for fast robust approximate majority. Distributed Computing, 21(2):87-102, 2008. Google Scholar
  4. Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing, 20(4):279-304, 2007. Google Scholar
  5. James Aspnes and Eric Ruppert. An introduction to population protocols. Bulletin of the EATCS, 93:98-117, 2007. Google Scholar
  6. Chen Avin, Michal Koucký, and Zvi Lotker. How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). In Automata, Languages and Programming, 35th International Colloquium, ICALP, pages 121-132, 2008. Google Scholar
  7. Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal. Balanced allocations. SIAM Journal of Computing, 29(1):180-200, 1999. Google Scholar
  8. Luca Becchetti, Andrea 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.
  9. Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, and Luca Trevisan. Simple dynamics for plurality consensus. In 26th ACM Symposium on Parallelism in Algorithms and Architectures, (SPAA), pages 247-256, 2014. URL: http://dx.doi.org/10.1145/2612669.2612677.
  10. Florence Bénézit, Patrick Thiran, and Martin Vetterli. Interval consensus: From quantized gossip to voting. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP, pages 3661-3664. IEEE, 2009. Google Scholar
  11. Florence Bénézit, Patrick Thiran, and Martin Vetterli. The distributed multiple voting problem. J. Sel. Topics Signal Processing, 5(4):791-804, 2011. Google Scholar
  12. Petra Berenbrink, Colin Cooper, Tom Friedetzky, Tobias Friedrich, and Thomas Sauerwald. Randomized diffusion for indivisible loads. J. Comput. Syst. Sci., 81(1):159-185, 2015. Google Scholar
  13. Petra Berenbrink, Tom Friedetzky, George Giakkoupis, and Peter Kling. Efficient plurality consensus, or: The benefits of cleaning up from time to time. In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP), 2016. to appear. Google Scholar
  14. Stephen P. Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory, 52(6):2508-2530, 2006. Google Scholar
  15. Luca Cardelli and Attila Csikász-Nagy. The cell cycle switch computes approximate majority. Scientific reports, 2, 2012. Google Scholar
  16. 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-762, 2013. Google Scholar
  17. Andrea E. F. Clementi, Miriam Di Ianni, Giorgio Gambosi, Emanuele Natale, and Riccardo Silvestri. Distributed community detection in dynamic graphs. Theor. Comput. Sci., 584:19-41, 2015. Google Scholar
  18. 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), pages 435-446, 2014. Google Scholar
  19. Colin Cooper, Robert Elsässer, Tomasz Radzik, Nicolas Rivera, and Takeharu Shiraga. Fast consensus for voting on general expander graphs. In Proceedings of the 29th International Symposium on Distributed Computing (DISC), pages 248-262, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48653-5_17.
  20. 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. Google Scholar
  21. Moez Draief and Milan Vojnovic. Convergence speed of binary interval consensus. SIAM J. Control and Optimization, 50(3):1087-1109, 2012. Google Scholar
  22. Devdatt P. Dubhashi and Desh Ranjan. Balls and bins: A study in negative dependence. Random Struct. Algorithms, 13(2):99-124, 1998. Google Scholar
  23. 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.
  24. Bhaskar Ghosh and S. Muthukrishnan. Dynamic load balancing by random matchings. J. Comput. Syst. Sci., 53(3):357-370, 1996. URL: http://dx.doi.org/10.1006/jcss.1996.0075.
  25. David Kempe, Alin Dobra, and Johannes Gehrke. Gossip-based computation of aggregate information. In Proceedings 44th Symposium on Foundations of Computer Science (FOCS), pages 482-491, 2003. Google Scholar
  26. Fabian Kuhn, Thomas Locher, and Stefan Schmid. Distributed computation of the mode. In Proceedings of the 26th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 15-24, 2008. Google Scholar
  27. George B. Mertzios, Sotiris E. Nikoletseas, Christoforos 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), pages 871-882, 2014. Google Scholar
  28. Elchanan Mossel, Joe Neeman, and Omer Tamuz. Majority dynamics and aggregation of information in social networks. Autonomous Agents and Multi-Agent Systems, 28(3):408-429, 2014. URL: http://dx.doi.org/10.1007/s10458-013-9230-4.
  29. Elchanan Mossel and Grant Schoenebeck. Reaching consensus on social networks. In Innovations in Computer Science - (ICS), pages 214-229, 2010. Google Scholar
  30. David Peleg. Local majorities, coalitions and monopolies in graphs: a review. Theor. Comput. Sci., 282(2):231-257, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(01)00055-X.
  31. Etienne Perron, Dinkar Vasudevan, and Milan Vojnovic. Using three states for binary consensus on complete graphs. In 28th IEEE International Conference on Computer Communications, (INFOCOM), pages 2527-2535, 2009. Google Scholar
  32. Thomas Sauerwald and He Sun. Tight bounds for randomized load balancing on arbitrary network topologies. In 53rd Annual IEEE Symposium on Foundations of Computer Science, (FOCS), pages 341-350, 2012. Google Scholar
  33. Thomas Sauerwald and He Sun. Tight bounds for randomized load balancing on arbitrary network topologies. CoRR, abs/1201.2715, 2012. full version of FOCS'12. URL: http://arxiv.org/abs/1201.2715.
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