License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2017.47
URN: urn:nbn:de:0030-drops-79724
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7972/
Go to the corresponding LIPIcs Volume Portal

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

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

pdf-format:
LIPIcs-DISC-2017-47.pdf (0.4 MB)

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).

BibTeX - Entry

@InProceedings{clementi_et_al:LIPIcs:2017:7972,
  author =	{Andrea Clementi and Luciano Gual{\`a} and Francesco Pasquale and Giacomo Scornavacca},
  title =	{{Brief Announcement: On the Parallel Undecided-State Dynamics with Two Colors}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{47:1--47:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Andr{\'e}a W. Richa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7972},
  URN =		{urn:nbn:de:0030-drops-79724},
  doi =		{10.4230/LIPIcs.DISC.2017.47},
  annote =	{Keywords: Distributed Consensus, Dynamics, Gossip model, Markov chains}
}

Keywords: Distributed Consensus, Dynamics, Gossip model, Markov chains
Collection: 31st International Symposium on Distributed Computing (DISC 2017)
Issue Date: 2017
Date of publication: 12.10.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI