Brief announcement: Rapid asynchronous plurality consensus

DOI10.1145/3087801.3087860zbMATH Open1380.68048arXiv1602.04667OpenAlexW2625096483MaRDI QIDQ5368985FDOQ5368985

Robert Elsässer, Horst Trinker, Frederik Mallmann-Trenn, Tom Friedetzky, Dominik Kaaser

Publication date: 11 October 2017

Published in: Proceedings of the ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Abstract: We consider distributed plurality consensus in a complete graph of size $n$ with $k$ initial opinions. We design an efficient and simple protocol in the asynchronous communication model that ensures that all nodes eventually agree on the initially most frequent opinion. In this model, each node is equipped with a random Poisson clock with parameter $lambda=1$. Whenever a node's clock ticks, it samples some neighbors, uniformly at random and with replacement, and adjusts its opinion according to the sample. A prominent example is the so-called two-choices algorithm in the synchronous model, where in each round, every node chooses two neighbors uniformly at random, and if the two sampled opinions coincide, then that opinion is adopted. This protocol is very efficient and well-studied when $k=2$. If $k=O(n^{v}arepsilon)$ for some small $varepsilon$, we show that it converges to the initial plurality opinion within $O(kcdotlogn)$ rounds, w.h.p., as long as the initial difference between the largest and second largest opinion is $Omega(sqrtnlogn)$. On the other side, we show that there are cases in which $Omega(k)$ rounds are needed, w.h.p. One can beat this lower bound in the synchronous model by combining the two-choices protocol with randomized broadcasting. Our main contribution is a non-trivial adaptation of this approach to the asynchronous model. If the support of the most frequent opinion is at least $(1+varepsilon)$ times that of the second-most frequent one and $k=O(exp(logn/loglogn))$, then our protocol achieves the best possible run time of $O(logn)$, w.h.p. We relax full synchronicity by allowing $o(n)$ nodes to be poorly synchronized, and the well synchronized nodes are only required to be within a certain time difference from one another. We enforce this synchronicity by introducing a novel gadget into the protocol.

Full work available at URL: https://arxiv.org/abs/1602.04667

Recommendations

• Efficient plurality consensus, or: the benefits of cleaning up from time to time
• A polylogarithmic gossip algorithm for plurality consensus
• Plurality consensus in the gossip model
• Plurality consensus in arbitrary graphs: lessons learned from load balancing
• Simple dynamics for plurality consensus

zbMATH Keywords

asynchronicitydistributed randomized algorithmsplurality consensus

Mathematics Subject Classification ID

Randomized algorithms (68W20) Distributed algorithms (68W15) Distributed systems (68M14)

Cited In (3)

• Noisy rumor spreading and plurality consensus
• Fast plurality consensus in regular expanders
• Phase transition of the \(k\)-majority dynamics in biased communication models

This page was built for publication: Brief announcement: Rapid asynchronous plurality consensus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368985)