文章基本信息
- 标题：Quasi-Majority Functional Voting on Expander Graphs
- 本地全文：下载
- 作者：Nobutaka Shimizu ; Takeharu Shiraga
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：168
- 页码：97:1-97:19
- DOI：10.4230/LIPIcs.ICALP.2020.97
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：Consider a distributed graph where each vertex holds one of two distinct opinions. In this paper, we are interested in synchronous voting processes where each vertex updates its opinion according to a predefined common local updating rule. For example, each vertex adopts the majority opinion among 1) itself and two randomly picked neighbors in best-of-two or 2) three randomly picked neighbors in best-of-three. Previous works intensively studied specific rules including best-of-two and best-of-three individually. In this paper, we generalize and extend previous works of best-of-two and best-of-three on expander graphs by proposing a new model, quasi-majority functional voting. This new model contains best-of-two and best-of-three as special cases. We show that, on expander graphs with sufficiently large initial bias, any quasi-majority functional voting reaches consensus within O(log n) steps with high probability. Moreover, we show that, for any initial opinion configuration, any quasi-majority functional voting on expander graphs with higher expansion (e.g., ErdÅ's-Rényi graph G(n,p) with p = Ω(1/â^Sn)) reaches consensus within O(log n) with high probability. Furthermore, we show that the consensus time is O(log n/log k) of best-of-(2k+1) for k = o(n/log n).
- 关键词：Distributed voting; consensus problem; expander graph; Markov chain
