On simple back-off in unreliable radio networks

DOI10.1016/J.TCS.2019.08.027MaRDI QIDQ2285148zbMATH OpenOpenAlexFDO

Authors Calvin Newport, Dominik Pajak, Nancy Lynch, Seth Gilbert

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, https://drops.dagstuhl.de/opus/volltexte/2018/10087/

zbMATH Keywords

algorithmbroadcastradio networksunreliable linksstochastic adversary

Mathematics Subject Classification ID

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

Abstract: In this paper, we study local and global broadcast in the dual graph model, which describes communication in a radio network with both reliable and unreliable links. Existing work proved that efficient solutions to these problems are impossible in the dual graph model under standard assumptions. In real networks, however, simple back-off strategies tend to perform well for solving these basic communication tasks. We address this apparent paradox by introducing a new set of constraints to the dual graph model that better generalize the slow/fast fading behavior common in real networks. We prove that in the context of these new constraints, simple back-off strategies now provide efficient solutions to local and global broadcast in the dual graph model. We also precisely characterize how this efficiency degrades as the new constraints are reduced down to non-existent, and prove new lower bounds that establish this degradation as near optimal for a large class of natural algorithms. We conclude with a preliminary investigation of the performance of these strategies when we include additional generality to the model. These results provide theoretical foundations for the practical observation that simple back-off algorithms tend to work well even amid the complicated link dynamics of real radio networks.

Recommendations

• On simple back-off in unreliable radio networks
• Structuring unreliable radio networks
• Structuring unreliable radio networks
• Lower bounds for structuring unreliable radio networks
• Broadcasting in unreliable radio networks
• On reliable broadcast in a radio network
• The cost of radio network broadcast for different models of unreliable links
• Computing and maximizing the exact reliability of wireless backhaul networks

Cites work

• scientific article; zbMATH DE number 7561455 (Why is no real title available?)
• A (truly) local broadcast layer for unreliable radio networks
• A lower bound for radio broadcast
• An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks
• Bounds on contention management in radio networks
• Broadcasting algorithms in radio networks with unknown topology
• Broadcasting in undirected ad hoc radio networks
• Broadcasting in unreliable radio networks
• Channel identification for high speed digital communications
• Leader election in unreliable radio networks
• Mathematical Analysis of Random Noise
• Multi-message broadcast with abstract MAC layers and unreliable links
• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
• Radio Network Lower Bounds Made Easy
• Round robin is optimal for fault-tolerant broadcasting on wireless networks
• Structuring unreliable radio networks
• Tail bounds for sums of geometric and exponential variables
• The cost of radio network broadcast for different models of unreliable links

Cited in

(3)

• Structuring unreliable radio networks
• Bounds on contention management in radio networks
• The cost of radio network broadcast for different models of unreliable links

This page was built for publication: On simple back-off in unreliable radio networks

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