English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

The \emph{Undecided-State Dynamics} is a well-known protocol for distributedconsensus. We analyze it in the parallel \pull\ communication model on thecomplete 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 completegraph with $n$ nodes. Previous work in this setting only considers initialcolor 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 theUndecided-State Dynamics that answers to the above question in the affirmative.We prove that, starting from \textit{any} initial configuration, the processreaches a monochromatic configuration within $O(\log n)$ rounds, with highprobability. This bound turns out to be tight. Our analysis also shows that, ifthe initial configuration has bias $\Omega(\sqrt{n\log n})$, then the dynamicsconverges toward the initial majority color, with high probability.

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