Simple dynamics for plurality consensus

DOI10.1007/s00446-016-0289-4zbMath1419.68027arXiv1310.2858OpenAlexW2551916216WikidataQ58219115 ScholiaQ58219115MaRDI QIDQ2401681

Luca Becchetti, Riccardo Silvestri, Luca Trevisan, Emanuele Natale, Andrea E. F. Clementi, Francesco Pasquale

Publication date: 4 September 2017

Published in: Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

dynamicsMarkov chainsdistributed randomized algorithmsplurality consensus

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Distributed systems (68M14) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items

On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols, An elementary analysis of the probability that a binomial random variable exceeds its expectation, Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models, Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication, Phase transition of the \(k\)-majority dynamics in biased communication models, Convex transform order of Beta distributions with some consequences, Unnamed Item, Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model, The Maximum Label Propagation Algorithm on Sparse Random Graphs, Phase transition of the 2-choices dynamics on core-periphery networks, Unnamed Item, Noisy rumor spreading and plurality consensus, Phase transition of the 3-majority dynamics with uniform communication noise

Cites Work

• Unnamed Item
• A simple population protocol for fast robust approximate majority
• Global majority consensus by local majority polling on graphs of a given degree sequence
• Local majorities, coalitions and monopolies in graphs: A review
• Distributed probabilistic polling and applications to proportionate agreement
• Distributed community detection in dynamic graphs
• Tight lower bound on the probability of a binomial exceeding its expectation
• Convergence Speed of Binary Interval Consensus
• Balls and bins: A study in negative dependence
• Determining Majority in Networks with Local Interactions and Very Small Local Memory
• Plurality Consensus in the Gossip Model