On simple back-off in unreliable radio networks

DOI10.1016/J.TCS.2019.08.027zbMATH Open1436.68238arXiv1803.02216OpenAlexW2970138543MaRDI QIDQ2285148FDOQ2285148

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

Publication date: 16 January 2020

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

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.

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

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

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)

Cites Work

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

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)