research-article

Public Access

A Polylogarithmic Gossip Algorithm for Plurality Consensus

Authors:

Mohsen Ghaffari,

Merav ParterAuthors Info & Claims

PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

Pages 117 - 126

https://doi.org/10.1145/2933057.2933097

Published: 25 July 2016 Publication History

Abstract

Consider n anonymous nodes each initially supporting an opinion in {1, 2, …, k} and suppose that they should all learn the opinion with the largest support. Per round, each node contacts a random other node and exchanges B bits with it, where typically B is at most O(log n).

This basic distributed computing problem is called the plurality consensus problem (in the gossip model) and it has received extensive attention. An efficient plurality protocol is one that converges to the plurality consensus as fast as possible, and the standard assumption is that each node has memory at most polylogarithmic in n. The best known time bound is due to Becchetti et al. [SODA'15], reaching plurality consensus in O(k log n) rounds using log(k+1) bits of local memory, under some mild assumptions. As stated by Becchetti et al., achieving a poly-logarithmic time complexity remained an open question.

Resolving this question, we present an algorithm that with high probability reaches plurality consensus in O(log k log n) rounds, while having message and memory size of log k + O (1) bits. This even holds under considerably more relaxed assumptions regarding the initial bias (towards plurality) compared to those of prior work. The algorithm is based on a very simple and arguably natural mechanism.

References

[1]

Dana Angluin, James Aspnes, Zoë Diamadi, Michael J Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed computing, 18(4):235--253, 2006.

Digital Library

[2]

Dana Angluin, James Aspnes, and David Eisenstat. A simple population protocol for fast robust approximate majority. Distributed Computing, 21(2):87--102, 2008.

[3]

Dana Angluin, Michael J Fischer, and Hong Jiang. Stabilizing consensus in mobile networks. In Distributed Computing in Sensor Systems, pages 37--50. Springer, 2006.

Digital Library

[4]

Dan Alistarh, Rati Gelashvili, and Milan Vojnovic. Fast and exact majority in population protocols. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp.(PODC), pages 47--56, 2015.

Digital Library

[5]

Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, and Luca Trevisan. Simple dynamics for plurality consensus. In Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures, pages 247--256. ACM, 2014.

Digital Library

[6]

L Becchetti, A Clementi, E Natale, F Pasquale, and R Silvestri. Plurality consensus in the gossip model. In Pro. of ACM-SIAM Symp. on Disc. Alg. (SODA), pages 371--390, 2015.

Digital Library

[7]

Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan. Stabilizing consensus with many opinions. to appear at SODA'16, arXiv preprint arXiv:1508.06782, 2015.

Digital Library

[8]

Petra Berenbrink, Tom Friedetzky, George Giakkoupis, and Peter Kling. Efficient plurality consensus, or: The benefits of cleaning up from time to time. In the Pro. of the Int'l Colloquium on Automata, Languages and Programming (ICALP), page to appear, 2016.

[9]

Radu Berinde, Piotr Indyk, Graham Cormode, and Martin J Strauss. Space-optimal heavy hitters with strong error bounds. ACM Transactions on Database Systems (TODS), 35(4):26, 2010.

Digital Library

[10]

Ohad Ben-Shahar, Shlomi Dolev, Andrey Dolgin, and Michael Segal. Direction election in flocking swarms. Ad Hoc Networks, 12:250--258, 2014.

Digital Library

[11]

Luca Cardelli and Attila Csikász-Nagy. The cell cycle switch computes approximate majority. Scientific reports, 2, 2012.

[12]

Yuan-Jyue Chen, Neil Dalchau, Niranjan Srinivas, Andrew Phillips, Luca Cardelli, David Soloveichik, and Georg Seelig. Programmable chemical controllers made from DNA. Nature nanotechnology, 8(10):755--762, 2013.

[13]

Iain D Couzin, Jens Krause, Nigel R Franks, and Simon A Levin. Effective leadership and decision-making in animal groups on the move. Nature, 433(7025):513--516, 2005.

[14]

Matthew Cook, David Soloveichik, Erik Winfree, and Jehoshua Bruck. Programmability of chemical reaction networks. In Algorithmic Bioprocesses, pages 543--584. Springer, 2009.

[15]

Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, and Christian Scheideler. Stabilizing consensus with the power of two choices. In Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures, pages 149--158. ACM, 2011.

Digital Library

[16]

David Doty. Timing in chemical reaction networks. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 772--784. SIAM, 2014.

Digital Library

[17]

Moez Draief and Milan Vojnovic. Convergence speed of binary interval consensus. SIAM Journal on Control and Optimization, 50(3):1087--1109, 2012.

[18]

Peter Donnelly and Dominic Welsh. Finite particle systems and infection models. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 94, pages 167--182. Cambridge Univ Press, 1983.

[19]

John Hopcroft. An $n łog n$ algorithm for minimizing states in a finite automaton. Theory of Machines and Computations, pages 189--196, 1971.

[20]

Yehuda Hassin and David Peleg. Distributed probabilistic polling and applications to proportionate agreement. Information and Computation, 171(2):248--268, 2001.

Digital Library

[21]

David Kempe, Alin Dobra, and Johannes Gehrke. Gossip-based computation of aggregate information. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS), pages 482--491, 2003.

