The Power of Two Choices in Distributed Voting
The Power of Two Choices in Distributed Voting
复制标题
DOI：
10.1007/978-3-662-43951-7_37
复制
发表时间：
2014-04
期刊：
影响因子：
--
通讯作者：
C. Cooper;Robert Elsässer;T. Radzik
中科院分区：
文献类型：
--
作者：
C. Cooper;Robert Elsässer;T. Radzik
分布式投票是分布式计算中的一个基本主题。在拉式投票中，每一步中每个顶点均匀随机选择一个邻居，并采纳其意见。当所有顶点意见一致时，投票结束。在包括常规图在内的许多图类上，拉动投票需要 Ω(n) 个预期步骤才能完成，即使最初只有两种不同的意见。在本文中，我们考虑一个称为双样本投票的相关过程：每个顶点在每个步骤中选择两个随机邻居。如果这些邻居的意见一致，则该顶点根据所选样本修改其意见。否则，它保留自己的意见。我们考虑在两个不同意见分别位于某些（任意）集合 A 和 B 的顶点上的情况下该过程的性能。在这里，|A| + |B| =n 是图的顶点数。我们证明存在一个常数 K，使得如果两种意见之间的初始不平衡为 ，则很有可能在随机正则图中以 O(logn) 步完成两个样本投票，并且初始多数意见获胜。我们还对任何正则图展示了相同的性能，如果ν0≥Kλ2，其中λ2是转移矩阵的第二大特征值。在我们考虑的图中，标准拉动投票需要 Ω(n) 个步骤，少数派仍然可以以 |B|/n 的概率获胜。
Distributed voting is a fundamental topic in distributed computing. In pull voting, in each step every vertex chooses a neighbour uniformly at random, and adopts its opinion. The voting is completed when all vertices hold the same opinion. On many graph classes including regular graphs, pull voting requires Ω(n) expected steps to complete, even if initially there are only two distinct opinions.In this paper we consider a related process which we call two-sample voting: every vertex chooses two random neighbours in each step. If the opinions of these neighbours coincide, then the vertex revises its opinion according to the chosen sample. Otherwise, it keeps its own opinion. We consider the performance of this process in the case where two different opinions reside on vertices of some (arbitrary) setsAandB, respectively. Here, |A| + |B| =nis the number of vertices of the graph.We show that there is a constantKsuch that if the initial imbalance between the two opinions is, then with high probability two sample voting completes in a randomdregular graph inO(logn) steps and the initial majority opinion wins. We also show the same performance for any regular graph, ifν0≥Kλ2, whereλ2is the second largest eigenvalue of the transition matrix. In the graphs we consider, standard pull voting requires Ω(n) steps, and the minority can still win with probability |B|/n.