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.DISC.2018.48
URN: urn:nbn:de:0030-drops-98373
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9837/
Go to the corresponding LIPIcs Volume Portal

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

Brief Announcement: On Simple Back-Off in Unreliable Radio Networks

pdf-format:
LIPIcs-DISC-2018-48.pdf (0.3 MB)

Abstract

In this paper, we study local 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 broadcast in the dual graph 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.

BibTeX - Entry

@InProceedings{gilbert_et_al:LIPIcs:2018:9837,
  author =	{Seth Gilbert and Nancy Lynch and Calvin Newport and Dominik Pajak},
  title =	{{Brief Announcement: On Simple Back-Off in Unreliable Radio Networks}},
  booktitle =	{32nd International Symposium on Distributed Computing  (DISC 2018)},
  pages =	{48:1--48:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Ulrich Schmid and Josef Widder},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9837},
  URN =		{urn:nbn:de:0030-drops-98373},
  doi =		{10.4230/LIPIcs.DISC.2018.48},
  annote =	{Keywords: radio networks, broadcast, unreliable links, distributed algorithm, robustness}
}

Keywords: radio networks, broadcast, unreliable links, distributed algorithm, robustness
Collection: 32nd International Symposium on Distributed Computing (DISC 2018)
Issue Date: 2018
Date of publication: 04.10.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI