Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

Original language | English |
---|---|

Title of host publication | 31st International Symposium on Distributed Computing, DISC 2017 |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Volume | 91 |

ISBN (Electronic) | 9783959770538 |

DOIs | |

Publication status | E-pub ahead of print - 17 Oct 2017 |

Event | 31st International Symposium on Distributed Computing, DISC 2017 - Vienna, Austria Duration: 16 Oct 2017 → 20 Oct 2017 |

Conference | 31st International Symposium on Distributed Computing, DISC 2017 |
---|---|

Country | Austria |

City | Vienna |

Period | 16/10/2017 → 20/10/2017 |

**Fast plurality consensus in_COOPER_Published2017_GOLD VoR (CC BY)**Fast_plurality_consensus_in_COOPER_Published2017_GOLD_VoR_CC_BY_.pdf, 523 KB, application/pdf

13/11/2017

Final published version

CC BY

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 A_{1} and A_{2} of the largest and second largest opinions is at least Cn max{ √ (log n)/A_{1}, λ}, then the largest opinion wins in O((n log n)/A_{1}) 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 A_{1}-A_{2} = o(n). If λ 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.

No data available

King's College London - Homepage

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