Brief announcement: Hardness of broadcasting in wireless networks with unreliable communication
Author(s)
Newport, Calvin Charles; Kuhn, Fabian; Lynch, Nancy Ann
DownloadLynch_Hardness of Broadcasting.pdf (129.9Kb)
OPEN_ACCESS_POLICY
Open Access Policy
Creative Commons Attribution-Noncommercial-Share Alike
Terms of use
Metadata
Show full item recordAbstract
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.
Date issued
2009Department
Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory; Massachusetts Institute of Technology. Department of Electrical Engineering and Computer ScienceJournal
Proceedings of the 28th ACM Symposium on Principles of Distributed Computing
Publisher
Association for Computing Machinery
Citation
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.
Version: Author's final manuscript
ISBN
978-1-60558-396-9