On the time-complexity of broadcast in radio networks: an exponential gap between determinism randomization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the time-complexity of broadcast in radio networks: an exponential gap between determinism randomization

Full text

Pdf (1.08 MB)

Source

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

Vancouver, British Columbia, Canada

Pages: 98 - 108

Year of Publication: 1987

ISBN:0-89791-239-4

Authors

Reuven Bar-Yehuda	Department of Computer Science, Technion - Israel Institute of Technology, Haifa 32000, ISRAEL
Oded Goldreich	Department of Computer Science, Technion - Israel Institute of Technology, Haifa 32000, ISRAEL
Alon Itai	Department of Computer Science, Technion - Israel Institute of Technology, Haifa 32000, ISRAEL

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 46, Citation Count: 19

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/41840.41849 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.

	A70	Abramson, N., "The Aloha system - Another approach for computer communications", in Proc. Fall Joint Computer Conf. AFIPS Conf., Vol. 37, (1970).
	BY76	Bently j. and Yao A.C., "An almost optimal algorithm for unbounded search", Inf. Proc. Letters, Vol. 5 (1976), 82-87.
	C79	Capetanakis, J., "Generalized TDMA: The multi-accessing tree protocol", IEEE Trans. Cammun., Vol. COM-27, 1479- 1484, (1979).
	CK85	Chlamtac, I. and Kutten, S., "On Broadcasting in Radio Networks- Problem Analysis and Protocol Design", IEEE Transactions on Communications, December (1985), Vol COM-33, No. 12.
	CW87	Chlamtac, I. and Weinstein O., "The wave expansion approach to broadcasting in multihop radio networks", INFOCOM (April 1987).
	DIX80	Digital-Intel-Xerox, "The Ethemet data link layer and physical layer specification 1.0" (Sept. 1980).
	ES74	Erdos, P., and J. Spencer, Probabilistic Methods in Combinatorics, Academic Press, (1974).
	EGMT	Even, S., Goldreich, O., Moran S. and Tong, P., "On the NP Completeness of Certain Network Testing Problems", Networks, Vol. 14, (1984), 1-24.
	Ga85	Gallager, R., "A perspective on multiaccess channels", IEEE Trans. on Inf. Theory, Vol. IT-31 (1985), 124-142.
	GVF76	Gitman, i., Van Slyke, R.M. and Frank, H., "Routing in Packet-Switching Broadcast Radio Networks", IEEE Transactions on Communications, (August 1976), 926-930.
	H78	Hayes, J.F, "An adaptive technique for local distribution", 1EEE Trans. on Cornmtm., Vol. COM-26, (1978), 1178-1186.
	H87	Hofri, M., "A Feedback-less Distributed Broadcast Algorithm for Multihop Radio Networks with Time-varying Structure", 2nd ACM lntr. MCPR Workshop, Rome (May 1987). Also available as TR-451, Computer Science Dept., Technion, Haifa, Israel (March 1987).
	IR81	Itai, A. and Rodeh, M., "Probabilistic Methods for Breaking Symmetry in Distributive Networks", Foundation of Computer Science (FOCS) 8I, Nashville, Tenn. (Nov. 1981).
	KG85	János Komlós , Albert G. Greenberg, Correction to "An asymptotically nonadaptive algorithm for conflict resolution i, IEEE Transactions on Information Theory, v.31 n.6, p.841-841, Nov. 1985
	R76	M.O. Rabin, "Probabilistic algorithms", Proc. Symp. on New Directions and Recent Results in Algorithms and Complexity, J.F. Traub ed., Academic Press, (1976).
	TM79	Tsybakov, B.S. and Mikhailov, V.A., "Free synchronous packet access in a broadcast channel with feedback", Prob. Inform. Th., Vol. 14, 259-280, (1979).
	VV85	L G Valiant , V V Vazirani, NP is as easy as detecting unique solutions, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.458-463, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22196]
	W87	Weinstein O., "The wave expansion approach to broadcasting in multihop radio networks", M.Sc. Thesis, Computer 3cience Dept., Technion, Haifa, Israel, in preparation, (1987).
	W86	Willard D.E., "Log-logarithmic selection protocols for resolving semaphore conflicts on multiple access channels", to appear in SIAM J. on Comput. (1986).

CITED BY 19

	N. Lynch, A hundred impossibility proofs for distributed computing, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.1-28, June 1989, Edmonton, Alberta, Canada
	Leszek Gąsieniec , Andrzej Pelc , David Peleg, The wakeup problem in synchronous broadcast systems (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.113-121, July 16-19, 2000, Portland, Oregon, United States
	Piotr Indyk, Explicit constructions of selectors and related combinatorial structures, with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.697-704, January 06-08, 2002, San Francisco, California
	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
	Michael Elkin , Guy Kortsarz, Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	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
	N. Alon , A. Bar-Noy , N. Linial , D. Peleg, On the complexity of radio communication, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.274-285, May 14-17, 1989, Seattle, Washington, United States
	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
	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
	A. Bagchi , S. L. Hakimi , E. F. Schmeichel, Gossiping in a Distributed Network, IEEE Transactions on Computers, v.42 n.2, p.253-256, February 1993
	Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, Initializing newly deployed ad hoc and sensor networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA
	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
	Thomas Moscibroda , Roger Wattenhofer, Maximal independent sets in radio networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Thomas Moscibroda , Roger Wattenhofer, Coloring unstructured radio networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Leszek Gasieniec , David Peleg , Qin Xin, Faster communication in known topology radio networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	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
	Leszek Gsieniec , Igor Potapov , Qin Xin, Time efficient centralized gossiping in radio networks, Theoretical Computer Science, v.383 n.1, p.45-58, September, 2007
	Olga Goussevskaia , Thomas Moscibroda , Roger Wattenhofer, Local broadcasting in the physical interference model, Proceedings of the fifth international workshop on Foundations of mobile 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