Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication

DOI10.1007/S00446-015-0249-4zbMath1423.68070arXiv1311.3425OpenAlexW764739102MaRDI QIDQ1689748

Amos Korman, Bernhard Haeupler, Ofer Feinerman

Publication date: 17 January 2018

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

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

zbMATH Keywords

noisereliabilityconsensusinformation disseminationrumor spreadinggossip

Mathematics Subject Classification ID

Communication networks in operations research (90B18) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed systems (68M14)

Related Items (4)

Phase Transition of a Non-linear Opinion Dynamics with Noisy Interactions ⋮ Phase transition of the \(k\)-majority dynamics in biased communication models ⋮ Making asynchronous distributed computations robust to noise ⋮ Phase transition of the 3-majority dynamics with uniform communication noise

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• A simple population protocol for fast robust approximate majority
• Mediated population protocols
• Adaptive broadcasting with faulty nodes
• On the runtime and robustness of randomized broadcasting
• Optimal adaptive broadcasting with a bounded fraction of faulty nodes
• Negative association of random variables, with applications
• Natural models for evolution on networks
• Computation in networks of passively mobile finite-state sensors
• Simple dynamics for plurality consensus
• Beeping a maximal independent set
• Collaborative search on the plane without communication
• Optimal gossip with direct addressing
• Asymptotically Optimal Randomized Rumor Spreading
• A Biological Solution to a Fundamental Distributed Computing Problem
• Coding for Errors and Erasures in Random Network Coding
• Strong Robustness of Randomized Rumor Spreading Protocols
• On Spreading a Rumor
• Fault tolerant distributed majority commitment
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Consensus Algorithms in Sensor Networks With Imperfect Communication: Link Failures and Channel Noise
• Balls and bins: A study in negative dependence
• Memory Lower Bounds for Randomized Collaborative Search and Implications for Biology
• The Power of Two Choices in Distributed Voting
• Stone age distributed computing
• On the role of zealotry in the voter model
• Error Correction Coding
• Asynchronous gossip
• Global computation in a poorly connected world
• Analyzing network coding gossip made easy

This page was built for publication: Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication