Noisy rumor spreading and plurality consensus

DOI10.1007/S00446-018-0335-5MaRDI QIDQ2318110zbMATH OpenOpenAlexFDO

Authors Pierre Fraigniaud, Emanuele Natale

Publication date 13 August 2019

Published in Distributed Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00446-018-0335-5

zbMATH Keywords

biological distributed algorithmsnoiseplurality consensusPUSH modelrumor spreading

Mathematics Subject Classification ID

Distributed systems (68M14) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07) Distributed algorithms (68W15)

Recommendations

• Noisy rumor spreading and plurality consensus (extended abstract)
• Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication
• Breathe before speaking
• Efficient plurality consensus, or: the benefits of cleaning up from time to time
• A polylogarithmic gossip algorithm for plurality consensus

Cites work

• A biological solution to a fundamental distributed computing problem
• A polylogarithmic gossip algorithm for plurality consensus
• A Remark on Stirling's Formula
• A simple population protocol for fast robust approximate majority
• Breathe before speaking
• Brief announcement: Rapid asynchronous plurality consensus
• Concentration of Measure for the Analysis of Randomized Algorithms
• Convergence speed of binary interval consensus
• Efficient plurality consensus, or: the benefits of cleaning up from time to time
• Global majority consensus by local majority polling on graphs of a given degree sequence
• scientific article; zbMATH DE number 5605125 (Why is no real title available?)
• scientific article; zbMATH DE number 6850453 (Why is no real title available?)
• Limits for rumor spreading in stochastic populations
• Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits
• Natural algorithms
• Network information theory
• On Spreading a Rumor
• Plurality consensus in arbitrary graphs: lessons learned from load balancing
• Plurality consensus in the gossip model
• Probability and Computing
• Simple dynamics for plurality consensus
• The computational power of population protocols
• The Power of Two Choices in Distributed Voting

Cited in

(9)

• Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication
• Phase transition of the 3-majority dynamics with uniform communication noise
• Mass-mobilization with noisy conditional beliefs
• Limits for rumor spreading in stochastic populations
• Phase Transition of a Non-linear Opinion Dynamics with Noisy Interactions
• Noisy rumor spreading and plurality consensus (extended abstract)
• Phase transition of the k-majority dynamics in biased communication models
• Quasi-majority functional voting on expander graphs
• Phase transition of the 3-majority opinion dynamics with noisy interactions

This page was built for publication: Noisy rumor spreading and plurality consensus

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