| Title | A Polylogarithmic Gossip Algorithm for Plurality Consensus |
| Publication Type | Conference Paper |
| Year of Publication | 2016 |
| Authors | Ghaffari, Mohsen, Parter, Merav |
| Conference Name | Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing |
| Publisher | ACM |
| Conference Location | New York, NY, USA |
| ISBN Number | 978-1-4503-3964-3 |
| Keywords | anonymous messaging, consensus, gossip algorithms, network dynamics, pubcrawl, Resiliency, scalabilty |
| 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. |
| URL | http://doi.acm.org/10.1145/2933057.2933097 |
| DOI | 10.1145/2933057.2933097 |
| Citation Key | ghaffari_polylogarithmic_2016 |
A Polylogarithmic Gossip Algorithm for Plurality Consensus