Decomposing Broadcast Algorithms Using Abstract MAC Layers
In much of the theoretical literature on global broadcast algorithms for wireless networks, 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 more d...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Published: |
2011
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/61391 |
| _version_ | 1826209136356884480 |
|---|---|
| author | Khabbazian, Majid Kowalski, Dariusz Kuhn, Fabian Lynch, Nancy |
| author2 | Nancy Lynch |
| author_facet | Nancy Lynch Khabbazian, Majid Kowalski, Dariusz Kuhn, Fabian Lynch, Nancy |
| author_sort | Khabbazian, Majid |
| collection | MIT |
| description | In much of the theoretical literature on global broadcast algorithms for wireless networks, 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 more difficult communication problems. In this paper, we present results aimed at simplifying such algorithms and analysis by decomposing the treatment into two levels, using abstract "MAC layer" specifications to encapsulate contention management. We use two different abstract MAC layers: the basic layer of Kuhn, Lynch, and Newport, and a new probabilistic layer. We first present a typical randomized contention-management algorithm for a standard graph-based radio network model and show that it implements both abstract MAC layers. Then we combine this algorithm with greedy algorithms for single-message and multi-message global broadcast and analyze the combinations, using both abstract MAC layers as intermediate layers. Using the basic MAC layer, we prove a bound of O(D log(n / epsilon) log(Delta)) 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 O((D + log(n/epsilon)) log(Delta)), which matches the best previously-known bound for single-message broadcast over the physical network model. For multi-message broadcast, we obtain bounds of O((D + k Delta) log(n/epsilon) log(Delta)) using the basic layer and O((D + k Delta log(n/epsilon)) log(Delta)) 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-23T14:18:09Z |
| id | mit-1721.1/61391 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T14:18:09Z |
| publishDate | 2011 |
| record_format | dspace |
| spelling | mit-1721.1/613912019-04-10T16:18:23Z Decomposing Broadcast Algorithms Using Abstract MAC Layers Khabbazian, Majid Kowalski, Dariusz Kuhn, Fabian Lynch, Nancy Nancy Lynch Theory of Computation broadcast protocol contention management wireless network algorithms multi-message broadcast global broadcast In much of the theoretical literature on global broadcast algorithms for wireless networks, 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 more difficult communication problems. In this paper, we present results aimed at simplifying such algorithms and analysis by decomposing the treatment into two levels, using abstract "MAC layer" specifications to encapsulate contention management. We use two different abstract MAC layers: the basic layer of Kuhn, Lynch, and Newport, and a new probabilistic layer. We first present a typical randomized contention-management algorithm for a standard graph-based radio network model and show that it implements both abstract MAC layers. Then we combine this algorithm with greedy algorithms for single-message and multi-message global broadcast and analyze the combinations, using both abstract MAC layers as intermediate layers. Using the basic MAC layer, we prove a bound of O(D log(n / epsilon) log(Delta)) 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 O((D + log(n/epsilon)) log(Delta)), which matches the best previously-known bound for single-message broadcast over the physical network model. For multi-message broadcast, we obtain bounds of O((D + k Delta) log(n/epsilon) log(Delta)) using the basic layer and O((D + k Delta log(n/epsilon)) log(Delta)) using the probabilistic layer, for the time to deliver a message everywhere in the presence of at most k concurrent messages. Author Lynch's research is supported by AFOSR contract FA9550-08-1-0159 and NSF grants CCF-0726514, CNS-0715397, CCF-0937274, and NSF-PURDUE-STC Award 0939370-CCF. Author Kowalski's research is supported by the Engineering and Physical Sciences Research Council [grant numbers EP/G023018/1, EP/H018816/1]. 2011-03-03T20:15:08Z 2011-03-03T20:15:08Z 2011-02-23 http://hdl.handle.net/1721.1/61391 MIT-CSAIL-TR-2011-010 39 p. application/pdf |
| spellingShingle | broadcast protocol contention management wireless network algorithms multi-message broadcast global broadcast Khabbazian, Majid Kowalski, Dariusz Kuhn, Fabian Lynch, Nancy 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 |
| topic | broadcast protocol contention management wireless network algorithms multi-message broadcast global broadcast |
| url | http://hdl.handle.net/1721.1/61391 |
| work_keys_str_mv | AT khabbazianmajid decomposingbroadcastalgorithmsusingabstractmaclayers AT kowalskidariusz decomposingbroadcastalgorithmsusingabstractmaclayers AT kuhnfabian decomposingbroadcastalgorithmsusingabstractmaclayers AT lynchnancy decomposingbroadcastalgorithmsusingabstractmaclayers |