Name
Abstract | ||
|---|---|---|
The emph{Undecided-State Dynamics} is a well-known protocol that achieves emph{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 (say, colA and colB) or stay in the emph{undecided} state. 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. A major open question here is whether this dynamics reaches consensus emph{quickly}, i.e. within a polylogarithmic number of rounds. In this paper we present an textit{unconditional} analysis of the Undecided-State Dynamics which answers to the above question in the affermative. Our analysis shows that, starting from textit{any} initial configuration, the Undecided-State Dynamics reaches a monochromatic configuration within $O(log^2 n)$ rounds, with high probability (w.h.p.). %This bound is almost tight since a lower bound $Omega(log n)$ is known. Moreover, we prove that if the initial configuration has bias $Omega(sqrt{nlog 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 textit{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 textit{Population Protocols}) and/or symmetric updated rules (such as textit{majority} rules). |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Data Structures and Algorithms | Discrete mathematics,Complete graph,Binary logarithm,Population,Combinatorics,Upper and lower bounds,Omega,Mathematics,Consensus dynamics,Binary number |
DocType | Volume | Citations |
Journal | abs/1707.05135 | 1 |
PageRank | References | Authors |
0.35 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrea E. F. Clementi | 1 | 1168 | 85.30 |
| Luciano Gualà | 2 | 121 | 19.25 |
| Francesco Pasquale | 3 | 421 | 28.22 |
| Giacomo Scornavacca | 4 | 4 | 3.43 |