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

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



PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.48.pdf
  • Filesize: 328 kB
  • 3 pages

Document Identifiers

Author Details

Seth Gilbert
  • National University of Singapore
Nancy Lynch
  • Massachusetts Institute of Technology, Cambridge, MA 02139, USA
Calvin Newport
  • Georgetown University, Washington, D.C., USA
Dominik Pajak
  • Massachusetts Institute of Technology, Cambridge, MA 02139, USA

Cite AsGet BibTex

Seth Gilbert, Nancy Lynch, Calvin Newport, and Dominik Pajak. Brief Announcement: On Simple Back-Off in Unreliable Radio Networks. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 48:1-48:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.DISC.2018.48

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Networks → Ad hoc networks
Keywords
  • radio networks
  • broadcast
  • unreliable links
  • distributed algorithm
  • robustness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Reuven Bar-Yehuda, Oded Goldreich, and Alon Itai. On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. J. Comput. Syst. Sci., 45(1):104-126, 1992. Google Scholar
  2. Mohsen Ghaffari, Bernhard Haeupler, Nancy A. Lynch, and Calvin C. Newport. Bounds on contention management in radio networks. In Distributed Computing - 26th International Symposium, DISC 2012, Salvador, Brazil, October 16-18, 2012. Proceedings, pages 223-237, 2012. Google Scholar
  3. Mohsen Ghaffari, Nancy A. Lynch, and Calvin C. Newport. The cost of radio network broadcast for different models of unreliable links. In ACM Symposium on Principles of Distributed Computing, PODC '13, Montreal, QC, Canada, pages 345-354, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail