Name
Abstract | ||
|---|---|---|
The emph{Undecided-State Dynamics} is a well-known protocol for distributed consensus. We analyze it in the parallel pull communication model on the complete graph for the emph{binary} case (every node can either support one of emph{two} possible colors, or be in the undecided state). An interesting open question is whether this dynamics emph{always} (i.e., starting from an arbitrary initial configuration) reaches consensus emph{quickly} (i.e., within a polylogarithmic number of rounds) in a complete graph with $n$ nodes. Previous work in this setting only considers initial color configurations with no undecided nodes and a large emph{bias} (i.e., $Theta(n)$) towards the majority color. In this paper we present an textit{unconditional} analysis of the Undecided-State Dynamics that answers to the above question in the affirmative. We prove that, starting from textit{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{nlog n})$, then the dynamics converges toward the initial majority color, with high probability. |
Year | Venue | Field |
|---|---|---|
2018 | MFCS | Consensus,Discrete mathematics,Complete graph,Binary logarithm,Monochromatic color,Combinatorics,Computer science,Models of communication,Omega,Time complexity,Binary number |
DocType | Citations | PageRank |
Conference | 1 | 0.35 |
References | Authors | |
0 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrea E. F. Clementi | 1 | 1168 | 85.30 |
| Mohsen Ghaffari | 2 | 452 | 44.89 |
| Luciano Gualà | 3 | 121 | 19.25 |
| Emanuele Natale | 4 | 74 | 14.52 |
| Francesco Pasquale | 5 | 421 | 28.22 |
| Giacomo Scornavacca | 6 | 4 | 3.43 |