Abstract
In a voting process on a graph vertices revise their opinions in a distributed way based on the opinions of nearby vertices. The voting completes when the vertices reach consensus, that is, they all have the same opinion. The classic example is synchronous pull voting where at each step, each vertex adopts the opinion of a random neighbour. This very simple process, however, can be slow and the final opinion is not necessarily the one with the initial largest support. It was shown earlier that if there are initially only two opposing opinions, then both these drawbacks can be overcome by a synchronous twosample voting, in which at each step each vertex considers its own opinion and the opinions of two random neighbours.
If there are initially three or more opinions, a problem arises when there is no clear majority. One class of opinions may be largest (the plurality opinion), although its total size is less than that of two other opinions put together. We analyse the performance of the twosample voting on dregular graphs for this case. We show that, if the difference between the initial sizes A_1 and A_2 of the largest and second largest opinions is at least C n max{sqrt((log n)/A_1), lambda}, then the largest opinion wins in O((n log n)/A_1) steps with high probability. Here C is a suitable constant and lambda is the absolute second eigenvalue of transition matrix P=Adj(G)/d of a simple random walk on the graph G. Our bound generalizes the results of Becchetti et al. [SPAA 2014] for the related threesample voting process on complete graphs. Our bound implies that if lambda = o(1), then the twosample voting can consistently converge to the largest opinion, even if A_1  A_2 = o(n). If lambda is constant, we show that the case A_1  A_2 = o(n) can be dealt with by sampling using short random walks. Finally, we give a simple and efficient push voting algorithm for the case when there are a number of large opinions and any of them is acceptable as the final winning opinion.
BibTeX  Entry
@InProceedings{cooper_et_al:LIPIcs:2017:7977,
author = {Colin Cooper and Tomasz Radzik and Nicol{\'a}s Rivera and Takeharu Shiraga},
title = {{Fast Plurality Consensus in Regular Expanders}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {13:113:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770538},
ISSN = {18688969},
year = {2017},
volume = {91},
editor = {Andr{\'e}a W. Richa},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7977},
URN = {urn:nbn:de:0030drops79778},
doi = {10.4230/LIPIcs.DISC.2017.13},
annote = {Keywords: Plurality consensus, Regular expanders}
}
Keywords: 

Plurality consensus, Regular expanders 
Collection: 

31st International Symposium on Distributed Computing (DISC 2017) 
Issue Date: 

2017 
Date of publication: 

12.10.2017 