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.MFCS.2018.28
URN: urn:nbn:de:0030-drops-96107
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9610/
Go to the corresponding LIPIcs Volume Portal

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

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

pdf-format:
LIPIcs-MFCS-2018-28.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{clementi_et_al:LIPIcs:2018:9610,
  author =	{Andrea Clementi and Mohsen Ghaffari and Luciano Gual{\`a} and Emanuele Natale and Francesco Pasquale and Giacomo Scornavacca},
  title =	{{A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors}},
  booktitle =	{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9610},
  URN =		{urn:nbn:de:0030-drops-96107},
  doi =		{10.4230/LIPIcs.MFCS.2018.28},
  annote =	{Keywords: Distributed Consensus, Self-Stabilization, PULL Model, Markov Chains}
}

Keywords: Distributed Consensus, Self-Stabilization, PULL Model, Markov Chains
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

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