Decomposing broadcast algorithms using abstract mac layers
In much of the theoretical literature on wireless algorithms, issues of message dissemination are considered together with issues of contention management. This combination leads to complicated algorithms and analysis, and makes it difficult to extend the work to harder communication problems. In t...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72062 https://orcid.org/0000-0003-3045-265X |
| _version_ | 1826197211916009472 |
|---|---|
| author | Khabbazian, Majid Kowalski, Dariusz R. Kuhn, Fabian Lynch, Nancy Ann |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Khabbazian, Majid Kowalski, Dariusz R. Kuhn, Fabian Lynch, Nancy Ann |
| author_sort | Khabbazian, Majid |
| collection | MIT |
| description | In much of the theoretical literature on wireless algorithms, issues of message dissemination are considered together with issues of contention management. This combination leads to
complicated algorithms and analysis, and makes it difficult to extend the work to harder communication problems. In this paper, we present results of a current project aimed at simplifying such algorithms and analysis by decomposing the treatment into two levels, using abstract "MAC layer" specifi cations to encapsulate the contention management. We use two di erent abstract MAC layers: the basic one of [14, 15] and a new probabilistic layer. We show that it implements both abstract MAC layers. We combine this algorithm with greedy algorithms for single- message and multi-message global broadcast and analyze the combination, using both abstract MAC layers as intermediate layers. Using the basic MAC layer, we prove a bound of ... for the time to deliver a single message everywhere with probability 1 -epsilon , where D is the network diameter, n is the number of nodes, and Delta is the maximum node degree. Using the probabilistic layer, we prove a bound of ..., which matches the best previously-known bound for single-message broadcast over the physical network model. For multi-message broadcast, we obtain bounds of ... using the basic layer and ... using the probabilistic layer, for the time to deliver a message everywhere in the presence of at most k concurrent messages. |
| first_indexed | 2024-09-23T10:44:32Z |
| format | Article |
| id | mit-1721.1/72062 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:44:32Z |
| publishDate | 2012 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/720622022-09-30T22:39:21Z Decomposing broadcast algorithms using abstract mac layers Khabbazian, Majid Kowalski, Dariusz R. Kuhn, Fabian Lynch, Nancy Ann Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Lynch, Nancy Ann Lynch, Nancy Ann In much of the theoretical literature on wireless algorithms, issues of message dissemination are considered together with issues of contention management. This combination leads to complicated algorithms and analysis, and makes it difficult to extend the work to harder communication problems. In this paper, we present results of a current project aimed at simplifying such algorithms and analysis by decomposing the treatment into two levels, using abstract "MAC layer" specifi cations to encapsulate the contention management. We use two di erent abstract MAC layers: the basic one of [14, 15] and a new probabilistic layer. We show that it implements both abstract MAC layers. We combine this algorithm with greedy algorithms for single- message and multi-message global broadcast and analyze the combination, using both abstract MAC layers as intermediate layers. Using the basic MAC layer, we prove a bound of ... for the time to deliver a single message everywhere with probability 1 -epsilon , where D is the network diameter, n is the number of nodes, and Delta is the maximum node degree. Using the probabilistic layer, we prove a bound of ..., which matches the best previously-known bound for single-message broadcast over the physical network model. For multi-message broadcast, we obtain bounds of ... using the basic layer and ... using the probabilistic layer, for the time to deliver a message everywhere in the presence of at most k concurrent messages. United States. Air Force Office of Scientific Research (AFOSR contract FA9550-08-1-0159) National Science Foundation (U.S.) (NSF grants CCF-072651) National Science Foundation (U.S.) (NSF grant CNS-0715397) National Science Foundation (U.S.) (NSF grant CCF- 0937274) Natural Sciences and Engineering Research Council of Canada (NSERC) (Post-doctoral fellowship) 2012-08-09T14:20:19Z 2012-08-09T14:20:19Z 2010-09 Article http://purl.org/eprint/type/ConferencePaper 1450304133 978-1-4503-0413-9 http://hdl.handle.net/1721.1/72062 Khabbazian, Majid et al. “Decomposing Broadcast Algorithms Using Abstract MAC Layers.” in Proceedings of the Sixth ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing, DIALM-POMC 2010, September 16th, Cambridge, Massachusetts, ACM Press, 2010. 13. Web. https://orcid.org/0000-0003-3045-265X en_US http://dx.doi.org/10.1145/1860684.1860690 Proceedings of the Sixth ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing, DIALM-POMC 2010 Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery Lynch via Amy Stout |
| spellingShingle | Khabbazian, Majid Kowalski, Dariusz R. Kuhn, Fabian Lynch, Nancy Ann Decomposing broadcast algorithms using abstract mac layers |
| title | Decomposing broadcast algorithms using abstract mac layers |
| title_full | Decomposing broadcast algorithms using abstract mac layers |
| title_fullStr | Decomposing broadcast algorithms using abstract mac layers |
| title_full_unstemmed | Decomposing broadcast algorithms using abstract mac layers |
| title_short | Decomposing broadcast algorithms using abstract mac layers |
| title_sort | decomposing broadcast algorithms using abstract mac layers |
| url | http://hdl.handle.net/1721.1/72062 https://orcid.org/0000-0003-3045-265X |
| work_keys_str_mv | AT khabbazianmajid decomposingbroadcastalgorithmsusingabstractmaclayers AT kowalskidariuszr decomposingbroadcastalgorithmsusingabstractmaclayers AT kuhnfabian decomposingbroadcastalgorithmsusingabstractmaclayers AT lynchnancyann decomposingbroadcastalgorithmsusingabstractmaclayers |