Brief Announcement: On the Parallel Undecided-State Dynamics with Two Colors

Authors Andrea Clementi, Luciano Gualà, Francesco Pasquale, Giacomo Scornavacca



PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.47.pdf
  • Filesize: 408 kB
  • 4 pages

Document Identifiers

Author Details

Andrea Clementi
Luciano Gualà
Francesco Pasquale
Giacomo Scornavacca

Cite AsGet BibTex

Andrea Clementi, Luciano Gualà, Francesco Pasquale, and Giacomo Scornavacca. Brief Announcement: On the Parallel Undecided-State Dynamics with Two Colors. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 47:1-47:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.DISC.2017.47

Abstract

The Undecided-State Dynamics is a well-known protocol that achieves Consensus in distributed systems formed by a set of n anonymous nodes interacting via a communication network. We consider this dynamics in the parallel PULL communication model on the complete graph for the binary case, i.e., when every node can either support one of two possible colors or stay in the undecided state. 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. A interesting open question here is whether this dynamics reaches consensus quickly, i.e. within a polylogarithmic number of rounds. In this paper we present an unconditional analysis of the Undecided-State Dynamics which answers to the above question in the affirmative. Our analysis shows that, starting from any initial configuration, the Undecided-State Dynamics reaches a monochromatic configuration within O(log^2 n) rounds, with high probability (w.h.p.). Moreover, we prove that if the initial configuration has bias Omega(sqrt(n log n)), then the dynamics converges toward the initial majority color within O(log n) round, w.h.p. At the heart of our approach there is a new analysis of the symmetry-breaking phase that the process must perform in order to escape from (almost-)unbiased configurations. Previous symmetry-breaking analysis of consensus dynamics essentially concern sequential communication models (such as Population Protocols) and/or symmetric updated rules (such as majority rules).
Keywords
  • Distributed Consensus
  • Dynamics
  • Gossip model
  • Markov chains

Metrics

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

References

  1. M. A. Abdullah et al. Majority consensus on random graphs of a given degree sequence. arXiv:1209.5025, 2012. Google Scholar
  2. Mohammed Amin Abdullah et al. Global majority consensus by local majority polling on graphs of a given degree sequence. Discrete Applied Mathematics, 180, 2015. Google Scholar
  3. Dana Angluin et al. A Simple Population Protocol for Fast Robust Approximate Majority. Distributed Computing, 21(2), 2008. Google Scholar
  4. A. Babaee et al. Distributed multivalued consensus. In Computer and Information Sciences III. Springer, 2013. Google Scholar
  5. Luca Becchetti et al. Plurality consensus in the gossip model. In ACM-SIAM SODA'15, 2015. Google Scholar
  6. F. Bénézit et al. Interval consensus: from quantized gossip to voting. In IEEE ICASSP'09, 2009. Google Scholar
  7. L. Cardelli et al. The cell cycle switch computes approximate majority. Scientific Reports, Vol. 2, 2012. Google Scholar
  8. K. Censor-Hillel et al. Global computation in a poorly connected world: Fast rumor spreading with no dependence on conductance. In ACM STOC'12, 2012. Google Scholar
  9. C. Cooper et al. The power of two choices in distributed voting. In ICALP'14, 2014. Google Scholar
  10. A. Demers et al. Epidemic algorithms for replicated database maintenance. In ACM PODC'87, 1987. Google Scholar
  11. Benjamin Doerr et al. Stabilizing consensus with the power of two choices. In ACM SPAA'11, 2011. Google Scholar
  12. David Doty. Timing in chemical reaction networks. In ACM-SIAM SODA'14, 2014. Google Scholar
  13. Moez Draief et al. Convergence speed of binary interval consensus. SIAM Journal on Control and Optimisation, 50(3), 2012. Google Scholar
  14. D. Kempe et al. Gossip-based computation of aggregate information. In IEEE FOCS'03, 2003. Google Scholar
  15. George B. Mertzios et al. Determining majority in networks with local interactions and very small local memory. In ICALP'14, 2014. Google Scholar
  16. Elchanan Mossel et al. Majority dynamics and aggregation of information in social networks. Autonomous Agents and Multi-Agent Systems, 28(3), 2014. URL: http://dx.doi.org/10.1007/s10458-013-9230-4.
  17. Etienne Perron et al. Using Three States for Binary Consensus on Complete Graphs. In INFOCOM'09, 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