The cost of radio network broadcast for different models of unreliable links
We study upper and lower bounds for the global and local broadcast problems in the dual graph model combined with different strength adversaries. The dual graph model is a generalization of the standard graph-based radio network model that includes unreliable links controlled by an adversary. It is...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2014
|
| Online Access: | http://hdl.handle.net/1721.1/90369 https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0003-4213-9898 |
| _version_ | 1811098444262014976 |
|---|---|
| author | Ghaffari, Mohsen Lynch, Nancy Ann Newport, Calvin Charles |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Ghaffari, Mohsen Lynch, Nancy Ann Newport, Calvin Charles |
| author_sort | Ghaffari, Mohsen |
| collection | MIT |
| description | We study upper and lower bounds for the global and local broadcast problems in the dual graph model combined with different strength adversaries. The dual graph model is a generalization of the standard graph-based radio network model that includes unreliable links controlled by an adversary. It is motivated by the ubiquity of unreliable links in real wireless networks. Existing results in this model [11, 12, 3, 8] assume an offline adaptive adversary - the strongest type of adversary considered in standard randomized analysis. In this paper, we study the two other standard types of adversaries: online adaptive and oblivious. Our goal is to find a model that captures the unpredictable behavior of real networks while still allowing for efficient broadcast solutions.
For the online adaptive dual graph model, we prove a lower bound that shows the existence of constant-diameter graphs in which both types of broadcast require Ω(n/ log n) rounds, for network size n. This result is within log-factors of the (near) tight upper bound for the offline adaptive setting. For the oblivious dual graph model, we describe a global broadcast algorithm that solves the problem in O(Dlog n + log[superscript 2] n) rounds for network diameter D, but prove a lower bound of Ω(√n= log n) rounds for local broadcast in this same setting. Finally, under the assumption of geographic constraints on the network graph, we describe a local broadcast algorithm that requires only O(log[superscript 2] n logΔ) rounds in the oblivious model, for maximum degree Δ. In addition to the theoretical interest of these results, we argue that the oblivious model (with geographic constraints) captures enough behavior of real networks to render our efficient algorithms useful for real deployments. |
| first_indexed | 2024-09-23T17:15:00Z |
| format | Article |
| id | mit-1721.1/90369 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T17:15:00Z |
| publishDate | 2014 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/903692022-09-30T00:41:14Z The cost of radio network broadcast for different models of unreliable links Ghaffari, Mohsen Lynch, Nancy Ann Newport, Calvin Charles Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Ghaffari, Mohsen Lynch, Nancy Ann We study upper and lower bounds for the global and local broadcast problems in the dual graph model combined with different strength adversaries. The dual graph model is a generalization of the standard graph-based radio network model that includes unreliable links controlled by an adversary. It is motivated by the ubiquity of unreliable links in real wireless networks. Existing results in this model [11, 12, 3, 8] assume an offline adaptive adversary - the strongest type of adversary considered in standard randomized analysis. In this paper, we study the two other standard types of adversaries: online adaptive and oblivious. Our goal is to find a model that captures the unpredictable behavior of real networks while still allowing for efficient broadcast solutions. For the online adaptive dual graph model, we prove a lower bound that shows the existence of constant-diameter graphs in which both types of broadcast require Ω(n/ log n) rounds, for network size n. This result is within log-factors of the (near) tight upper bound for the offline adaptive setting. For the oblivious dual graph model, we describe a global broadcast algorithm that solves the problem in O(Dlog n + log[superscript 2] n) rounds for network diameter D, but prove a lower bound of Ω(√n= log n) rounds for local broadcast in this same setting. Finally, under the assumption of geographic constraints on the network graph, we describe a local broadcast algorithm that requires only O(log[superscript 2] n logΔ) rounds in the oblivious model, for maximum degree Δ. In addition to the theoretical interest of these results, we argue that the oblivious model (with geographic constraints) captures enough behavior of real networks to render our efficient algorithms useful for real deployments. Ford Motor Company (University Research Program) United States. Air Force Office of Scientific Research (AFOSR Contract No. FA9550- 13-1-0042) National Science Foundation (U.S.) (NSF Award No. CCF-1217506) National Science Foundation (U.S.) (NSF Award No. 0939370-CCF) National Science Foundation (U.S.) (NSF Award No. CCF-AF-0937274) United States. Air Force Office of Scientific Research (AFOSR Contract No. FA9550-08-1-0159) National Science Foundation (U.S.) (NSF Award No. CCF-072651) 2014-09-25T20:38:03Z 2014-09-25T20:38:03Z 2013-07 Article http://purl.org/eprint/type/JournalArticle 9781450320658 http://hdl.handle.net/1721.1/90369 Ghaffari, Mohsen, Nancy Lynch, and Calvin Newport. “The Cost of Radio Network Broadcast for Different Models of Unreliable Links.” Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing - PODC ’13 (2013), July 22–24, 2013, Montréal, Québec, Canada. ACM New York, NY, USA, p. 345-354. https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0003-4213-9898 en_US http://dx.doi.org/10.1145/2484239.2484259 Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing - PODC '13 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery MIT web domain |
| spellingShingle | Ghaffari, Mohsen Lynch, Nancy Ann Newport, Calvin Charles The cost of radio network broadcast for different models of unreliable links |
| title | The cost of radio network broadcast for different models of unreliable links |
| title_full | The cost of radio network broadcast for different models of unreliable links |
| title_fullStr | The cost of radio network broadcast for different models of unreliable links |
| title_full_unstemmed | The cost of radio network broadcast for different models of unreliable links |
| title_short | The cost of radio network broadcast for different models of unreliable links |
| title_sort | cost of radio network broadcast for different models of unreliable links |
| url | http://hdl.handle.net/1721.1/90369 https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0003-4213-9898 |
| work_keys_str_mv | AT ghaffarimohsen thecostofradionetworkbroadcastfordifferentmodelsofunreliablelinks AT lynchnancyann thecostofradionetworkbroadcastfordifferentmodelsofunreliablelinks AT newportcalvincharles thecostofradionetworkbroadcastfordifferentmodelsofunreliablelinks AT ghaffarimohsen costofradionetworkbroadcastfordifferentmodelsofunreliablelinks AT lynchnancyann costofradionetworkbroadcastfordifferentmodelsofunreliablelinks AT newportcalvincharles costofradionetworkbroadcastfordifferentmodelsofunreliablelinks |