Fast, scalable synchronization with minimal hardware support

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast, scalable synchronization with minimal hardware support

Full text

Pdf (1.22 MB)

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: 171 - 182

Year of Publication: 1993

ISBN:0-89791-613-1

Authors

Jae-Heon Yang
James H. Anderson

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.164072 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	A. Agarwal , M. Cherian, Adaptive backoff synchronization techniques, Proceedings of the 16th annual international symposium on Computer architecture, p.396-406, April 1989, Jerusalem, Israel
	2	J. Anderson, "A Fine-Grained Solution to the Mutual Exclusion Problem", to appear in Acta In/ormatica .
	3	T. E. Anderson, The Performance of Spin Lock Alternatives for Shared-Money Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.6-16, January 1990 [doi>10.1109/71.80120]
	4	BBN Advanced Computers, Inside the TC2000 Computer, February, 1990.
	5	K. Mani Chandy, Parallel program design: a foundation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
	6	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]
	7	James R. Goodman , Mary K. Vernon , Philip J. Woest, Efficient synchronization primitives for large-scale cache-coherent multiprocessors, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.64-75, April 03-06, 1989, Boston, Massachusetts, United States
	8	Gary Granunke , Shreekant Thakkar, Synchronization Algorithms for Shared-Memory Multiprocessors, Computer, v.23 n.6, p.60-69, June 1990 [doi>10.1109/2.55501]
	9	J. Kessels, "Arbitration Without Common Modifiable Variables", Acts Informatica, Vol. 17, 1982, pp. 135-141.
	10	Clyde P. Kruskal , Larry Rudolph , Marc Snir, Efficient synchronization of multiprocessors with shared memory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.579-601, Oct. 1988 [doi>10.1145/48022.48024]
	11	Leslie Lamport, A fast mutual exclusion algorithm, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.1-11, Feb. 1987 [doi>10.1145/7351.7352]
	12	John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
	13	Gary L. Peterson , Michael J. Fischer, Economical solutions for the critical section problem in a distributed system (Extended Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.91-97, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803398]
	14	G. Peterson, "Myths About the Mutual Exclusion Problem", Informalion Processing Lelters, Vol. 12, No. 3, June, 1981, pp. 115-116.
	15	Eugene Styer, Improving fast mutual exclusion, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.159-168, August 10-12, 1992, Vancouver, British Columbia, Canada [doi>10.1145/135419.135453]
	16	P.-C. Yew , N.-F. Tzeng , D. H. Lawrie, Distributing hot-spot addressing in large-scale multiprocessors, IEEE Transactions on Computers, v.36 n.4, p.388-395, April 1987 [doi>10.1109/TC.1987.1676921]

CITED BY 12

	Rajeev Alur , Gadi Taubenfeld, Contention—free complexity of shared memory algorithms, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.61-70, August 14-17, 1994, Los Angeles, California, United States
	Subodh Kumar , Chun-Fa Chang , Dinesh Manocha, Scalable parallel algorithms for interactive visualization of curved surfaces, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.7-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States
	Manhoi Choy , Ambuj K. Singh, Adaptive solutions to the mutual exclusion problem, Distributed Computing, v.8 n.1, p.1-17, August 1994
	James H. Anderson, Lamport on mutual exclusion: 27 years of planting seeds, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.3-12, August 2001, Newport, Rhode Island, United States
	Jae-Heon Yang , James H. Anderson, Time bounds for mutual exclusion and related problems, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.224-233, May 23-25, 1994, Montreal, Quebec, Canada
	Robert Cypher, The communication requirements of mutual exclusion, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.147-156, June 24-26, 1995, Santa Barbara, California, United States
	James H. Anderson , Mark Moir, Using k-exclusion to implement resilient, scalable shared objects (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.141-150, August 14-17, 1994, Los Angeles, California, United States
	Leonidas I. Kontothanassis , Robert W. Wisniewski , Michael L. Scott, Scheduler-conscious synchronization, ACM Transactions on Computer Systems (TOCS), v.15 n.1, p.3-40, Feb. 1997
	Cynthia Dwork , Maurice Herlihy , Orli Waarts, Contention in shared memory algorithms, Journal of the ACM (JACM), v.44 n.6, p.779-805, Nov. 1997
	James H. Anderson , Yong-Jik Kim, An improved lower bound for the time complexity of mutual exclusion, Distributed Computing, v.15 n.4, p.221-253, December 2002
	Xiaodong Zhang , Yong Yan , Robert Castañeda, Evaluating and Designing Software Mutual Exclusion Algorithms on Shared-Memory Multiprocessors, IEEE Parallel & Distributed Technology: Systems & Technology, v.4 n.1, p.25-42, March 1996
	James H. Anderson , Mark Moir, Using local-spin k-exclusion algorithms to improve wait-free object implementations, Distributed Computing, v.11 n.1, p.1-20, December 1997