Atomic snapshots of shared memory

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Atomic snapshots of shared memory

Full text

Pdf (1.25 MB)

Source

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

Quebec City, Quebec, Canada

Pages: 1 - 13

Year of Publication: 1990

ISBN:0-89791-404-X

Authors

Yehuda Afek	Tel-Aviv University and AT&T Bell Laboratories
Danny Dolev	IBM Almaden Research Center and Hebrew University
Hagit Attiya	Laboratory for Computer Science, MIT
Eli Gafni	Tel-Aviv University and University of California, Los Angeles
Michael Merritt	AT&T Bell Laboratories
Nir Shavit	IBM Almaden Research Center and Stanford University

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): 2, Downloads (12 Months): 11, Citation Count: 29

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

	A88	Karl Abrahamson, On achieving consensus using a shared memory, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.291-302, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62594]
	A89a	James H. Anderson, Composite Registers, University of Texas at Austin, Austin, TX, 1990
	A89b	James H. Anderson, Multiple-Writer Composite Registers, University of Texas at Austin, Austin, TX, 1990
	An90	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 [doi>10.1145/93385.93396]
	AG88	James H. Anderson , Mohamed G. Gouda, The Virtue of Patience: Concurrent Programming with and Without Waiting, University of Texas at Austin, Austin, TX, 1990
	AH89	James Aspnes , M. Herlihy, Fast randomized consensus using shared memory, Journal of Algorithms, v.11 n.3, p.441-461, Sep. 1990 [doi>10.1016/0196-6774(90)90021-6]
	A90	James Aspnes, Time-and space-efficient randomized consensus, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.325-331, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93433]
	AH90	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 [doi>10.1145/97444.97701]
	ABD	Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.363-375, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93441]
	ADS89	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 [doi>10.1145/72981.73001]
	BT84	Gabriel Bracha , Sam Toueg, A distributed algorithm for generalized deadlock detection, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.285-301, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806756]
	Blo87	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 [doi>10.1145/41840.41861]
	CL85	K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
	DGS88	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 [doi>10.1145/62212.62220]
	DS89	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 [doi>10.1145/73007.73051]
	G86	E. Gafni, "Perspective on Distributed Network Protocols: A Case for Building Blocks," MILCOM '86, October 1986, Monterey, California.
	H88	M.P. tterlihy, "Wait Free Implementations of Concurrent Objects," Proc. 7th A CM Syrup. on Principles of Distribuled Computing, 1988, pp. 276-290.
	HW87	M. P. Herlihy , J. M. Wing, Axioms for concurrent objects, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.13-26, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41627]
	K78	Howard P. Katseff, A new solution to the critical section problem, Proceedings of the tenth annual ACM symposium on Theory of computing, p.86-88, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804335]
	L86a	L. Lamport, "On Interprocess Communication. Part I" Basic Formalism," Distributed Computing 1, 2 1986, 77-85.
	L86b	L. Lamport, "On Interprocess Communication. Part II: Algorithms," Distributed Computing 1, ~ 1986, pp. 86-101.
	L86c	Leslie Lamport, The mutual exclusion problem: partII—statement and solutions, Journal of the ACM (JACM), v.33 n.2, p.327-348, April 1986 [doi>10.1145/5383.5385]
	LT87	Nancy A. Lynch , Mark R. Tuttle, Hierarchical correctness proofs for distributed algorithms, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.137-151, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41852]
	LTV89	M. Li, J. Tromp and P. M.B. Vitanyi, "How to Share Concurrent Wait-Free Variables," ICALP 1989. Expanded version: Report CS-R8916, CWI, Amsterdam, April I989.
	M86	J. Misra, Axioms for memory access in asynchronous hardware systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.1, p.142-153, Jan. 1986 [doi>10.1145/5001.5007]
	OG76	S. Owicki and D. Gries, "An Axiomatic Proof Technique for Parallel Programs," Acta lnformatica, 6(1):319-340, 1976.
	Owi75	Susan Speer Owicki, Axiomatic proof techniques for parallel programs., 1975
	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]
	PB87	C.L. Peterson, and J. E. Burns, "Concurrent Reading While Writing Ii ~ The Multi- Writer Case," Proc. 28th Annual IEEE Syrup. on Foundations of Computer Science, 1987, pp. 383-392.
	S88	R. Schaffer, "On the Correctness of Atomic Multi-Writer Registers," MIT/LCS/TM- 364, June 1988.
	VA86	P.M.B. Vitanyi and B. Awerbuch, "Atomic Shared Register Access by Asynchronous Hardware," Proc. 27th IEEE Annual Syrup. on Foundations of Computer Science, pp. 233-243, 1986.

