Constructing multi-reader atomic values from non-atomic values

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Constructing multi-reader atomic values from non-atomic values

Full text

Pdf (1.14 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: 222 - 231

Year of Publication: 1987

ISBN:0-89791-239-4

Authors

James E. Burns	School of Information and Computer Science, Georgia Institute of Technology, Atlanta, GA
Gary L. Peterson	School of Information and Computer Science, Georgia Institute of Technology, Atlanta, GA

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): 1, Downloads (12 Months): 17, Citation Count: 32

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.41859 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.

	BB	Bard Bloom. Constructing two-writer atomic registers. Unpublished manuscript, MIT-LCS, 1986.
	B&P86	J.E. Burns and G.L. Peterson. Constructing an atomic single-writer, multi-reader register from atomic single-writer, single-reader registers. TR GIT-ICS-86/27, School of Info. and Comp. Sci., Georgia Tech., December 1986.
	B&P87a	J.E. Burns and G.L. Peterson. Pure buffers for concurrent reading While writing. Georgia Institute of Technology, School of Information and Computer Science~ GIT-ICS-87/17, April 1087.
	B&P87b	J.E. Burns and G.L. Peters on. Sharp bounds for concurrent reading while writing problems. (In preparation.)
	CH&P	P. J. Courtois , F. Heymans , D. L. Parnas, Concurrent control with “readers” and “writers”, Communications of the ACM, v.14 n.10, p.667-668, Oct. 1971 [doi>10.1145/362759.362813]
	KKV	Lefteris M. Kirousis, Evangelos Kranakis, and Paul M.B. Vit~nyi. Atomic multireader register (detailed abstract). Manuscript, Jan. 1987.
	L77	Leslie Lamport, Concurrent reading and writing, Communications of the ACM, v.20 n.11, p.806-811, Nov. 1977 [doi>10.1145/359863.359878]
	L85	Leslie Lamport. On interproce~s communication. Digital Systems Research Center report" ~8, Dec. 1985. To appear in Distributed Computing.
	N-W87	Richard Newman-Wolfe, A protocol for wait-free, atomic, multi-reader shared variables, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.232-248, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41860]
	P79a	G. L. Peterson, Time-space trade-offs for asynchronous parallel models (Reducibilities and Equivalences), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.224-230, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804416]
	P79b	Gary Lynn Peterson, The complexity of parallel algorithms, 1979
	P83	Gary L. Peterson, Concurrent Reading While Writing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.46-55, Jan. 1983 [doi>10.1145/357195.357198]
	P86	Gary L. Peterson. Some concerns about an algorithm of Vitanyi and Awerbuch. Unpublished manuscript.
	P&B	Gary L. Peterson and James E. Burns. Concurrent reading while writing II: The multi-writer case. Georgia Institute of Technology, School of Information and Computer Science, GIT-ICS- 86/26, Dec. 1986.
	SAG	James H. Anderson , Ambuj K. Singh , Mohamed G. Gouda, The Elusive Atomic Register, University of Texas at Austin, Austin, TX, 1986
	V&A	Paul Vit~myi and Baruch Awerbuch. Atomic shared register access by asynchronous hardware." Proceedings 27th IEEE Syrup. on Foundations of Computer Science, Oct. 1986, pp. 233-243.

