Paper Info
Title
The Power of Two Choices in Distributed Voting.
Abstract
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 Omega(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) sets A and B, respectively. Here, vertical bar A vertical bar + vertical bar B vertical bar = n is the number of vertices of the graph. We show that there is a constant K such that if the initial imbalance between the two opinions is nu(0) = (vertical bar A vertical bar -vertical bar B vertical bar)/n >= K root(1/d) + (d/n), then with high probability two sample voting completes in a random d regular graph in O(log n) steps and the initial majority opinion wins. We also show the same performance for any regular graph, if nu(0) >= K lambda(2), where lambda(2) is the second largest eigenvalue of the transition matrix. In the graphs we consider, standard pull voting requires O(n) steps, and the minority can still win with probability vertical bar B vertical bar/n.
Year
DOI
Venue
2014
10.1007/978-3-662-43951-7_37
Lecture Notes in Computer Science
DocType
Volume
ISSN
Journal
8573
0302-9743
Citations 
PageRank 
References 
20
1.21
17
Authors
3
Name
Order
Citations
PageRank
Colin Cooper185791.88
Robert Elsässer210413.93
Tomasz Radzik3109895.68