Digital Library

[22]

Thomas Liggett. Interacting particle systems, volume 276. Springer Science & Business Media, 2012.

[23]

Nancy A Lynch. Distributed algorithms. Morgan Kaufmann, 1996.

Digital Library

[24]

George B Mertzios, Sotiris E Nikoletseas, Christoforos L Raptopoulos, and Paul G Spirakis. Determining majority in networks with local interactions and very small local memory. In Automata, Languages, and Programming, pages 871--882. Springer, 2014.

[25]

Elchanan Mossel and Grant Schoenebeck. Reaching consensus on social networks.

[26]

Etienne Perron, Dinkar Vasudevan, and Milan Vojnovic. Using three states for binary consensus on complete graphs. In the Proc. of IEEE INFOCOM, pages 2527--2535, 2009.

[27]

David JT Sumpter, Jens Krause, Richard James, Iain D Couzin, and Ashley JW Ward. Consensus decision making by fish. Current Biology, 18(22):1773--1777, 2008.

[28]

H. Spencer. The Principles of Biology. Number v. 1 in Spencer, Herbert: A system of synthetic philosophy. Williams and Norgate, 1864.

[29]

J. N. Tsitsiklis, D. P. Bertsekas, and M. Athans. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE transactions on automatic control, 31(9):803--812, 1986.

[30]

John Nikolas Tsitsiklis. Problems in decentralized decision making and computation. Technical report, DTIC Document, 1984.

[31]

Fang Wu and Bernardo A Huberman. Social structure and opinion formation. arXiv preprint cond-mat/0407252, 2004.

[32]

Sheng Yu. State complexity: Recent results and open problems. Fundamenta Informaticae, 64(1--4):471--480, 2005.

Digital Library

Cited By

d'Amore FZiccardi I(2024)Phase Transition of the 3-Majority Dynamics with Uniform Communication NoiseTheoretical Computer Science10.1016/j.tcs.2024.115030(115030)Online publication date: Dec-2024
https://doi.org/10.1016/j.tcs.2024.115030
Berenbrink PHoefer MKaaser DLenzner PRau MSchmand D(2024)Asynchronous opinion dynamics in social networksDistributed Computing10.1007/s00446-024-00467-337:3(207-224)Online publication date: 26-Apr-2024
https://doi.org/10.1007/s00446-024-00467-3
Berenbrink PCooper CGava CMarzagão DMallmann-Trenn FRadzik TRivera NOshman RNolin AHalldorsson MBalliu A(2023)Distributed Averaging in Opinion DynamicsProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594593(211-221)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594593
Show More Cited By

Index Terms

A Polylogarithmic Gossip Algorithm for Plurality Consensus
1. Networks
  1. Network algorithms
  2. Network properties
    1. Network dynamics
2. Theory of computation
  1. Design and analysis of algorithms
    1. Distributed algorithms

Recommendations

Faster randomized consensus with an oblivious adversary

Two new algorithms are given for randomized consensus in a shared-memory model with an oblivious adversary. Each is based on a new construction of a conciliator, an object that guarantees termination and validity, but that only guarantees agreement with ...
Plurality consensus in the gossip model
SODA '15: Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms

