An Ω(D log(N/D)) lower bound for broadcast in radio networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

An Ω(D log(N/D)) lower bound for broadcast in radio networks

Full text

Pdf (691 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the twelfth annual ACM symposium on Principles of distributed computing table of contents

Ithaca, New York, United States

Pages: 65 - 74

Year of Publication: 1993

ISBN:0-89791-613-1

Authors

Eyal Kushilevitz
Yishay Mansour

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 13, Citation Count: 12

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/164051.164059 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	ABLP91	Noga Alon , Amotz Bar-Noy , Nathan Linial , David Peleg, A lower bound for radio broadcast, Journal of Computer and System Sciences, v.43 n.2, p.290-298, Oct. 1991 [doi>10.1016/0022-0000(91)90015-W]
	ABLP92	Noga Alon , Amotz Bar-Noy , Nathan Linial , David Peleg, Single round simulation on radio networks, Journal of Algorithms, v.13 n.2, p.188-210, June, 1992 [doi>10.1016/0196-6774(92)90015-5]
	BGI91	Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection, Distributed Computing, v.5 n.2, p.67-71, September 1991 [doi>10.1007/BF02259748]
	BGI92	Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization, Journal of Computer and System Sciences, v.45 n.1, p.104-126, Aug. 1992 [doi>10.1016/0022-0000(92)90042-H]
	BII89	R. Bar-Yehuda , A. Israeli, Multiple communication in multi-hop radio networks, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.329-338, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.73005]
	CK85a	I. Chlamtac and S. Kutten. On broadcasting in radio networks- problem analysis and protocol design. IEEE Trans. Comm., COM-33, 1985.
	CK85b	I. Chlamtac and S. Kutten. A spa. tial reuse tdma/fdma for mobile multi-hop radio networks. In INFOCOM, pages 389-:394, 1985.
	CK87	I. Chlamtac , S. Kutten, Tree-based broadcasting in multihop radio networks, IEEE Transactions on Computers, v.36 n.10, p.1209-1223, Oct. 1987 [doi>10.1109/TC.1987.1676861]
	CW87	i. Chlamtac and O. Weinstein. The wave expansion approach to broadcasting in multihop radio networks. In INFOCOM, pages 874-881, 1987.
	Gal85	R. Gallager. A perspective on multiaccess channels. IEEE Transactions on {nforlnatioT~ Theory, 31'124-142, 1985.
	Ten81	A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
	Wil86	Dan E Willard, Log-logarithmic selection resolution protocols in a multiple access channel, SIAM Journal on Computing, v.15 n.2, p.468-477, May 1986 [doi>10.1137/0215032]

CITED BY 12

	Micah Adler , Christian Scheideler, Efficient communication strategies for ad-hoc wireless networks (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.259-268, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Anders Dessmark , Andrzej Pelc, Tradeoffs between knowledge and time of communication in geometric radio networks, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.59-66, July 2001, Crete Island, Greece
	Andrea E. F. Clementi , Angelo Monti , Riccardo Silvestri, Distributed multi-broadcast in unknown radio networks, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.255-264, August 2001, Newport, Rhode Island, United States
	Bogdan S. Chlebus , Leszek Gąsieniec , Alan Gibbons , Andrzej Pelc , Wojciech Rytter, Deterministic broadcasting in unknown radio networks, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.861-870, January 09-11, 2000, San Francisco, California, United States
	Andrea E. F. Clementi , Angelo Monti , Riccardo Silvestri, Selective families, superimposed codes, and broadcasting on unknown radio networks, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.709-718, January 07-09, 2001, Washington, D.C., United States
	Iris Gaber , Yishay Mansour, Broadcast in radio networks, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.577-585, January 22-24, 1995, San Francisco, California, United States
	Eyal Kushilevitz , Yishay Mansour, Computation in noisy radio networks, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.236-243, January 25-27, 1998, San Francisco, California, United States
	Chiu-Yuen Koo, Broadcast in radio networks tolerating byzantine adversarial behavior, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Danilo Bruschi , Massimiliano Del Pinto, Lower bounds for the broadcast problem in mobile radio networks, Distributed Computing, v.10 n.3, p.129-135, April 1997
	Gianluca De Marco, Distributed broadcast in unknown radio networks, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.208-217, January 20-22, 2008, San Francisco, California
	Shlomi Dolev , Seth Gilbert , Rachid Guerraoui , Calvin Newport, Secure communication over radio channels, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Johannes Schneider , Roger Wattenhofer, Coloring unstructured wireless multi-hop networks, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada