License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2018.27
URN: urn:nbn:de:0030-drops-100877
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10087/
Gilbert, Seth ;
Lynch, Nancy ;
Newport, Calvin ;
Pajak, Dominik
On Simple Back-Off in Unreliable Radio Networks
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 an analysis of a more general model where we propose an enhanced back-off algorithm. 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.
BibTeX - Entry
@InProceedings{gilbert_et_al:LIPIcs:2018:10087,
author = {Seth Gilbert and Nancy Lynch and Calvin Newport and Dominik Pajak},
title = {{On Simple Back-Off in Unreliable Radio Networks}},
booktitle = {22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
pages = {27:1--27:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-098-9},
ISSN = {1868-8969},
year = {2018},
volume = {125},
editor = {Jiannong Cao and Faith Ellen and Luis Rodrigues and Bernardo Ferreira},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10087},
URN = {urn:nbn:de:0030-drops-100877},
doi = {10.4230/LIPIcs.OPODIS.2018.27},
annote = {Keywords: radio networks, broadcast, unreliable links, distributed algorithm, robustness}
}
|
Keywords: |
|
radio networks, broadcast, unreliable links, distributed algorithm, robustness |
|
Collection: |
|
22nd International Conference on Principles of Distributed Systems (OPODIS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
15.01.2019 |