We study Plurality Consensus in the GOSSIP Model over a network of n anonymous agents. Each agent supports an initial opinion or color. We assume that at the onset, the number of agents supporting the plurality color exceeds that of the agents ...
On the complexity of asynchronous gossip
PODC '08: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing

In this paper, we study the complexity of gossip in an asynchronous, message-passing fault-prone distributed system. In short, we show that an adaptive adversary can significantly hamper the spreading of a rumor, while an oblivious adversary cannot. ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

July 2016

508 pages

ISBN:9781450339643

DOI:10.1145/2933057

General Chair:
George Giakkoupis
INRIA, France

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation
AFOSR

Conference

PODC '16

Sponsor:

PODC '16: ACM Symposium on Principles of Distributed Computing

July 25 - 28, 2016

Illinois, Chicago, USA

Acceptance Rates

PODC '16 Paper Acceptance Rate 40 of 149 submissions, 27%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
611
Total Downloads

Downloads (Last 12 months)73
Downloads (Last 6 weeks)14

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

d'Amore FZiccardi I(2024)Phase Transition of the 3-Majority Dynamics with Uniform Communication NoiseTheoretical Computer Science10.1016/j.tcs.2024.115030(115030)Online publication date: Dec-2024
https://doi.org/10.1016/j.tcs.2024.115030
Berenbrink PHoefer MKaaser DLenzner PRau MSchmand D(2024)Asynchronous opinion dynamics in social networksDistributed Computing10.1007/s00446-024-00467-337:3(207-224)Online publication date: 26-Apr-2024
https://doi.org/10.1007/s00446-024-00467-3
Berenbrink PCooper CGava CMarzagão DMallmann-Trenn FRadzik TRivera NOshman RNolin AHalldorsson MBalliu A(2023)Distributed Averaging in Opinion DynamicsProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594593(211-221)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594593
Amir TAspnes JBerenbrink PBiermeier FHahn CKaaser DLazarsfeld JOshman RNolin AHalldorsson MBalliu A(2023)Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol ModelProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594589(13-23)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594589
Li FYuan XWang LYang HYu DLyu WCheng X(2023)Collaborative Learning in General Graphs With Limited Memorization: Complexity, Learnability, and ReliabilityIEEE/ACM Transactions on Networking10.1109/TNET.2023.327350131:6(3222-3237)Online publication date: Dec-2023
https://doi.org/10.1109/TNET.2023.3273501
Berenbrink PHoefer MKaaser DLenzner PRau MSchmand DPelachaud CTaylor MFaliszewski PMascardi V(2022)Asynchronous Opinion Dynamics in Social NetworksProceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems10.5555/3535850.3535864(109-117)Online publication date: 9-May-2022
https://dl.acm.org/doi/10.5555/3535850.3535864
d’Amore FClementi ANatale E(2022)Phase transition of a nonlinear opinion dynamics with noisy interactionsSwarm Intelligence10.1007/s11721-022-00217-w16:4(261-304)Online publication date: 17-Nov-2022
https://doi.org/10.1007/s11721-022-00217-w
Alistarh DTöpfer MUznański PMiller ACensor-Hillel K(2021)Comparison Dynamics in Population ProtocolsProceedings of the 2021 ACM Symposium on Principles of Distributed Computing10.1145/3465084.3467915(55-65)Online publication date: 21-Jul-2021
https://dl.acm.org/doi/10.1145/3465084.3467915
Cruciani ENatale ENusser AScornavacca G(2021)Phase transition of the 2-Choices dynamics on core–periphery networksDistributed Computing10.1007/s00446-021-00396-5Online publication date: 26-May-2021
https://doi.org/10.1007/s00446-021-00396-5
Bankhamer GElsässer RKaaser DKrnc MEmek YCachin C(2020)Positive Aging Admits Fast Asynchronous Plurality ConsensusProceedings of the 39th Symposium on Principles of Distributed Computing10.1145/3382734.3406506(385-394)Online publication date: 31-Jul-2020
https://dl.acm.org/doi/10.1145/3382734.3406506
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten