Skip to main content

Research Repository

Advanced Search

Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time

Berenbrink, Petra; Friedetzky, Tom; Giakkoupis, George; Kling, Peter

Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time Thumbnail


Authors

Petra Berenbrink

George Giakkoupis

Peter Kling



Contributors

Ioannis Chatzigiannakis
Editor

Michael Mitzenmacher
Editor

Yuval Rabani
Editor

Davide Sangiorgi
Editor

Abstract

Plurality consensus considers a network of n nodes, each having one of k opinions. Nodes execute a (randomized) distributed protocol with the goal that all nodes adopt the plurality (the opinion initially supported by the most nodes). Communication is realized via the Gossip (or random phone call) model. A major open question has been whether there is a protocol for the complete graph that converges (w.h.p.) in polylogarithmic time and uses only polylogarithmic memory per node (local memory). We answer this question affirmatively. We propose two protocols that need only mild assumptions on the bias in favor of the plurality. As an example of our results, consider the complete graph and an arbitrarily small constant multiplicative bias in favor of the plurality. Our first protocol achieves plurality consensus in O(log(k)*log(log(n))) rounds using log(k) + Theta(log(log(k))) bits of local memory. Our second protocol achieves plurality consensus in O(log(n)*log(log(n))) rounds using only log(k) + 4 bits of local memory. This disproves a conjecture by Becchetti et al. (SODA'15) implying that any protocol with local memory log(k)+O(1) has worst-case runtime Omega(k). We provide similar bounds for much weaker bias assumptions. At the heart of our protocols lies an undecided state, an idea introduced by Angluin et al. (Distributed Computing'08).

Citation

Berenbrink, P., Friedetzky, T., Giakkoupis, G., & Kling, P. (2016). Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time. In I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, & D. Sangiorgi (Eds.), 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) (1-14). https://doi.org/10.4230/lipics.icalp.2016.136

Conference Name 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Conference Location Rome, Italy
Acceptance Date Apr 14, 2016
Online Publication Date Aug 1, 2016
Publication Date Aug 1, 2016
Deposit Date Oct 17, 2016
Publicly Available Date Oct 21, 2016
Pages 1-14
Series Title Leibniz International Proceedings in Informatics (LIPIcs)
Series Number 55
Series ISSN 1868-8969
Book Title 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
DOI https://doi.org/10.4230/lipics.icalp.2016.136
Public URL https://durham-repository.worktribe.com/output/1149747
Additional Information Conference date: 11-15 July 2016

Files





You might also like



Downloadable Citations