Feasibility and complexity of broadcasting with random transmission failures

DOI10.1016/J.TCS.2006.10.031MaRDI QIDQ868959zbMATH OpenOpenAlexFDO

Authors Andrzej Pelc, David Peleg

Publication date 26 February 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2006.10.031

zbMATH Keywords

broadcastingmalicious transmission failuresmessage passingnode-omission failuresradio networksrandom failures

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Recommendations

• Feasibility and complexity of broadcasting with random transmission failures
• FAST BROADCASTING WITH BYZANTINE FAULTS
• scientific article; zbMATH DE number 751136
• Reliable broadcasting in hypercubes with random link and node failures
• Fault-tolerant broadcasting in radio networks

Cites work

• A guided tour of Chernoff bounds
• A lower bound for radio broadcast
• Almost Safe Gossiping in Bounded Degree Networks
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Broadcast in radio networks tolerating Byzantine adversarial behavior
• Broadcasting algorithms in radio networks with unknown topology
• Fault-tolerant broadcasting and gossiping in communication networks
• Fault-tolerant broadcasting in radio networks
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• Information dissemination in distributed systems with faulty units
• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
• Optimal communication in networks with randomly distributed byzantine faults
• Reliable Broadcasting in Logarithmic Time with Byzantine Link Failures
• Slide—The Key to Polynomial End-to-End Communication
• The Byzantine generals strike again
• The impossibility of implementing reliable communication in the face of crashes
• Time of Deterministic Broadcasting in Radio Networks with Local Knowledge

Cited in

(9)

• Reliability versus cost: Design of a probabilistic broadcast algorithm
• On linear-time data dissemination in dynamic rooted trees
• The complexity of finding a broadcast center
• Optimal gossiping in geometric radio networks in the presence of dynamical faults
• FAST BROADCASTING WITH BYZANTINE FAULTS
• scientific article; zbMATH DE number 1156838 (Why is no real title available?)
• Sparse networks supporting efficient reliable broadcasting
• Feasibility and complexity of broadcasting with random transmission failures
• \(f\)-sensitivity distance oracles and routing schemes

This page was built for publication: Feasibility and complexity of broadcasting with random transmission failures

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