Petra Berenbrink
Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time
Berenbrink, Petra; Friedetzky, Tom; Giakkoupis, George; Kling, Peter
Authors
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).
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) |
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
Published Conference Proceeding
(644 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© Petra Berenbrink, Tom Friedetzky, George Giakkoupis, and Peter Kling; licensed under Creative Commons License CC-BY.
You might also like
Payment scheduling in the Interval Debt Model
(2023)
Presentation / Conference Contribution
Infinite Balanced Allocation via Finite Capacities
(2021)
Presentation / Conference Contribution
Tight & Simple Load Balancing
(2019)
Presentation / Conference Contribution
A population protocol for exact majority with $O(\log^{5/3} n)$ stabilization time and asymptotically optimal number of states
(2018)
Presentation / Conference Contribution
Infinite parallel job allocation (extended abstract)
(2000)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search