On contention resolution protocols and associated probabilistic phenomena

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On contention resolution protocols and associated probabilistic phenomena

Full text

Pdf (1.09 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

Pages: 153 - 162

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

P. D. MacKenzie	Department of Computer Science, University of Texas at Austin
C. G. Plaxton	Department of Computer Science, University of Texas at Austin
R. Rajaraman	Department of Computer Science, University of Texas at Austin

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 14, Citation Count: 7

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

	1	N. Abramson. The ALOHA system. In N. Abramson and F. Kuo, editors, Computer-Communication Networks. Prentice-Hall. Englewoocl Cliffs, N J, 1973_
	2	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]
	3	N. Alon and J. H. Spencer. The Probabilistic Method. Wiley- Interscience, New York, NY, 1992.
	4	R. J. Anderson and G. L. Miller. Optical communication for pointer based algorithms. Technical Report CRI-88-14, Computer Science Department, University of Southern Callfornia, 1988.
	5	H. Chernoff. A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics, 23:493-509, 1952.
	6	Martin Dietzfelbinger , Friedhelm Meyer auf der Heide, Simple, efficient shared memory simulations, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.110-119, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165246]
	7	Mihály Geréb-Graus , Thanasis Tsantilas, Efficient optical communication in parallel computers, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.41-48, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140906]
	8	L. A. Goldberg and M. Jerrum. A sub-logarithmic communication algorithm for the completely connected optical communication parallel computer. Technical Report ECS-LFCS- 92-234, Laboratory for Foundations of Computer Science, Department of Computer Science, University of Edinburgh, September 1992.
	9	Leslie Ann Goldberg , Mark Jerrum , Tom Leighton , Satish Rao, A doubly logarithmic communication algorithm for the completely connected optical communication parallel computer, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.300-309, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.166108]
	10	Leslie Ann Goldberg , Yossi Matias , Satish Rao, An optical simulation of shared memory, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.257-267, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181406]
	11	Albert G. Greenberg , Philippe Flajolet , Richard E. Ladner, Estimating the multiplicities of conflicts to speed their resolution in multiple access channels, Journal of the ACM (JACM), v.34 n.2, p.289-325, April 1987 [doi>10.1145/23005.23006]
	12	Albert G. Greenberg , Schmuel Winograd, A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels, Journal of the ACM (JACM), v.32 n.3, p.589-596, July 1985 [doi>10.1145/3828.214125]
	13	Richard M. Karp , Michael Luby , Friedhelm Meyer auf der Heide, Efficient PRAM simulation on a distributed memory machine, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.318-326, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129743]
	14	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
	15	P. D. MacKenzie , C. G Plaxton , R. Rajaraman, On Contention Resolution Protocols and Associated Probabilistic Phenomena, University of Texas at Austin, Austin, TX, 1994
	16	C. U. Martel , T. P. Vayda, The complexity of selection resolution, conflict resolution and maximum finding on multiple access channels, VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	17	Robert M. Metcalfe , David R. Boggs, Ethernet: distributed packet switching for local computer networks, Communications of the ACM, v.19 n.7, p.395-404, July 1976 [doi>10.1145/360248.360253]
	18	F. Meyer auf der Heide, C. Scheideler, and V. Stemann. Fast, simple dictionaries and shared memory simulations on distributed memory machines; upper and lower bounds. Manuscript, January 1994.
	19	Eli Upfal , Avi Wigderson, How to share memory in a distributed system, Journal of the ACM (JACM), v.34 n.1, p.116-127, Jan. 1987 [doi>10.1145/7531.7926]
	20	L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	21	A. C. Yao. Lower bounds by probabilistic arguments. In Proceedings of the 2#th Annual IEEE Symposium on Foundations of Computer Science, pages 420-428, October 1983.

CITED BY 7

	Prabhakar Raghavan , Eli Upfal, Stochastic contention resolution with short delays, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.229-237, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Dannie Durand , Ravi Jain , David Tseytlin, Applying randomized edge coloring algorithms to distributed communication: an experimental study, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.264-274, June 24-26, 1995, Santa Barbara, California, United States
	Leslie Ann Goldberg , Mark Jerrum , Philip D. MacKenzie, An Ω(√ log log n) lower bound for routing in optical networks, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.147-156, June 27-29, 1994, Cape May, New Jersey, United States
	Dannie Durand , Ravi Jain , David Tseytlin, Parallel I/O scheduling using randomized, distributed edge coloring algorithms, Journal of Parallel and Distributed Computing, v.63 n.6, p.611-618, June 2003
	Leslie Ann Goldberg , Yossi Matias , Satish Rao, An optical simulation of shared memory, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.257-267, June 27-29, 1994, Cape May, New Jersey, United States
	Volker Stemann, Parallel balanced allocations, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.261-269, June 24-26, 1996, Padua, Italy
	Sailesh Kumar , Patrick Crowley, Segmented hash: an efficient hash table implementation for high performance networking subsystems, Proceedings of the 2005 symposium on Architecture for networking and communications systems, October 26-28, 2005, Princeton, NJ, USA