Brief announcement: Hardness of broadcasting in wireless networks with unreliable communication
We prove two broadcast lower bounds for a wireless network model that includes unreliable links. For deterministic algorithms, we show n − 1 rounds are required, where n is the number of processes. For randomized algorithms, ε(n − 1) rounds are required for success probability ε. In both cases, the...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2010
|
| Online Access: | http://hdl.handle.net/1721.1/51002 https://orcid.org/0000-0003-3045-265X |
| _version_ | 1826194264487362560 |
|---|---|
| author | Newport, Calvin Charles 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 Newport, Calvin Charles Kuhn, Fabian Lynch, Nancy Ann |
| author_sort | Newport, Calvin Charles |
| collection | MIT |
| description | We prove two broadcast lower bounds for a wireless network model that includes unreliable links. For deterministic algorithms, we show n − 1 rounds are required, where n is the number of processes. For randomized algorithms, ε(n − 1) rounds are required for success probability ε. In both cases, the bounds are proved for a network in which constant-time broadcast is possible. |
| first_indexed | 2024-09-23T09:53:06Z |
| format | Article |
| id | mit-1721.1/51002 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:53:06Z |
| publishDate | 2010 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/510022022-09-26T14:19:38Z Brief announcement: Hardness of broadcasting in wireless networks with unreliable communication Newport, Calvin Charles 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 Newport, Calvin Charles Kuhn, Fabian Lynch, Nancy Ann We prove two broadcast lower bounds for a wireless network model that includes unreliable links. For deterministic algorithms, we show n − 1 rounds are required, where n is the number of processes. For randomized algorithms, ε(n − 1) rounds are required for success probability ε. In both cases, the bounds are proved for a network in which constant-time broadcast is possible. 2010-01-28T15:26:37Z 2010-01-28T15:26:37Z 2009 2009-08 Article http://purl.org/eprint/type/SubmittedJournalArticle 978-1-60558-396-9 http://hdl.handle.net/1721.1/51002 Kuhn, Fabian, Nancy Lynch, and Calvin Newport. “Brief announcement: hardness of broadcasting in wireless networks with unreliable communication.” Proceedings of the 28th ACM symposium on Principles of distributed computing. Calgary, AB, Canada: ACM, 2009. 330-331. https://orcid.org/0000-0003-3045-265X en_US http://dx.doi.org/10.1145/1582716.1582794 Proceedings of the 28th ACM Symposium on Principles of Distributed Computing Attribution-Noncommercial-Share Alike 3.0 Unported http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery Joanne Hanley |
| spellingShingle | Newport, Calvin Charles Kuhn, Fabian Lynch, Nancy Ann Brief announcement: Hardness of broadcasting in wireless networks with unreliable communication |
| title | Brief announcement: Hardness of broadcasting in wireless networks with unreliable communication |
| title_full | Brief announcement: Hardness of broadcasting in wireless networks with unreliable communication |
| title_fullStr | Brief announcement: Hardness of broadcasting in wireless networks with unreliable communication |
| title_full_unstemmed | Brief announcement: Hardness of broadcasting in wireless networks with unreliable communication |
| title_short | Brief announcement: Hardness of broadcasting in wireless networks with unreliable communication |
| title_sort | brief announcement hardness of broadcasting in wireless networks with unreliable communication |
| url | http://hdl.handle.net/1721.1/51002 https://orcid.org/0000-0003-3045-265X |
| work_keys_str_mv | AT newportcalvincharles briefannouncementhardnessofbroadcastinginwirelessnetworkswithunreliablecommunication AT kuhnfabian briefannouncementhardnessofbroadcastinginwirelessnetworkswithunreliablecommunication AT lynchnancyann briefannouncementhardnessofbroadcastinginwirelessnetworkswithunreliablecommunication |