CITED BY 32

	P. D. V. Van Der Stok , A. H. T. Janssen-Raemaekers, Real-Time Atomic Multicast Algorithms Implemented on a Shared Memory Multiprocessor, Real-Time Systems, v.24 n.1, p.55-91, January 2003
	J. E. Burns , G. L. Peterson, The ambiguity of choosing, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.145-157, June 1989, Edmonton, Alberta, Canada
	James Anderson, Composite registers, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.15-29, August 22-24, 1990, Quebec City, Quebec, Canada
	Ming Li , John Tromp , Paul M. B. Vitányi, How to share concurrent wait-free variables, Journal of the ACM (JACM), v.43 n.4, p.723-746, July 1996
	Bard Bloom, Constructing two-writer atomic registers, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.249-259, August 10-12, 1987, Vancouver, British Columbia, Canada
	Yehuda Afek , David S. Greenberg , Michael Merritt , Gadi Taubenfeld, Computing with faulty shared objects, Journal of the ACM (JACM), v.42 n.6, p.1231-1274, Nov. 1995
	Richard Newman-Wolfe, A protocol for wait-free, atomic, multi-reader shared variables, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.232-248, August 10-12, 1987, Vancouver, British Columbia, Canada
	Prasad Jayanti , Tushar Deepak Chandra , Sam Toueg, Fault-tolerant wait-free shared objects, Journal of the ACM (JACM), v.45 n.3, p.451-500, May 1998
	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
	Ambuj K. Singh , James H. Anderson , Mohamed G. Gouda, The elusive atomic register, Journal of the ACM (JACM), v.41 n.2, p.311-339, March 1994
	Maurice Herlihy, A methodology for implementing highly concurrent data objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.5, p.745-770, Nov. 1993
	Danny Dolev , Eli Gafni , Nir Shavit, Toward a non-atomic era: l-exclusion as a test case, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.78-92, May 02-04, 1988, Chicago, Illinois, United States
	Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991
	D. Dolev , N. Shavit, Bounded concurrrent time-stamp systems are constructible, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.454-466, May 14-17, 1989, Seattle, Washington, United States
	M. Herlihy, A methodology for implementing highly concurrent data structures, ACM SIGPLAN Notices, v.25 n.3, p.197-206, Mar. 1990
	H. Attiya , D. Dolev , N. Shavit, Bounded polynomial randomized consensus, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.281-293, June 1989, Edmonton, Alberta, Canada
	Maurice P. Herlihy, Impossibility and universality results for wait-free synchronization, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.276-290, August 15-17, 1988, Toronto, Ontario, Canada
	Sibsankar Haldar , Paul Vitányi, Bounded concurrent timestamp systems using vector clocks, Journal of the ACM (JACM), v.49 n.1, p.101-126, January 2002
	J. Aspnes , M. Herlihy, Wait-free data structures in the asynchronous PRAM model, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.340-349, July 02-06, 1990, Island of Crete, Greece
	B. Bloom, Constructing Two-Writer Atomic Registers, IEEE Transactions on Computers, v.37 n.12, p.1506-1514, December 1988
	S. Haldar , K. Vidyasankar, Constructing 1-writer multireader multivalued atomic variables from regular variables, Journal of the ACM (JACM), v.42 n.1, p.186-203, Jan. 1995
	Yehuda Afek , David S. Greenberg , Michael Merritt , Gadi Taubenfeld, Computing with faulty shared memory, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.47-58, August 10-12, 1992, Vancouver, British Columbia, Canada
	Shai Ben-David, The global time assumption and semantics for concurrent systems, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.223-231, August 15-17, 1988, Toronto, Ontario, Canada
	Maurice Herlihy, Impossibility results for asynchronous PRAM (extended abstract), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.327-336, July 21-24, 1991, Hilton Head, South Carolina, United States
	Rida A. Bazzi , Gil Neiger , Gary L. Peterson, On the use of registers in achieving wait-free consensus, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.354-362, August 14-17, 1994, Los Angeles, California, United States
	Maurice Herlihy, Randomized wait-free concurrent objects (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.11-21, August 19-21, 1991, Montreal, Quebec, Canada
	Rida A. Bazzi , Gil Neiger , Gary L. Peterson, On the use of registers in achieving wait-free consensus, Distributed Computing, v.10 n.3, p.117-127, April 1997
	James H. Anderson, Composite registers, Distributed Computing, v.6 n.3, p.141-154, April 1993
	Ambuj K. Singh, On reasoning with the global time assumption, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.89-103, March 1992
	James H. Anderson, Multi-writer composite registers, Distributed Computing, v.7 n.4, p.175-195, May 1994
	Hai Huang , Padmanabhan Pillai , Kang G. Shin, Improving Wait-Free Algorithms for Interprocess Communication in Embedded Real-Time Systems, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.303-316, June 10-15, 2002
	S. Halder , K. Vidyasankar, Counterexamples to a one writer multireader atomic variable construction of Burns and Peterson, ACM SIGOPS Operating Systems Review, v.26 n.1, p.78-87, Jan. 1992