King's College London

Research portal

Fast plurality consensus in regular expanders

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Colin Cooper, Tomasz Radzik, Nicolás Rivera, Takeharu Shiraga

Original languageEnglish
Title of host publication31st International Symposium on Distributed Computing, DISC 2017
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770538
Publication statusE-pub ahead of print - 17 Oct 2017
Event31st International Symposium on Distributed Computing, DISC 2017 - Vienna, Austria
Duration: 16 Oct 201720 Oct 2017


Conference31st International Symposium on Distributed Computing, DISC 2017


King's Authors


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 two-sample 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 two-sample voting on d-regular graphs for this case. We show that, if the difference between the initial sizes A1 and A2 of the largest and second largest opinions is at least Cn max{ √ (log n)/A1, λ}, then the largest opinion wins in O((n log n)/A1) steps with high probability. Here C is a suitable constant and 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 three-sample voting process on complete graphs. Our bound implies that if λ = o(1), then the two-sample voting can consistently converge to the largest opinion, even if A1-A2 = o(n). If λ is constant, we show that the case A1 -A2 = 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.

Download statistics

No data available

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454