Log-logarithmic protocols for resolving ethernet and semaphore conflicts

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Log-logarithmic protocols for resolving ethernet and semaphore conflicts

Full text

Pdf (642 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the sixteenth annual ACM symposium on Theory of computing table of contents

Pages: 512 - 521

Year of Publication: 1984

ISBN:0-89791-133-4

Author

Dan E. Willard

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/800057.808721 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	J. Burns, M. Fischer, P. Jackson, N. Lynch and G. Peterson, "Shared data requirements for implementating mutual exclusion using test-and-set primitives ", Univ. of Washington report F8-08-08, 1978.
	2	J. Capetaannkis, "Tree algorithms for packet broadcast channels", IEEE Trans. on Information Theory (25) 1979, pp. 505-515.
	3	E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, v.8 n.9, p.569, Sept. 1965 [doi>10.1145/365559.365617]
	4	W. Feller, Introduction to Probability Theory, Wiley, New York, 1968.
	5	Albert Gordon Greenberg, Efficient algorithms for multiple access channels, 1983
	6	A. Greenberg and R. Ladner, "Estimating the multiplicity of conflicts in multiple access channels", 24th IEEE Symp. FOCS, 1983, pp. 383-392.
	7	Donald E. Knuth, Additional comments on a problem in concurrent programming control, Communications of the ACM, v.9 n.5, p.321-322, May 1966 [doi>10.1145/355592.365595]
	8	R. Metcalfe, "Steady state analysis of slotted and controlled Aloha systems with blocking", Proc. 6th Hawaii Conf. on Syst. Sci., 1973, pp. 375-38O.
	9	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]
	10	V.A. Mikhailov and B.S. Tsybakov, "Upper bound for the capacity of a random multiple access system", original Russian version, Problomy Peredaihi Informntsii (17) 1981, pp. 90-95; translated into English in Problems of Information Transmission.
	11	N. Pippenger, "Bounds on the performance of protocols on multiple-access broadcast channels", IBM repot RC7742(33525), 1979.
	12	M. Rabin, "N-process synchronization by 4 log N-valued shared variables", 21st IEEE Symp. on FOCS, 1980, pp. 407-410.
	13	John F. Shoch , Jon A. Hupp, Measured performance of an Ethernet local network, Communications of the ACM, v.23 n.12, p.711-721, Dec. 1980 [doi>10.1145/359038.359044]
	14	D.E. Willard, "Predicate Retrieval Theory", 21-st Alleton Conference on Communications, Control and Computing, 1983, pp. 665-675.
	15	Dan E. Willard, Sampling Algorithms for Differential Batch Retrieval Problems (Extended Abstract), Proceedings of the 11th Colloquium on Automata, Languages and Programming, p.514-526, July 16-20, 1984

CITED BY 3

	Yehuda Afek , Gad M. Landau , Baruch Schieber , Moti Yung, The power of multimedia: combining point-to point and multi-access networks, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.90-104, August 15-17, 1988, Toronto, Ontario, Canada
	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
	Michael A. Bender , Martin Farach-Colton , Simai He , Bradley C. Kuszmaul , Charles E. Leiserson, Adversarial contention resolution for simple channels, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA