A polylogarithmic gossip algorithm for plurality consensus

DOI10.1145/2933057.2933097MaRDI QIDQ5361925zbMATH OpenOpenAlexFDO

Authors Mohsen Ghaffari, M. Parter

Publication date 29 September 2017

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

Full work available at URL https://doi.org/10.1145/2933057.2933097

zbMATH Keywords

consensusnetwork dynamicsgossip algorithms

Mathematics Subject Classification ID

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

Recommendations

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

Cited in

(18)

• Broadcast Gossip Algorithms for Consensus
• Noisy rumor spreading and plurality consensus
• Game dynamics and equilibrium computation in the population protocol model
• Plurality consensus in the gossip model
• A population protocol for exact majority with \(O(\log^{5/3} n)\) stabilization time and \(\Theta(\log n)\) states
• Asynchronous opinion dynamics in social networks
• Restorable shortest path tiebreaking for edge-faulty graphs
• Almost-optimal gossip-based aggregate computation
• Asynchronous majority dynamics in preferential attachment trees
• Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model
• Distributed Averaging in Opinion Dynamics
• The Maximum Label Propagation Algorithm on Sparse Random Graphs
• Phase transition of the 3-majority opinion dynamics with noisy interactions
• Asynchronous majority dynamics on binomial random graphs
• Plurality consensus in arbitrary graphs: lessons learned from load balancing
• Brief announcement: Rapid asynchronous plurality consensus
• Efficient plurality consensus, or: the benefits of cleaning up from time to time
• Phase transition of the 2-choices dynamics on core-periphery networks

This page was built for publication: A polylogarithmic gossip algorithm for plurality consensus

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