On simple back-off in unreliable radio networks

DOI10.1016/j.tcs.2019.08.027zbMath1436.68238arXiv1803.02216OpenAlexW2970138543MaRDI QIDQ2285148

Calvin Newport, Seth Gilbert, Dominik Pająk, Nancy A. Lynch

Publication date: 16 January 2020

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

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

zbMATH Keywords

algorithmbroadcastradio networksunreliable linksstochastic adversary

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• A lower bound for radio broadcast
• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
• Tail bounds for sums of geometric and exponential variables
• Round robin is optimal for fault-tolerant broadcasting on wireless networks
• A (Truly) Local Broadcast Layer for Unreliable Radio Networks
• Multi-message broadcast with abstract MAC layers and unreliable links
• Channel identification for high speed digital communications
• An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks
• Leader Election in Unreliable Radio Networks.
• Bounds on Contention Management in Radio Networks
• The cost of radio network broadcast for different models of unreliable links
• Broadcasting in unreliable radio networks
• Broadcasting algorithms in radio networks with unknown topology
• Radio Network Lower Bounds Made Easy
• Mathematical Analysis of Random Noise
• Broadcasting in undirected ad hoc radio networks
• Structuring unreliable radio networks