Lower Bounds for the Noisy Broadcast Problem

DOI10.1137/060654864zbMATH Open1178.68263OpenAlexW2047805348MaRDI QIDQ3549324FDOQ3549324

Authors: Navin Goyal, Guy Kindler, Michael Saks 

Publication date: 22 December 2008

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/060654864

Recommendations

• On the optimality of general lower bounds for broadcasting and gossiping
• Algorithms for noisy broadcast with erasures
• Improved upper and lower bounds for \(k\)-broadcasting
• Optimal and near-optimal broadcast in random graphs
• Lower Bounds on the Broadcasting and Gossiping Time of Restricted Protocols
• An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks
• Improved lower bound for deterministic broadcasting in radio networks
• Lower bounds for the broadcast problem in mobile radio networks
• Reliable broadcasts and communication models: tradeoffs and lower bounds

zbMATH Keywords

distributed computationcomputation in presence of noise

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Cited In (9)

• Computing in fault tolerant broadcast networks and noisy decision trees
• Computation in Noisy Radio Networks
• Reliable communication over highly connected noisy networks
• Rounds vs queries trade-off in noisy computation
• Signal propagation and noisy circuits
• Algorithms for noisy broadcast with erasures
• Finding OR in a noisy broadcast network
• Computing with Noisy Information
• Limits for rumor spreading in stochastic populations

This page was built for publication: Lower Bounds for the Noisy Broadcast Problem

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