On Simple Back-Off in Unreliable Radio Networks

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



PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2018.27.pdf
  • Filesize: 0.51 MB
  • 17 pages

Document Identifiers

Author Details

Seth Gilbert
  • National University of Singapore, Singapore
Nancy Lynch
  • MIT, Cambridge, MA, USA
Calvin Newport
  • Georgetown University, Washington, DC, USA
Dominik Pajak
  • MIT, Cambridge, MA, USA

Cite AsGet BibTex

Seth Gilbert, Nancy Lynch, Calvin Newport, and Dominik Pajak. On Simple Back-Off in Unreliable Radio Networks. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.OPODIS.2018.27

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.

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. N. Alon, A. Bar-Noy, N. Linial, and D. Peleg. A Lower Bound for Radio Broadcast. Journal of Computer and System Sciences, 43(2):290-298, 1991. Google Scholar
  2. 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. URL: http://dx.doi.org/10.1016/0022-0000(92)90042-H.
  3. Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch, and Calvin Newport. Structuring Unreliable Radio Networks. Distributed Computing, 27(1):1-19, 2014. Google Scholar
  4. Andrea E. F. Clementi, Angelo Monti, and Riccardo Silvestri. Round Robin is optimal for fault-tolerant broadcasting on wireless networks. J. Parallel Distrib. Comput., 64(1):89-96, 2004. URL: http://dx.doi.org/10.1016/j.jpdc.2003.09.002.
  5. Mohsen Ghaffari. Bounds on Contention Management in Radio Networks. Master’s thesis, Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, February 2013. Google Scholar
  6. Mohsen Ghaffari, Bernhard Haeupler, Nancy Lynch, and Calvin Newport. Bounds on Contention Management in Radio Networks. In Marcos K. Aguilera, editor, Distributed Computing: 26th International Symposium (DISC 2012), Salvador, Brazil, October, 2012, volume 7611 of Lecture Notes in Computer Science, pages 223-237. Springer, 2012. Google Scholar
  7. Mohsen Ghaffari, Erez Kantor, Nancy Lynch, and Calvin Newport. Multi-Message Broadcast with Abstract MAC Layers and Unreliable Links. In Proceedings of the 33nd Annual ACM Symposium on Principles of Distributed Computing (PODC'14), pages 56-65, Paris, France, July 2014. Google Scholar
  8. Mohsen Ghaffari, Nancy Lynch, and Calvin Newport. The Cost of Radio Network Broadcast for Different Models of Unreliable Links. In Proceedings of the 32nd Annual ACM Symposium on Principles of Distributed Computing, pages 345-354, Montreal, Canada, July 2013. Google Scholar
  9. Mohsen Ghaffari and Calvin Newport. A Leader Election in Unreliable Radio Networks. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), 2016. Google Scholar
  10. Seth Gilbert, Nancy A. 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, New Orleans, LA, USA, October 15-19, 2018, pages 48:1-48:3, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.DISC.2018.48.
  11. Fabian Kuhn, Nancy Lynch, and Calvin Newport. Brief Announcement: Hardness of Broadcasting in Wireless Networks with Unreliable Communication. In Proceedings of the 28th Annual ACM Symposium on the Principles of Distributed Computing (PODC 2009), Calgary, Alberta, Canada, August 2009. Google Scholar
  12. Fabian Kuhn, Nancy Lynch, Calvin Newport, Rotem Oshman, and Andrea Richa. Broadcasting in Unreliable Radio Networks. In Proceedings of the 29th ACM Symposium on Principles of Distributed Computing (PODC), pages 336-345, Zurich, Switzerland, July 2010. Google Scholar
  13. E. Kushilevitz and Y. Mansour. An Ω(D log(N/D)) Lower Bound for Broadcast in Radio Networks. SIAM Journal on Computing, 27(3):702-712, 1998. Google Scholar
  14. Nancy Lynch and Calvin Newport. A (Truly) Local Broadcast Layer for Unreliable Radio Networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), 2015. Google Scholar
  15. Calvin Newport. Lower Bounds for Radio Networks Made Easy. In Proceedings of the International Symposium on Distributed Computing (DISC), 2014. Google Scholar
  16. Mike Willis. Propagation Tutorial: Fading. http://www.mike-willis.com/Tutorial/PF15.htm. May 5, 2007.
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