文章基本信息

标题：A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors
本地全文：下载
作者：Andrea Clementi ; Mohsen Ghaffari ; Luciano Gual{\`a 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：117
页码：1-15
DOI：10.4230/LIPIcs.MFCS.2018.28
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Distributed Consensus; Self-Stabilization; PULL Model; Markov Chains