Document Open Access Logo

A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors

Authors Andrea Clementi, Mohsen Ghaffari, Luciano Gualà, Emanuele Natale, Francesco Pasquale, Giacomo Scornavacca

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.28.pdf
  • Filesize: 0.61 MB
  • 15 pages

Document Identifiers

Author Details

Andrea Clementi
  • Università Tor Vergata di Roma, Italy
Mohsen Ghaffari
  • ETH Zürich, Switzerland
Luciano Gualà
  • Università Tor Vergata di Roma, Italy
Emanuele Natale
  • Max Planck Institute for Informatics, Germany
Francesco Pasquale
  • Università Tor Vergata di Roma, Italy
Giacomo Scornavacca
  • Università degli Studi dell'Aquila, Italy

Funding

  • Pasquale, Francesco: Partly supported by the University of "Tor Vergata" under research programme "Mission: Sustainability" project ISIDE (grant no. E81I18000110005)

Cite As Get BibTex

Andrea 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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.28

Abstract

The Undecided-State Dynamics is a well-known protocol for distributed consensus. We analyze it in the parallel PULL communication model on the complete graph with n nodes for the binary case (every node can either support one of two possible colors, or be in the undecided state).
An interesting open question is whether this dynamics is an efficient Self-Stabilizing protocol, namely, starting from an arbitrary initial configuration, it reaches consensus quickly (i.e., within a polylogarithmic number of rounds). Previous work in this setting only considers initial color configurations with no undecided nodes and a large bias (i.e., Theta(n)) towards the majority color.
In this paper we present an unconditional analysis of the Undecided-State Dynamics that answers to the above question in the affirmative. We prove that, starting from any initial configuration, the process reaches a monochromatic configuration within O(log n) rounds, with high probability. This bound turns out to be tight. Our analysis also shows that, if the initial configuration has bias Omega(sqrt(n log n)), then the dynamics converges toward the initial majority color, with high probability.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Distributed Consensus
  • Self-Stabilization
  • PULL Model
  • Markov Chains

Metrics

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

Related Versions

References

  1. Mohammed Amin Abdullah and Moez Draief. Global majority consensus by local majority polling on graphs of a given degree sequence. Discrete Applied Mathematics, 180:1-10, 2015. Google Scholar
  2. Dana Angluin, James Aspnes, and David Eisenstat. A Simple Population Protocol for Fast Robust Approximate Majority. Distributed Computing, 21(2):87-102, 2008. (Preliminary version in DISC'07). Google Scholar
  3. Arta Babaee and Moez Draief. Distributed Multivalued Consensus. In Computer and Information Sciences III, pages 271-279. Springer, 2013. Google Scholar
  4. Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Riccardo Silvestri. Plurality Consensus in the Gossip Model. In ACM-SIAM SODA'15, pages 371-390, 2015. Google Scholar
  5. Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, and Luca Trevisan. Simple dynamics for plurality consensus. In ACM SPAA'14, pages 247-256, 2014. Google Scholar
  6. Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan. Stabilizing consensus with many opinions. In ACM-SIAM SODA'16, pages 620-635, 2016. Google Scholar
  7. Florence Bénézit, Patrick Thiran, and Martin Vetterli. Interval consensus: from quantized gossip to voting. In IEEE ICASSP'09, pages 3661-3664, 2009. Google Scholar
  8. Petra Berenbrink, Andrea Clementi, Peter Kling, Robert Elsässer, Frederik Mallmann-Trenn, and Emanuele Natale. Ignore or Comply? On Breaking Symmetry in Consensus. In ACM PODC'17, pages 335-344, 2017. (Tech. Rep. in arXiv:1702.04921 [cs.DC]). Google Scholar
  9. Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec, and Frederik Mallmann-Trenn. Bounds on the Voter Model in Dynamic Networks. In ICALP'16, 2016. Google Scholar
  10. Alan A. Berryman and Pavel Kindlmann. Population Systems: A General Introduction. Springer, 2008. Google Scholar
  11. Luca Cardelli and Attila Csikász-Nagy. The cell cycle switch computes approximate majority. Scientific Reports, Vol. 2, 2012. Google Scholar
  12. Keren Censor-Hillel, Bernhard Haeupler, Jonathan Kelner, and Petar Maymounkov. Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance. In ACM STOC'12, pages 961-970, 2012. Google Scholar
  13. Bernard Chazelle. Natural Algorithms and Influence Systems. Commun. ACM, 55(12):101-110, 2012. Google Scholar
  14. Andrea Clementi, Mohsen Ghaffari, Luciano Gualà, Emanuele Natale, Francesco Pasquale, and Giacomo Scornavacca. A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors. CoRR, abs/1707.05135v3, 2018. URL: https://arxiv.org/abs/1707.05135v3.
  15. Colin Cooper, Robert Elsässer, and Tomasz Radzik. The Power of Two Choices in Distributed Voting. In ICALP'14, pages 435-446, 2014. Google Scholar
  16. Colin Cooper, Robert Elsässer, Tomasz Radzik, Nicolas Rivera, and Takeharu Shiraga. Fast Consensus for Voting on General Expander Graphs. In DISC'15, pages 248-262, 2015. Google Scholar
  17. Alan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swinehart, and Doug Terry. Epidemic algorithms for replicated database maintenance. In ACM PODC'87, pages 1-12, 1987. Google Scholar
  18. Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, and Christian Scheideler. Stabilizing consensus with the power of two choices. In ACM SPAA'11, pages 149-158, 2011. Google Scholar
  19. David Doty. Timing in chemical reaction networks. In ACM-SIAM SODA'14, pages 772-784, 2014. Google Scholar
  20. Moez Draief and Milan Vojnović. Convergence speed of binary interval consensus. SIAM Journal on Control and Optimisation, 50(3):1087-1109, 2012. Google Scholar
  21. Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009. Google Scholar
  22. Mohsen Ghaffari and Johannes Lengler. Tight analysis for the 3-majority consensus dynamics. CoRR, abs/1705.05583, 2017. URL: http://arxiv.org/abs/1705.05583.
  23. Yehuda Hassin and David Peleg. Distributed probabilistic polling and applications to proportionate agreement. Information and Computation, 171(2):248-268, 2001. Google Scholar
  24. David Kempe, Alin Dobra, and Johannes Gehrke. Gossip-based computation of aggregate information. In IEEE FOCS'03, pages 482-491, 2003. Google Scholar
  25. David Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2008. Google Scholar
  26. Thomas M. Liggett. Stochastic Interacting Systems: Contact, Voter and Exclusion Processes. Springer-Verlag, 1999. 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 ICALP'14, 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. Google Scholar
  29. Saket Navlakha and Ziv Bar-Joseph. Algorithms in nature: the convergence of systems biology and computational thinking. Mol. Syst. Biol., 7, 2011. Google Scholar
  30. Marshall Pease, Robert Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. Journal of the ACM, 27(2):228-234, 1980. Google Scholar
  31. Etienne Perron, Dinkar Vasudevan, and Milan Vojnovic. Using Three States for Binary Consensus on Complete Graphs. In IEEE INFOCOM'09, pages 2527-1535, 2009. 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 About DROPS Imprint Privacy Contact