论文标题
quasi-mafority功能投票在扩展器图上
Quasi-majority Functional Voting on Expander Graphs
论文作者
论文摘要
考虑一个分布式图，每个顶点都有两个不同意见之一。在本文中，我们对同步投票过程感兴趣，在该过程中，每个顶点都根据预定义的常见本地更新规则更新其意见。例如，每个顶点在1）本身中采用多数意见，而两个在最佳两个中则随机挑选的邻居或2）三个随机挑选的邻居中的三个最佳邻居。以前的作品深入研究了特定的规则，包括两个单独的两个和三个最佳规则。 在本文中，我们通过提出了一种新的模型，即质量 - 多数功能投票，从而在扩展图上概括并扩展了以前的两个最佳和三个最佳作品。这种新模型包含最佳两个和三个最佳特殊情况。我们表明，在具有足够大的初始偏见的扩张器图上，任何准杂货功能投票都在$ O（\ log n）$ spep中达成共识，并具有很高的可能性。此外，我们表明，对于任何初始意见配置，在扩展较高的扩展图上进行的任何Quasi-majority函数投票（例如，Erdős-rényigraph $ g（n，p）$（n，p）$，$ p =ω（1/\ sqrt {n}）$在$ o（\ log log n）内与$ o（\ log n）中的共识。此外，我们表明共识时间为$ o（\ log n/\ log k）$ - $（2k+1）$ for $ k = o（n/\ log n）$。
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/\sqrt{n})$) 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)$.
