Brief announcement: On simple back-off in unreliable radio networks
© Seth Gilbert, Nancy Lynch, Calvin Newport, and Dominik Pajak. 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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137761 |
| _version_ | 1811076228060282880 |
|---|---|
| author | Lynch, Nancy |
| author_facet | Lynch, Nancy |
| author_sort | Lynch, Nancy |
| collection | MIT |
| description | © Seth Gilbert, Nancy Lynch, Calvin Newport, and Dominik Pajak. 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. |
| first_indexed | 2024-09-23T10:18:18Z |
| format | Article |
| id | mit-1721.1/137761 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:18:18Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1377612021-11-09T03:31:02Z Brief announcement: On simple back-off in unreliable radio networks Lynch, Nancy © Seth Gilbert, Nancy Lynch, Calvin Newport, and Dominik Pajak. 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. 2021-11-08T18:27:35Z 2021-11-08T18:27:35Z 2018 2019-06-13T14:55:29Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137761 Lynch, Nancy. 2018. "Brief announcement: On simple back-off in unreliable radio networks." en 10.4230/LIPIcs.DISC.2018.48 Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf DROPS |
| spellingShingle | Lynch, Nancy Brief announcement: On simple back-off in unreliable radio networks |
| title | Brief announcement: On simple back-off in unreliable radio networks |
| title_full | Brief announcement: On simple back-off in unreliable radio networks |
| title_fullStr | Brief announcement: On simple back-off in unreliable radio networks |
| title_full_unstemmed | Brief announcement: On simple back-off in unreliable radio networks |
| title_short | Brief announcement: On simple back-off in unreliable radio networks |
| title_sort | brief announcement on simple back off in unreliable radio networks |
| url | https://hdl.handle.net/1721.1/137761 |
| work_keys_str_mv | AT lynchnancy briefannouncementonsimplebackoffinunreliableradionetworks |