The abstract MAC layer
A diversity of possible communication assumptions complicates the study of algorithms and lower bounds for radio networks. We address this problem by defining an abstract MAC layer. This service provides reliable local broadcast communication, with timing guarantees stated in terms of a collection o...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Springer Nature America, Inc
2021
|
| Online Access: | https://hdl.handle.net/1721.1/134460 |
| _version_ | 1811084361428107264 |
|---|---|
| author | Kuhn, Fabian Lynch, Nancy Newport, Calvin |
| author_facet | Kuhn, Fabian Lynch, Nancy Newport, Calvin |
| author_sort | Kuhn, Fabian |
| collection | MIT |
| description | A diversity of possible communication assumptions complicates the study of algorithms and lower bounds for radio networks. We address this problem by defining an abstract MAC layer. This service provides reliable local broadcast communication, with timing guarantees stated in terms of a collection of abstract delay functions applied to the relevant contention. Algorithm designers can analyze their algorithms in terms of these functions, independently of specific channel behavior. Concrete implementations of the abstract MAC layer over basic radio network models generate concrete definitions for these delay functions, automatically adapting bounds proven for the abstract service to bounds for the specific radio network under consideration. To illustrate this approach, we use the abstract MAC layer to study the new problem of Multi-Message Broadcast, a generalization of standard single-message broadcast in which multiple messages can originate at different times and locations in the network.We present and analyze two algorithms for Multi-Message Broadcast in static networks: a simple greedy algorithm and one that uses regional leaders. We then indicate how these results can be extended to mobile networks. © 2010 Springer-Verlag. |
| first_indexed | 2024-09-23T12:49:30Z |
| format | Article |
| id | mit-1721.1/134460 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:49:30Z |
| publishDate | 2021 |
| publisher | Springer Nature America, Inc |
| record_format | dspace |
| spelling | mit-1721.1/1344602022-03-31T14:31:25Z The abstract MAC layer Kuhn, Fabian Lynch, Nancy Newport, Calvin A diversity of possible communication assumptions complicates the study of algorithms and lower bounds for radio networks. We address this problem by defining an abstract MAC layer. This service provides reliable local broadcast communication, with timing guarantees stated in terms of a collection of abstract delay functions applied to the relevant contention. Algorithm designers can analyze their algorithms in terms of these functions, independently of specific channel behavior. Concrete implementations of the abstract MAC layer over basic radio network models generate concrete definitions for these delay functions, automatically adapting bounds proven for the abstract service to bounds for the specific radio network under consideration. To illustrate this approach, we use the abstract MAC layer to study the new problem of Multi-Message Broadcast, a generalization of standard single-message broadcast in which multiple messages can originate at different times and locations in the network.We present and analyze two algorithms for Multi-Message Broadcast in static networks: a simple greedy algorithm and one that uses regional leaders. We then indicate how these results can be extended to mobile networks. © 2010 Springer-Verlag. 2021-10-27T20:05:06Z 2021-10-27T20:05:06Z 2011 2019-06-13T14:30:00Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/134460 en 10.1007/s00446-010-0118-0 Distributed Computing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer Nature America, Inc MIT web domain |
| spellingShingle | Kuhn, Fabian Lynch, Nancy Newport, Calvin The abstract MAC layer |
| title | The abstract MAC layer |
| title_full | The abstract MAC layer |
| title_fullStr | The abstract MAC layer |
| title_full_unstemmed | The abstract MAC layer |
| title_short | The abstract MAC layer |
| title_sort | abstract mac layer |
| url | https://hdl.handle.net/1721.1/134460 |
| work_keys_str_mv | AT kuhnfabian theabstractmaclayer AT lynchnancy theabstractmaclayer AT newportcalvin theabstractmaclayer AT kuhnfabian abstractmaclayer AT lynchnancy abstractmaclayer AT newportcalvin abstractmaclayer |