CITED BY 29

	Yehuda Afek , Dalia Dauber , Dan Touitou, Wait-free made fast, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.538-547, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Yehuda Afek , Eytan Weisberger , Hanan Weisman, A completeness theorem for a class of synchronization objects, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.159-170, August 15-18, 1993, Ithaca, New York, United States
	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
	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
	Maurice Herlihy , Nir Shavit, The asynchronous computability theorem for t-resilient tasks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.111-120, May 16-18, 1993, San Diego, California, United States
	Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.363-375, August 22-24, 1990, Quebec City, Quebec, Canada
	Elizabeth Borowsky , Eli Gafni, Generalized FLP impossibility result for t-resilient asynchronous computations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.91-100, May 16-18, 1993, San Diego, California, United States
	Hagit Attiya , Ophir Rachman, Atomic snapshots in O(n log n) operations, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.29-40, August 15-18, 1993, Ithaca, New York, United States
	Maurice P. Herlihy , J. E. B. Moss, Lock-free garbage collection for multiprocessors, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.229-236, July 21-24, 1991, Hilton Head, South Carolina, United States
	L. M. Kirousis , P. Spirakis , P. Tsigas, Reading Many Variables in One Atomic Operation: Solutions with Linear or Sublinear Complexity, IEEE Transactions on Parallel and Distributed Systems, v.5 n.7, p.688-696, July 1994
	Yehuda Afek , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, A bounded first-in, first-enabled solution to the l-exclusion problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.939-953, May 1994
	Elizabeth Borowsky , Eli Gafni, Immediate atomic snapshots and fast renaming, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.41-51, August 15-18, 1993, Ithaca, New York, United States
	Maurice Herlihy , Nir Shavit, The topological structure of asynchronous computability, Journal of the ACM (JACM), v.46 n.6, p.858-923, Nov. 1999
	James Aspnes , William Hurwood, Spreading rumors rapidly despite an adversary, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.143-151, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Elizabeth Borowsky , Eli Gafni, A simple algorithmically reasoned characterization of wait-free computation (extended abstract), Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.189-198, August 21-24, 1997, Santa Barbara, California, United States
	Cynthia Dwork , Orli Waarts, Simple and efficient bounded concurrent timestamping or bounded concurrent timestamp systems are comprehensible!, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.655-666, May 04-06, 1992, Victoria, British Columbia, Canada
	M. P. Herlihy , J. E. B. Moss, Lock-Free Garbage Collection for Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.3 n.3, p.304-311, May 1992
	Jaap-Henk Hoepman , Marina Papatriantafilou , Philippas Tsigas, Self-stabilization of wait-free shared memory objects, Journal of Parallel and Distributed Computing, v.62 n.5, p.818-842, May 2002
	Cynthia Dwork , Maurice Herlihy, Bounded round number, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.53-64, August 15-18, 1993, Ithaca, New York, United States
	Ömer Eǧecioǧlu , Ambuj K. Singh, Naming symmetric processes using shared variables, Distributed Computing, v.8 n.1, p.19-38, August 1994
	Ho-fung Leung , Hing-fung Ting, An Optimal Algorithm for Global Termination Detection in Shared-Memory Asynchronous Multiprocessor Systems, IEEE Transactions on Parallel and Distributed Systems, v.8 n.5, p.538-543, May 1997
	James H. Anderson, Composite registers, Distributed Computing, v.6 n.3, p.141-154, April 1993
	Prasad Jayanti, f-arrays: implementation and applications, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Michael Merritt , Gadi Taubenfeld, Atomic m-register operations, Distributed Computing, v.7 n.4, p.213-221, May 1994
	Eli Gafni , Rachid Guerraoui , Bastian Pochon, From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Prasad Jayanti, An optimal multi-writer snapshot algorithm, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	James H. Anderson, Multi-writer composite registers, Distributed Computing, v.7 n.4, p.175-195, May 1994
	Danny Dolev, Century papers at the first quarter-century milestone, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, p.3-4, July 23-26, 2006, Denver, Colorado, USA
	Eli Gafni, The extended BG-simulation and the characterization of t-resiliency, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA