An efficient communication abstraction for dense wireless networks
© Magnús Halldórsson, Fabian Kuhn, Nancy Lynch, and Calvin Newport. In this paper we study the problem of developing efficient distributed algorithms for dense wireless networks. For many problems in this setting, fast solutions must leverage the reality that radio signals fade with distance, which...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137778 |
| _version_ | 1811081206564913152 |
|---|---|
| author | Halldórsson, Magnús M. Kuhn, Fabian Lynch, Nancy Ann Newport, Calvin |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Halldórsson, Magnús M. Kuhn, Fabian Lynch, Nancy Ann Newport, Calvin |
| author_sort | Halldórsson, Magnús M. |
| collection | MIT |
| description | © Magnús Halldórsson, Fabian Kuhn, Nancy Lynch, and Calvin Newport. In this paper we study the problem of developing efficient distributed algorithms for dense wireless networks. For many problems in this setting, fast solutions must leverage the reality that radio signals fade with distance, which can be exploited to enable concurrent communication among multiple sender/receiver pairs. To simplify the development of these algorithms we describe a new communication abstraction called FadingMAC which exposes the benefits of this concurrent communication, but also hides the details of the underlying low-level radio signal behavior. This approach splits efforts between those who develop useful algorithms that run on the abstraction, and those who implement the abstraction in concrete low-level wireless models, or on real hardware. After defining FadingMAC, we describe and analyze an efficient implementation of the abstraction in a standard low-level SINR-style network model. We then describe solutions to the following problems that run on the abstraction: max, min, sum, and mean computed over input values; process renaming; consensus and leader election; and optimal packet scheduling. Combining our abstraction implementation with these applications that run on the abstraction, we obtain near-optimal solutions to these problems in our low-level SINR model - significantly advancing the known results for distributed algorithms in this setting. Of equal importance to these concrete bounds, however, is the general idea advanced by this paper: as wireless networks become more dense, both theoreticians and practitioners must explore new communication abstractions that can help tame this density. |
| first_indexed | 2024-09-23T11:43:07Z |
| format | Article |
| id | mit-1721.1/137778 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:43:07Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1377782023-02-09T18:54:35Z An efficient communication abstraction for dense wireless networks Halldórsson, Magnús M. Kuhn, Fabian Lynch, Nancy Ann Newport, Calvin Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science © Magnús Halldórsson, Fabian Kuhn, Nancy Lynch, and Calvin Newport. In this paper we study the problem of developing efficient distributed algorithms for dense wireless networks. For many problems in this setting, fast solutions must leverage the reality that radio signals fade with distance, which can be exploited to enable concurrent communication among multiple sender/receiver pairs. To simplify the development of these algorithms we describe a new communication abstraction called FadingMAC which exposes the benefits of this concurrent communication, but also hides the details of the underlying low-level radio signal behavior. This approach splits efforts between those who develop useful algorithms that run on the abstraction, and those who implement the abstraction in concrete low-level wireless models, or on real hardware. After defining FadingMAC, we describe and analyze an efficient implementation of the abstraction in a standard low-level SINR-style network model. We then describe solutions to the following problems that run on the abstraction: max, min, sum, and mean computed over input values; process renaming; consensus and leader election; and optimal packet scheduling. Combining our abstraction implementation with these applications that run on the abstraction, we obtain near-optimal solutions to these problems in our low-level SINR model - significantly advancing the known results for distributed algorithms in this setting. Of equal importance to these concrete bounds, however, is the general idea advanced by this paper: as wireless networks become more dense, both theoreticians and practitioners must explore new communication abstractions that can help tame this density. 2021-11-08T18:56:58Z 2021-11-08T18:56:58Z 2017 2019-06-13T16:23:16Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137778 Lynch, Nancy. 2017. "An efficient communication abstraction for dense wireless networks." en 10.4230/LIPIcs.DISC.2017.25 Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf DROPS |
| spellingShingle | Halldórsson, Magnús M. Kuhn, Fabian Lynch, Nancy Ann Newport, Calvin An efficient communication abstraction for dense wireless networks |
| title | An efficient communication abstraction for dense wireless networks |
| title_full | An efficient communication abstraction for dense wireless networks |
| title_fullStr | An efficient communication abstraction for dense wireless networks |
| title_full_unstemmed | An efficient communication abstraction for dense wireless networks |
| title_short | An efficient communication abstraction for dense wireless networks |
| title_sort | efficient communication abstraction for dense wireless networks |
| url | https://hdl.handle.net/1721.1/137778 |
| work_keys_str_mv | AT halldorssonmagnusm anefficientcommunicationabstractionfordensewirelessnetworks AT kuhnfabian anefficientcommunicationabstractionfordensewirelessnetworks AT lynchnancyann anefficientcommunicationabstractionfordensewirelessnetworks AT newportcalvin anefficientcommunicationabstractionfordensewirelessnetworks AT halldorssonmagnusm efficientcommunicationabstractionfordensewirelessnetworks AT kuhnfabian efficientcommunicationabstractionfordensewirelessnetworks AT lynchnancyann efficientcommunicationabstractionfordensewirelessnetworks AT newportcalvin efficientcommunicationabstractionfordensewirelessnetworks |