Linearizability: a correctness condition for concurrent objects

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Linearizability: a correctness condition for concurrent objects

Full text

Pdf (2.21 MB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 12 , Issue 3 (July 1990) table of contents

Pages: 463 - 492

Year of Publication: 1990

ISSN:0164-0925

Authors

Maurice P. Herlihy	Carnegie-Mellon Univ., Pittsburgh, PA
Jeannette M. Wing	Carnegie-Mellon Univ., Pittsburgh, PA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 39, Downloads (12 Months): 360, Citation Count: 265

Additional Information:

abstract references cited by index terms review 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/78969.78972 What is a DOI?

ABSTRACT

A concurrent object is a data object shared by concurrent processes. Linearizability is a correctness condition for concurrent objects that exploits the semantics of abstract data types. It permits a high degree of concurrency, yet it permits programmers to specify and reason about concurrent objects using known techniques from the sequential domain. Linearizability provides the illusion that each operation applied by concurrent processes takes effect instantaneously at some point between its invocation and its response, implying that the meaning of a concurrent object's operations can be given by pre- and post-conditions. This paper defines linearizability, compares it to other correctness conditions, presents and demonstrates a method for proving the correctness of implementations, and shows how to reason about concurrent objects, given they are linearizable.

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	AEADI, M., AND LAMPORT, L. The existence of refinement mappings. Tech. Rep. 29, DEC Systems Research Center, Aug. 1988.
	2	GOGUEN, J. A., THATCHER, J. W., WAGNER, E. G., AND WRIGHT, J.B. Abstract data types as initial algebras and correctness of data representations. In Proceedings of the Conference on Computer Graphics, Pattern Recognition and Data Structures (May 1975). ACM, New York, 1975, 89-93.
	3	Krzysztof R. Apt , Nissim Francez , Willem P. de Roever, A Proof System for Communicating Sequential Processes, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.3, p.359-385, July 1980 [doi>10.1145/357103.357110]
	4	BAYER, R., AND SCHKOLNICK, M. Concurrency of operations on B-trees. Acta In{. 1, 1 (1977), 1-21.
	5	BIRKHOFF, G., AND LIPSON, J.D. Heterogeneous algebras. J. Comb. Theor. 8 (1970), 115-133.
	6	BISWAS, Z., AND BROWNE, J.C. Simultaneous update of priority structures. In Proceedings of the 1987 International Conference on Parallel Processing (St. Charles, Ill., 1987). 124-131.
	7	Stephen D. Brookes, An Axiomatic Treatment of a Parallel Programming Language, Proceedings of the Conference on Logic of Programs, p.41-60, June 17-19, 1985
	8	BURSTALL, R. M., AND GOGUEN, J. A. Putting theories together to make specifications. In Fifth International Joint Conference on Artificial Intelligence (Cambridge, Mass., Aug. 1977). 1045-1058. Invited paper.
	9	DEPARTMENT OF DEFENSE. Reference Manual for the ADA Programming Language. ANSI/ MIL-STD-1815A-1983, 1983.
	10	Hartmut Ehrig , B. Mahr, Fundamentals of Algebraic Specification I, Springer-Verlag New York, Inc., Secaucus, NJ, 1985
	11	ELLIS, C.S. Concurrent search and insertion in 2-3 trees. Acta Inf. 14 (1980), 63-86.
	12	K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
	13	Ray Ford , Jim Calhoun, Concurrency control mechanisms and the serializability of concurrent tree algorithms, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588020]
	14	GERTH, R., AND DEROEVER, W.P. Proving monitors revisited: A first step towards verifying object oriented systems. Fundamental Inf. 9 (1986), 371-400.
	15	Allan Gottlieb , Boris D. Lubachevsky , Larry Rudolph, Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.164-189, April 1983 [doi>10.1145/69624.357206]
	16	GUIBAS, L., AND SEDGEWICK, R. A dichromatic framework for balanced trees. In 19th ACM Symposium on Foundations of Computer Science (Providence, R.I., 1978). ACM, New York, 1978, 8-21.
	17	John Vogel Guttag, The specification and application to programming of abstract data types., 1975
	18	John V. Guttag , Ellis Horowitz , David R. Musser, Abstract data types and software validation, Communications of the ACM, v.21 n.12, p.1048-1064, Dec. 1978 [doi>10.1145/359657.359666]
	19	GUTTAG, J. V., HORNING, J. Z., AND WING, J.M. Larch in five easy pieces. Tech. Rep. 5, DEC Systems Research Center, July 1985.
	20	GUTTAG, J. V., HORNING, J. J., AND WING, J.M. The Larch family of specification languages. IEEE Softw. 2, 5 (Sept. 1985), 24-36.
	21	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]
	22	Maurice Herlihy, Dynamic quorum adjustment for partitioned data, ACM Transactions on Database Systems (TODS), v.12 n.2, p.170-194, June 1987 [doi>10.1145/22952.22953]
	23	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 [doi>10.1145/62546.62593]
	24	C. A. R. Hoare, An axiomatic basis for computer programming, Communications of the ACM, v.12 n.10, p.576-580, Oct. 1969 [doi>10.1145/363235.363259]
	25	HOARE, C. A.R. Proof of correctness of data representations. Acta Inf. 1, I (1972), 271-281.
	26	C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
	27	C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
	28	John H. Howard, Proving monitors, Communications of the ACM, v.19 n.5, p.273-279, May 1976 [doi>10.1145/360051.360079]
	29	Cliff B. Jones, Software Development: A Rigorous Approach, Prentice Hall PTR, Upper Saddle River, NJ, 1980
	30	Clyde P Kruskal , Larry Rudolph , Marc Snir, Efficient synchronization of multiprocessors with shared memory, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.218-228, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10609]
	31	LAMPORT, L. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Trans. Comput. C-28, 9 (Sept. 1979), 690-691.
	32	Leslie Lamport, Specifying Concurrent Program Modules, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.190-222, April 1983 [doi>10.1145/69624.357207]
	33	Philip L. Lehman , s. Bing Yao, Efficient locking for concurrent operations on B-trees, ACM Transactions on Database Systems (TODS), v.6 n.4, p.650-670, Dec. 1981 [doi>10.1145/319628.319663]
	34	Z Manna , Amir Pnueli, Verification of concurrent programs, Part I: The temporal framework, Stanford University, Stanford, CA, 1981
	35	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]
	36	NAKAJIMA, R., HONDA, M., AND NAKAHARA, H. Hierarchical program specification and verification--A many-sorted logical approach. Acta Inf. 14 (1980), 135-155.
	37	Susan Owicki , David Gries, Verifying properties of parallel programs: an axiomatic approach, Communications of the ACM, v.19 n.5, p.279-285, May 1976 [doi>10.1145/360051.360224]
	38	OWICKI, S., AND GRIES, D. An axiomatic proof technique for parallel programs. Acta Inf. 6, 4 (1976), 319-340.
	39	Susan Owicki , Leslie Lamport, Proving Liveness Properties of Concurrent Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.455-495, July 1982 [doi>10.1145/357172.357178]
	40	Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM (JACM), v.26 n.4, p.631-653, Oct. 1979 [doi>10.1145/322154.322158]
	41	David P. Reed, Implementing atomic actions on decentralized data, ACM Transactions on Computer Systems (TOCS), v.1 n.1, p.3-23, Feb. 1983 [doi>10.1145/357353.357355]
	42	Yehoshua Sagiv, Concurrent operations on B-trees with overtaking, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.28-37, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325409]
	43	STANDISH, W. A. Data structures: An axiomatic approach. Rep. 2639, Bolt, Beranek, and Newman, Cambridge, Mass., Aug. 1973.
	44	STIRLING, C. A generalization of Owicki-Gries-Hoare logic for a concurrent while language. Tech. Rep., Edinburgh Univ., March 1987.
	45	HERLIHY, M. P., AND WING, J.M. Axioms for concurrent objects. Tech. Rep. CMU-CS-86-154, Computer Science Dept., Carnegie Mellon Univ., 1986.
	46	W. E. Weihl, Local atomicity properties: modular concurrency control for abstract data types, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.2, p.249-282, April 1989 [doi>10.1145/63264.63518]

CITED BY 265

	John Howard , Shmuel Katz, Reconciliations, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.14-21, August 14-17, 1994, Los Angeles, California, United States
	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
	Svend Frølund , Rachid Guerraoui, X-ability: a theory of replication, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.229-237, July 16-19, 2000, Portland, Oregon, United States
	Antonio Fernández , Ernesto Jiménez , Vicent Cholvi, On the interconnection of causal memory systems, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.163-170, July 16-19, 2000, Portland, Oregon, United States
	Hagit Attiya , Jennifer L. Welch, Sequential consistency versus linearizability, ACM Transactions on Computer Systems (TOCS), v.12 n.2, p.91-122, May 1994
	Haifeng Yu , Amin Vahdat, Minimal replication cost for availability, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	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
	Phillip B. Gibbons , Michael Merritt, Specifying non-blocking shared memories (extended abstract), Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.306-315, June 29-July 01, 1992, San Diego, California, United States
	Klaus-Peter Löhr, Concurrency annotations, ACM SIGPLAN Notices, v.27 n.10, p.327-340, Oct. 1992
	Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada
	Wai-Kau Lo , Vassos Hadzilacos, All of us are smarter than any of us: wait-free hierarchies are not robust, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.579-588, May 04-06, 1997, El Paso, Texas, United States
	H. Rebecca Callison, A time-sensitive object model for real-time systems, ACM Transactions on Software Engineering and Methodology (TOSEM), v.4 n.3, p.287-317, July 1995
	Elizabeth Borowsky , Eli Gafni , Yehuda Afek, Consensus power makes (some) sense! (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.363-372, August 14-17, 1994, Los Angeles, 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 Herlihy , Nir Shavit, The topological structure of asynchronous computability, Journal of the ACM (JACM), v.46 n.6, p.858-923, Nov. 1999
	Yehuda Afek , Gideon Stupp, Delimiting the power of bounded size synchronization objects (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.42-51, August 14-17, 1994, Los Angeles, California, United States
	Prasad Jayanti , King Tan , Sam Toueg, Time and space lower bounds for non-blocking implementations (preliminary version), Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.257-266, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Marta Patiño-Martínez , Ricardo Jiménez-Peris , Sergio Arévalo, Synchronizing group transaction with rendezvous in a distributed Ada environment, Proceedings of the 1998 ACM symposium on Applied Computing, p.2-9, February 27-March 01, 1998, Atlanta, Georgia, 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
	Marios Mavronicolas , Michael Merritt , Gadi Taubenfeld, Sequentially consistent versus linearizable counting networks, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.133-142, May 04-06, 1999, Atlanta, Georgia, United States
	Alan Fekete , M. Frans Kaashoek , Nancy Lynch, Implementing sequentially consistent shared objects using broadcast and point-to-point communication, Journal of the ACM (JACM), v.45 n.1, p.35-69, Jan. 1998
	Nir Shavit , Asaph Zemach, Combining funnels: a new twist on an old tale…, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.61-70, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Guy E. Blelloch , Perry Cheng , Phillip B. Gibbons, Room synchronizations, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.122-133, July 2001, Crete Island, Greece
	Hagit Attiya , Roy Friedman, A correctness condition for high-performance multiprocessors (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.679-690, May 04-06, 1992, Victoria, British Columbia, 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
	Phillip B. Gibbons , John L. Bruno , Steven Phillips, Post-mortem black-box correctness tests for basic parallel data structures, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.44-53, June 27-30, 1999, Saint Malo, France
	Faith Fich , Maurice Herlihy , Nir Shavit, On the space complexity of randomized synchronization, Journal of the ACM (JACM), v.45 n.5, p.843-862, Sept. 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
	Hagit Attiya , Eyal Dagan, Improved implementations of binary universal operations, Journal of the ACM (JACM), v.48 n.5, p.1013-1037, September 2001
	Christian Queinnec, Locality, causality and continuations, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.91-102, July-Sept. 1994
	Philippas Tsigas , Yi Zhang, A simple, fast and scalable non-blocking concurrent FIFO queue for shared memory multiprocessor systems, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.134-143, July 2001, Crete Island, Greece
	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
	Roy Friedman, Implementing hybrid consistency with high-level synchronization operations, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.229-240, August 15-18, 1993, Ithaca, New York, United States
	Eli Gafni , Michael Merritt , Gadi Taubenfeld, The concurrency hierarchy, and algorithms for unbounded concurrency, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.161-169, August 2001, Newport, Rhode Island, United States
	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
	John D. Valois, Lock-free linked lists using compare-and-swap, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.214-222, August 20-23, 1995, Ottowa, Ontario, Canada
	Prasad Jayanti, On the robustness of Herlihy's hierarchy, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.145-157, August 15-18, 1993, Ithaca, New York, United States
	James H. Anderson , Mark Moir, Universal constructions for multi-object operations, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.184-193, August 20-23, 1995, Ottowa, Ontario, Canada
	Divyakant Agrawal , Manhoi Choy , Hong Va Leong , Ambuj K. Singh, Mixed consistency: a model for parallel programming (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.101-110, August 14-17, 1994, Los Angeles, California, United States
	Nir Shavit , Asaph Zemach, Scalable concurrent priority queue algorithms, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.113-122, May 04-06, 1999, Atlanta, Georgia, United States
	Mukund Raghavachari , Anne Rogers, Ace: a language for parallel programming with customizable protocols, ACM Transactions on Computer Systems (TOCS), v.17 n.3, p.202-248, Aug. 1999
	Eric Ruppert, Determining consensus numbers, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.93-99, August 21-24, 1997, Santa Barbara, California, United States
	Mark Moir, Practical implementations of non-blocking synchronization primitives, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.219-228, August 21-24, 1997, Santa Barbara, California, United States
	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
	Mustaque Ahamad , Rida A. Bazzi , Ranjit John , Prince Kohli , Gil Neiger, The power of processor consistency, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.251-260, June 30-July 02, 1993, Velen, Germany
	Wai-Kau Lo , Vassos Hadziolacos, On the power of shared object types to implement one-resilient Consensus, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.101-110, August 21-24, 1997, Santa Barbara, California, United States
	Eric Ruppert, Consensus numbers of multi-objects, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.211-217, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Prasad Jayanti, A lower bound on the local time complexity of universal constructions, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.183-192, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Mukund Raghavachari , Anne Rogers, Ace: linguistic mechanisms for customizable protocols, ACM SIGPLAN Notices, v.32 n.7, p.80-89, July 1997
	Prasad Jayanti, A time complexity lower bound for randomized implementations of some shared objects, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.201-210, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Nir Shavit , Dan Touitou, Elimination trees and the construction of pools and stacks: preliminary version, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.54-63, June 24-26, 1995, Santa Barbara, California, United States
	Phillip B. Gibbons , Ephraim Korach, On testing cache-coherent shared memories, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.177-188, June 27-29, 1994, Cape May, New Jersey, United States
	Hagit Attiya , Roy Friedman, Programming DEC-Alpha based multiprocessors the easy way (extended abstract), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.157-166, June 27-29, 1994, Cape May, New Jersey, United States
	Maurice Herlihy , Beng-Hong Lim , Nir Shavit, Scalable concurrent counting, ACM Transactions on Computer Systems (TOCS), v.13 n.4, p.343-364, Nov. 1995
	Maged M. Michael , Michael L. Scott, Simple, fast, and practical non-blocking and blocking concurrent queue algorithms, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.267-275, May 23-26, 1996, Philadelphia, Pennsylvania, 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
	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
	Haifeng Yu , Amin Vahdat, Design and evaluation of a conit-based continuous consistency model for replicated services, ACM Transactions on Computer Systems (TOCS), v.20 n.3, p.239-282, August 2002
	Yehuda Afek , Michael Merritt , Gadi Taubenfeld, The power of multi-objects (extended abstract), Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.213-222, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	A. J. Wellings , B. Johnson , B. Sanden , J. Kienzle , T. Wolf , S. Michell, Integrating object-oriented programming and protected objects in Ada 95, ACM SIGAda Ada Letters, v.XXII n.2, p.11-44, June 2002
	Panagiota Fatourou , Faith Fich , Eric Ruppert, A tight time lower bound for space-optimal implementations of multi-writer snapshots, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Hagit Attiya , Jennifer L. Welch, Sequential consistency versus linearizability (extended abstract), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.304-315, July 21-24, 1991, Hilton Head, South Carolina, United States
	Tushar Deepak Chandra, Polylog randomized wait-free consensus, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.166-175, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Maged M. Michael, High performance dynamic lock-free hash tables and list-based sets, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Mark Moir, Laziness pays! using lazy synchronization mechanisms to improve non-blocking constructions, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.61-70, July 16-19, 2000, Portland, Oregon, United States
	François Pacull , Alain Sandoz , André Schiper, Duplex: a distributed collaborative editing environment in large scale, Proceedings of the 1994 ACM conference on Computer supported cooperative work, p.165-173, October 22-26, 1994, Chapel Hill, North Carolina, United States
	Udo Fritzke, Jr. , Philippe Ingels , Achour Mostefaoui , Michel Raynal, Consensus-based fault-tolerant total order multicast, IEEE Transactions on Parallel and Distributed Systems, v.12 n.2, p.146-156, February 2001
	Nancy Lynch , Nir Shavit , Alex Shvartsman , Dan Touitou, Counting networks are practically linearizable, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.280-289, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Michael Greenwald, Two-handed emulation: how to build non-blocking implementations of complex data-structures using DCAS, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Gilbert Caplain, Correctness properties in a shared-memory parallel language, Journal of the ACM (JACM), v.49 n.6, p.785-827, November 2002
	Romain Boichat , Partha Dutta , Svend Frølund , Rachid Guerraoui, Deconstructing paxos, ACM SIGACT News, v.34 n.1, March 2003
	David R. Cheriton , Dale Skeen, Understanding the limitations of causally and totally ordered communication, ACM SIGOPS Operating Systems Review, v.27 n.5, p.44-57, Dec. 1993
	Amos Israeli , Lihu Rappoport, Disjoint-access-parallel implementations of strong shared memory primitives, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.151-160, August 14-17, 1994, Los Angeles, California, United States
	Francisco J. Torres-Rojas , Mustaque Ahamad , Michel Raynal, Timed consistency for shared distributed objects, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.163-172, May 04-06, 1999, Atlanta, Georgia, United States
	H. Rebecca Callison, A periodic object model for real-time systems, Proceedings of the 16th international conference on Software engineering, p.291-300, May 16-21, 1994, Sorrento, Italy
	Kenneth P. Birman, Maintaining consistency in distributed systems, Proceedings of the 5th workshop on ACM SIGOPS European workshop: Models and paradigms for distributed systems structuring, September 21-23, 1992, Mont Saint-Michel, France
	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
	Hagit Attiya , Soma Chaudhuri , Roy Friedman , Jennifer L. Welch, Shared memory consistency conditions for non-sequential execution: definitions and programming strategies, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.241-250, June 30-July 02, 1993, Velen, Germany
	A. J. Wellings , B. Johnson , B. Sanden , J. Kienzle , T. Wolf , S. Michell, Integrating object-oriented programming and protected objects in Ada 95, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.3, p.506-539, May 2000
	Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, The combined power of conditions and failure detectors to solve asynchronous set agreement, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Hagit Brit , Shlomo Moran , Gadi Taubenfeld, Public data structures: counters as a special case, Theoretical Computer Science, v.289 n.1, p.401-423, 23 October 2002
	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
	Seth Gilbert , Nancy Lynch, Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services, ACM SIGACT News, v.33 n.2, June 2002
	Ole Agesen , David L. Detlefs , Christine H. Flood , Alexander T. Garthwaite , Paul A. Martin , Nir N. Shavit , Guy L. Steele, Jr., DCAS-based concurrent deques, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.137-146, July 09-13, 2000, Bar Harbor, Maine, United States
	Michel Raynal, Sequential consistency as lazy linearizability, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Roberto Baldoni , Carlo Marchetti, Three-tier replication for FT-CORBA infrastructures, Software—Practice & Experience, v.33 n.8, p.767-797, 10 July 2003
	Panagiota Fatourou , Faith Fich , Eric Ruppert, Space-optimal multi-writer snapshot objects are slow, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Cormac Flanagan , Shaz Qadeer, A type and effect system for atomicity, ACM SIGPLAN Notices, v.38 n.5, May 2003
	Brad Lushman , Gordon V. Cormack, Proof of correctness of Ressel's adOPTed algorithm, Information Processing Letters, v.86 n.6, p.303-310, 30 June 2003
	John Tromp , Paul Vitányi, Randomized two-process wait-free test-and-set, Distributed Computing, v.15 n.3, p.127-135, July 2002
	Liqiang Wang , Scott D. Stoller, Accurate and efficient runtime detection of atomicity errors in concurrent programs, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA
	Mihai Surdeanu , Dan Moldovan, Design and Performance Analysis of a Distributed Java Virtual Machine, IEEE Transactions on Parallel and Distributed Systems, v.13 n.6, p.611-627, June 2002
	Frank Stomp , Gadi Taubenfeld, Constructing a Reliable Test&Set Bit, IEEE Transactions on Parallel and Distributed Systems, v.10 n.3, p.252-265, March 1999
	Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, Conditions on input vectors for consensus solvability in asynchronous distributed systems, Journal of the ACM (JACM), v.50 n.6, p.922-954, November 2003
	Ori Shalev , Nir Shavit, Split-ordered lists: lock-free extensible hash tables, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.102-111, July 13-16, 2003, Boston, Massachusetts
	Cormac Flanagan , Stephen N Freund, Atomizer: a dynamic atomicity checker for multithreaded programs, ACM SIGPLAN Notices, v.39 n.1, p.256-267, January 2004
	Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September 2003
	Marcos K. Aguilera, A pleasant stroll through the land of infinitely many creatures, ACM SIGACT News, v.35 n.2, June 2004
	Danny Hendler , Nir Shavit , Lena Yerushalmi, A scalable lock-free stack algorithm, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Manhoi Choy , Hong V. Leong , Man Hon Wong, On distributed object checkpointing and recovery, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.64-73, August 20-23, 1995, Ottowa, Ontario, 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
	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
	Maurice Herlihy, On beyond registers: wait-free readable objects, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.26-42, August 2001, Newport, Rhode Island, United States
	Martha J. Kosa, Making operations of concurrent data types fast, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.32-41, August 14-17, 1994, Los Angeles, California, United States
	Hagit Attiya , Eyal Dagan, Universal operations: unary versus binary, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.223-232, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Faith Fich , Maurice Herlihy , Nir Shavit, On the space complexity of randomized synchronization, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.241-249, August 15-18, 1993, Ithaca, New York, United States
	Maurice Herlihy , Victor Luchangco , Mark Moir , William N. Scherer, III, Software transactional memory for dynamic-sized data structures, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.92-101, July 13-16, 2003, Boston, Massachusetts
	Prasad Jayanti, Robust wait-free hierarchies, Journal of the ACM (JACM), v.44 n.4, p.592-614, July 1997
	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
	Yehuda Afek , Hagit Attiya , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Journal of the ACM (JACM), v.40 n.4, p.873-890, Sept. 1993
	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
	Theodore Johnson , Padmashree Krishna, Lazy updates for distributed search structure, ACM SIGMOD Record, v.22 n.2, p.337-346, June 1, 1993
	Victor Luchangco , Mark Moir , Nir Shavit, Nonblocking k-compare-single-swap, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Alberto Bartoli, Implementing a replicated service with group communication, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.8, p.493-519, August 2004
	Mustaque Ahamad , Rammohan Kordale, Scalable Consistency Protocols for Distributed Services, IEEE Transactions on Parallel and Distributed Systems, v.10 n.9, p.888-903, September 1999
	Vicent Cholvi , Josep Bernabéu, Relationships between memory models, Information Processing Letters, v.90 n.2, p.53-58, 30 April 2004
	Jalal Kawash, Consistency models for Internet caching, Proceedings of the winter international synposium on Information and communication technologies, January 05-08, 2004, Cancun, Mexico
	Simon Doherty , David L. Detlefs , Lindsay Grove , Christine H. Flood , Victor Luchangco , Paul A. Martin , Mark Moir , Nir Shavit , Guy L. Steele, Jr., DCAS is not a silver bullet for nonblocking algorithm design, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Cormac Flanagan , Stephen N. Freund , Shaz Qadeer, Exploiting purity for atomicity, ACM SIGSOFT Software Engineering Notes, v.29 n.4, July 2004
	Wim H. Hesselink, Progress under bounded fairness, Distributed Computing, v.12 n.4, p.197-207, September 1999
	Rachid Guerraoui , André Schiper, Software-Based Replication for Fault Tolerance, Computer, v.30 n.4, p.68-74, April 1997
	Matei David, Brief announcement: a single enqueuer wait-free queue implementation, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Robert C. Steinke , Gary J. Nutt, A unified theory of shared memory consistency, Journal of the ACM (JACM), v.51 n.5, p.800-849, September 2004
	Hans-J. Boehm, An almost non-blocking stack, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Partha Dutta , Rachid Guerraoui , Ron R. Levy , Arindam Chakraborty, How fast can a distributed atomic read be?, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Mikhail Fomitchev , Eric Ruppert, Lock-free linked lists and skip lists, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Woei-Jiunn Tsaur , Shi-Jinn Horng, Auditing Causal Relationships of Group Multicast Communications in Group-Oriented Distributed Systems, The Journal of Supercomputing, v.18 n.1, p.25-45, Jan. 2001
	James H. Anderson , Mark Moir, Universal Constructions for Large Objects, IEEE Transactions on Parallel and Distributed Systems, v.10 n.12, p.1317-1332, December 1999
	Yasushi Saito , Svend Frølund , Alistair Veitch , Arif Merchant , Susan Spence, FAB: building distributed enterprise disk arrays from commodity components, ACM SIGARCH Computer Architecture News, v.32 n.5, December 2004
	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
	Håkan Sundell , Philippas Tsigas, Fast and lock-free concurrent priority queues for multi-thread systems, Journal of Parallel and Distributed Computing, v.65 n.5, p.609-627, May 2005
	Simon Doherty , Maurice Herlihy , Victor Luchangco , Mark Moir, Bringing practical lock-free synchronization to 64-bit applications, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Roger Wattenhofer , Peter Widmayer, The counting pyramid: an adaptive distributed counting scheme, Journal of Parallel and Distributed Computing, v.64 n.4, p.449-460, April 2004
	Cormac Flanagan , Stephen N. Freund , Marina Lifshin, Type inference for atomicity, Proceedings of the 2005 ACM SIGPLAN international workshop on Types in languages design and implementation, p.47-58, January 10-10, 2005, Long Beach, California, USA
	Haifeng Yu , Amin Vahdat, Consistent and automatic replica regeneration, ACM Transactions on Storage (TOS), v.1 n.1, p.3-37, February 2005
	Yves Eychenne , Michel Simatic , Christophe Baradel , Bruno Kohen, Exploiting late binding in object messaging for implementing object replication, Proceedings of the 5th workshop on ACM SIGOPS European workshop: Models and paradigms for distributed systems structuring, September 21-23, 1992, Mont Saint-Michel, France
	Sibsankar Haldar, Constructing regular variables in message passing systems, Journal of Parallel and Distributed Computing, v.65 n.1, p.15-28, January 2005
	Dahlia Malkhi , Michael Merritt , Michael K. Reiter , Gadi Taubenfeld, Objects shared by Byzantine processes, Distributed Computing, v.16 n.1, p.37-48, February 2003
	Håkan Sundell , Philippas Tsigas, Scalable and lock-free concurrent dictionaries, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
	Carole Delporte-Gallet , Hugues Fauconnier , Rachid Guerraoui , Vassos Hadzilacos , Petr Kouznetsov , Sam Toueg, The weakest failure detectors to solve certain fundamental problems in distributed computing, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	James H. Anderson, Composite registers, Distributed Computing, v.6 n.3, p.141-154, April 1993
	Wim H. Hesselink, Wait-free linearization with an assertional proof, Distributed Computing, v.8 n.2, p.65-80, October 1994
	Virendra J. Marathe , William N. Scherer , Michael L. Scott, Design tradeoffs in modern software transactional memory systems, Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems, p.1-7, October 22-23, 2004, Houston, Texas
	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
	Hagit Attiya , Maurice Herlihy , Ophir Rachman, Atomic snapshots using lattice agreement, Distributed Computing, v.8 n.3, p.121-132, March 1995
	Roy Friedman, Implementing hybrid consistency with high-level synchronization operations, Distributed Computing, v.9 n.3, p.119-129, December 1995
	Panagiota Fatourou , Maurice Herlihy, Read-modify-write networks, Distributed Computing, v.17 n.1, p.33-46, February 2004
	Yasushi Saito , Marc Shapiro, Optimistic replication, ACM Computing Surveys (CSUR), v.37 n.1, p.42-81, March 2005
	Paweł T. Wojciechowski, Isolation-only transactions by typing and versioning, Proceedings of the 7th ACM SIGPLAN international conference on Principles and practice of declarative programming, p.70-81, July 11-13, 2005, Lisbon, Portugal
	Michael A. Bender , Jeremy T. Fineman , Seth Gilbert , Bradley C. Kuszmaul, Concurrent cache-oblivious b-trees, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	William N. Scherer, III , Doug Lea , Michael L. Scott, Scalable synchronous queues, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA
	Viktor Vafeiadis , Maurice Herlihy , Tony Hoare , Marc Shapiro, Proving correctness of highly-concurrent linearisable objects, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA
	Mark Moir , Daniel Nussbaum , Ori Shalev , Nir Shavit, Using elimination to implement scalable and lock-free FIFO queues, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Faith Fich , Danny Hendler , Nir Shavit, On the inherent weakness of conditional synchronization primitives, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Tayfun Elmas , Serdar Tasiran , Shaz Qadeer, VYRD: verifYing concurrent programs by runtime refinement-violation detection, ACM SIGPLAN Notices, v.40 n.6, June 2005
	Liqiang Wang , Scott D. Stoller, Static analysis of atomicity for programs with non-blocking synchronization, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA
	Michel Raynal, Wait-free computing: an introductory lecture, Future Generation Computer Systems, v.21 n.5, p.655-663, May 2005
	Michael Abd-El-Malek , Gregory R. Ganger , Garth R. Goodson , Michael K. Reiter , Jay J. Wylie, Fault-scalable Byzantine fault-tolerant services, ACM SIGOPS Operating Systems Review, v.39 n.5, December 2005
	Cormac Flanagan , Stephen N. Freund , Shaz Qadeer, Exploiting Purity for Atomicity, IEEE Transactions on Software Engineering, v.31 n.4, p.275-291, April 2005
	Rachid Guerraoui , Corine Hari, On the consistency problem in mobile distributed computing, Proceedings of the second ACM international workshop on Principles of mobile computing, October 30-31, 2002, Toulouse, France
	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
	Maurice Herlihy , Nir Shavit , Orli Waarts, Linearizable counting networks, Distributed Computing, v.9 n.4, p.193-203, February 1996
	Ali Sezgin , Ganesh Gopalakrishnan, On the definition of sequential consistency, Information Processing Letters, v.96 n.6, p.193-196, 31 December 2005
	Christopher Cole , Maurice Herlihy, Snapshots and software transactional memory, Science of Computer Programming, v.58 n.3, p.310-324, December 2005
	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
	Wojciech Golab , Danny Hendler , Philipp Woelfel, An O(1) RMRs leader election algorithm, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	H. Gao , J. F. Groote , W. H. Hesselink, Lock-free dynamic hash tables with open addressing, Distributed Computing, v.18 n.1, p.21-42, July 2005
	James H. Anderson, Multi-writer composite registers, Distributed Computing, v.7 n.4, p.175-195, May 1994
	Noga Alon , Michael Merritt , Omer Reingold , Gadi Taubenfeld , Rebecca N. Wright, Tight bounds for shared memory systems accessed by Byzantine processes, Distributed Computing, v.18 n.2, p.99-109, December 2005
	Hyunyoung Lee , Jennifer L. Welch, Randomized registers and iterative algorithms, Distributed Computing, v.17 n.3, p.209-221, March 2005
	Shlomi Dolev , Seth Gilbert , Nancy A. Lynch , Alexander A. Shvartsman , Jennifer L. Welch, GeoQuorums: implementing atomic memory in mobile ad hoc networks, Distributed Computing, v.18 n.2, p.125-155, December 2005
	James Aspnes , Faith Ellen Fich , Eric Ruppert, Relationships between broadcast and shared memory in reliable anonymous distributed systems, Distributed Computing, v.18 n.3, p.209-219, February 2006
	Guy E. Blelloch , Phillip B. Gibbons , S. Harsha Vardhan, Combinable memory-block transactions, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Hagit Attiya , Danny Hendler , Philipp Woelfel, Tight RMR lower bounds for mutual exclusion and other problems, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Rachid Guerraoui , Marko VukoliĆ, Refined quorum systems, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Lindsay Groves, Verifying Michael and Scott's lock-free queue algorithm using trace reduction, Proceedings of the fourteenth symposium on Computing: the Australasian theory, January 01-01, 2008, Wollongong, NSW, Australia
	Panagiota Fatourou , Faith Ellen Fich , Eric Ruppert, Time-space tradeoffs for implementations of snapshots, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Ori Shalev , Nir Shavit, Split-ordered lists: Lock-free extensible hash tables, Journal of the ACM (JACM), v.53 n.3, p.379-405, May 2006
	Patrick Eugster, Uniform proxies for Java, ACM SIGPLAN Notices, v.41 n.10, October 2006
	Yi Zhang , Ling Chen , Gencai Chen, Globally synchronized dead-reckoning with local lag for continuous distributed multiplayer games, Proceedings of 5th ACM SIGCOMM workshop on Network and system support for games, October 30-31, 2006, Singapore
	Costas Busch , Marios Mavronicolas , Paul Spirakis, The cost of concurrent, low-contention Read&Modify&Write, Theoretical Computer Science, v.333 n.3, p.373-400, 3 March 2005
	Tim Harris , Mark Plesko , Avraham Shinnar , David Tarditi, Optimizing memory transactions, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Alexander Thomasian, Multi-level RAID for very large disk arrays, ACM SIGMETRICS Performance Evaluation Review, v.33 n.4, March 2006
	Panagiota Fatourou , Nikolaos D. Kallimanis, Single-scanner multi-writer snapshot implementations are fast!, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Yehuda Afek , Eli Gafni , Adam Morrison, Common2 extended to stacks and unbounded concurrency, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Ori Shalev , Nir Shavit, Predictive log-synchronization, ACM SIGOPS Operating Systems Review, v.40 n.4, October 2006
	Keir Fraser , Tim Harris, Concurrent programming without locks, ACM Transactions on Computer Systems (TOCS), v.25 n.2, p.5-es, May 2007
	Matthew Parkinson , Richard Bornat , Peter O'Hearn, Modular verification of a non-blocking stack, ACM SIGPLAN Notices, v.42 n.1, January 2007
	Jinyuan Li , Maxwell Krohn , David Mazières , Dennis Shasha, Secure untrusted data repository (SUNDR), Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.9-9, December 06-08, 2004, San Francisco, CA
	Svend Frølund , Arif Merchant , Yasushi Saito , Susan Spence , Alistair Veitch, FAB: enterprise storage systems on a shoestring, Proceedings of the 9th conference on Hot Topics in Operating Systems, p.29-29, May 18-21, 2003, Lihue, Hawaii
	Michael Abd-El-Malek , William V. Courtright, II , Chuck Cranor , Gregory R. Ganger , James Hendricks , Andrew J. Klosterman , Michael Mesnier , Manish Prasad , Brandon Salmon , Raja R. Sambasivan , Shafeeq Sinnamohideen , John D. Strunk , Eno Thereska , Matthew Wachs , Jay J. Wylie, Ursa minor: versatile cluster-based storage, Proceedings of the 4th conference on USENIX Conference on File and Storage Technologies, p.5-5, December 13-16, 2005, San Francisco, CA
	Haifeng Yu , Amin Vahdat, Consistent and automatic replica regeneration, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.24-24, March 29-31, 2004, San Francisco, California
	Lisa Higham , Lillanne Jackson , Jalal Kawash, Specifying memory consistency of write buffer multiprocessors, ACM Transactions on Computer Systems (TOCS), v.25 n.1, p.1-es, February 2007
	Anders Gidenstam , Marina Papatriantafilou, LFTHREADS: a lock-free thread library, ACM SIGARCH Computer Architecture News, v.36 n.5, December 2008
	James Hendricks , Gregory R. Ganger , Michael K. Reiter, Low-overhead byzantine fault-tolerant storage, ACM SIGOPS Operating Systems Review, v.41 n.6, December 2007
	Lindsay Groves , Robert Colvin, Derivation of a Scalable Lock-Free Stack Algorithm, Electronic Notes in Theoretical Computer Science (ENTCS), 187, p.55-74, July, 2007
	Yossi Lev , Jan-Willem Maessen, Split hardware transactions: true nesting of transactions using best-effort hardware transactional memory, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA
	Vincent Gramoli , Emmanuelle Anceaume , Antonino Virgillito, SQUARE: scalable quorum-based atomic memory with local reconfiguration, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea
	Phuong Hoai Ha , Marina Papatriantafilou , Philippas Tsigas, Self-tuning reactive diffracting trees, Journal of Parallel and Distributed Computing, v.67 n.6, p.674-694, June, 2007
	Michel Raynal , Gadi Taubenfeld, The notion of a timed register and its application to indulgent synchronization, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Ramakrishna Kotla , Lorenzo Alvisi , Mike Dahlin , Allen Clement , Edmund Wong, Zyzzyva: speculative byzantine fault tolerance, ACM SIGOPS Operating Systems Review, v.41 n.6, December 2007
	Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, Conditions on input vectors for consensus solvability in asynchronous distributed systems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.153-162, July 2001, Hersonissos, Greece
	John Maccormick , Chandramohan A. Thekkath , Marcus Jager , Kristof Roomp , Lidong Zhou , Ryan Peterson, Niobe: A practical replication protocol, ACM Transactions on Storage (TOS), v.3 n.4, p.1-43, February 2008
	Sibsankar Haldar , K. Vidyasankar, On specification of Read/Write shared variables, Journal of the ACM (JACM), v.54 n.6, p.31-es, December 2007
	M. Rasit Eskicioglu, A comprehensive bibliography of distributed shared memory, ACM SIGOPS Operating Systems Review, v.30 n.1, p.71-96, Jan. 1996
	Peter F. Corbett , Sandra Johnson Baylor , Dror G. Feitelson, Overview of the Vesta parallel file system, ACM SIGARCH Computer Architecture News, v.21 n.5, p.7-14, Dec. 1993
	Dave Dice , Nir Shavit, Understanding Tradeoffs in Software Transactional Memory, Proceedings of the International Symposium on Code Generation and Optimization, p.21-33, March 11-14, 2007
	John Giacomoni , Tipp Moseley , Manish Vachharajani, FastForward for efficient pipeline parallelism: a cache-optimized concurrent lock-free queue, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA
	Håkan Sundell , Philippas Tsigas, Lock-free deques and doubly linked lists, Journal of Parallel and Distributed Computing, v.68 n.7, p.1008-1020, July, 2008
	Rachid Guerraoui , Petr Kuznetsov, The gap in circumventing the impossibility of consensus, Journal of Computer and System Sciences, v.74 n.5, p.823-830, August, 2008
	Carlo Marchetti , Roberto Baldoni , Sara Tucci-Piergiovanni , Antonino Virgillito, Fully Distributed Three-Tier Active Software Replication, IEEE Transactions on Parallel and Distributed Systems, v.17 n.7, p.633-645, July 2006
	Udo Fritzke , Philippe Ingels , Achour Mostefaoui , Michel Raynal, Consensus-Based Fault-Tolerant Total Order Multicast, IEEE Transactions on Parallel and Distributed Systems, v.12 n.2, p.147-156, February 2001
	Lisa Higham , Jalal Kawash, Tight Bounds for Critical Sections in Processor Consistent Platforms, IEEE Transactions on Parallel and Distributed Systems, v.17 n.10, p.1072-1083, October 2006
	James Aspnes , Keren Censor, Approximate shared-memory counting despite a strong adversary, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.441-450, January 04-06, 2009, New York, New York
	Rachid Guerraoui , Michal Kapalka, The semantics of progress in lock-based transactional memory, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA
	Martin Vechev , Eran Yahav, Deriving linearizable fine-grained concurrent objects, ACM SIGPLAN Notices, v.43 n.6, June 2008
	Cormac Flanagan , Stephen N. Freund , Marina Lifshin , Shaz Qadeer, Types for atomicity: Static checking and inference for Java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.4, p.1-53, July 2008
	Eric Koskinen , Maurice Herlihy, Dreadlocks: efficient deadlock detection, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Christian Cachin , Abhi Shelat , Alexander Shraer, Efficient fork-linearizable access to untrusted shared memory, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Hagit Attiya, Needed: foundations for transactional memory, ACM SIGACT News, v.39 n.1, March 2008
	Rachid Guerraoui , Maurice Herlihy , Petr Kouznetsov , Nancy Lynch , Calvin Newport, On the weakest failure detector ever, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Alejandro Cornejo , Sergio Rajsbaum , Michel Raynal , Corentin Travers, Failure detectors are schedulers, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Rachid Guerraoui , Michal Kapalka, On the correctness of transactional memory, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA
	Cormac Flanagan , Stephen N. Freund, Atomizer: A dynamic atomicity checker for multithreaded programs, Science of Computer Programming, v.71 n.2, p.89-109, April, 2008
	Hakim Weatherspoon , Hugo Miranda , Konrad Iwanicki , Ali Ghodsi , Yann Busnel, Gossiping over storage systems is practical, ACM SIGOPS Operating Systems Review, v.41 n.5, October 2007
	Byung-Gon Chun , Petros Maniatis , Scott Shenker , John Kubiatowicz, Attested append-only memory: making adversaries stick to their word, ACM SIGOPS Operating Systems Review, v.41 n.6, December 2007
	Lisa Higham , Jalal Kawash, Implementing sequentially consistent programs on processor consistent platforms, Journal of Parallel and Distributed Computing, v.68 n.4, p.488-500, April, 2008
	Maurice Herlihy , Eric Koskinen, Transactional boosting: a methodology for highly-concurrent transactional objects, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA
	Panagiota Fatourou , Nikolaos D. Kallimanis, Time-optimal, space-efficient single-scanner snapshots & multi-scanner snapshots using CAS, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Alysson Neves Bessani , Eduardo Pelison Alchieri , Miguel Correia , Joni Silva Fraga, DepSpace: a byzantine fault-tolerant coordination service, ACM SIGOPS Operating Systems Review, v.42 n.4, May 2008
	Faith Ellen , Yossi Lev , Victor Luchangco , Mark Moir, SNZI: scalable NonZero indicators, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Rachid Guerraoui , Ron R. Levy , Bastian Pochon , Jim Pugh, The collective memory of amnesic processes, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-31, March 2008
	Daniela Tulone, Ensuring strong data guarantees in highly mobile ad hoc networks via quorum systems, Ad Hoc Networks, v.5 n.8, p.1251-1271, November, 2007
	Lidong Zhou , Vijayan Prabhakaran , Venugopalan Ramasubramanian , Roy Levin , Chandramohan A. Thekkath, Graceful degradation via versions: specifications and implementations, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Faith Ellen , Panagiota Fatourou , Eric Ruppert, Time lower bounds for implementations of multi-writer snapshots, Journal of the ACM (JACM), v.54 n.6, p.30-es, December 2007
	Lindsay Groves, Trace-based Derivation of a Lock-Free Queue Algorithm, Electronic Notes in Theoretical Computer Science (ENTCS), 201, p.69-98, March, 2008
	Jinho Ahn, Effective service replication mechanisms exploiting agent mobility, Proceedings of the 7th WSEAS International Conference on Software Engineering, Parallel and Distributed Systems, p.74-79, February 20-22, 2008, Cambridge, UK
	Ramakrishna Kotla , Allen Clement , Edmund Wong , Lorenzo Alvisi , Mike Dahlin, Zyzzyva: speculative Byzantine fault tolerance, Communications of the ACM, v.51 n.11, November 2008
	Rachid Guerraoui , Michal Kapalka, On obstruction-free transactions, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Armando Solar-Lezama , Christopher Grant Jones , Rastislav Bodik, Sketching concurrent data structures, ACM SIGPLAN Notices, v.43 n.6, June 2008
	Roy Friedman , Achour Mostefaoui , Michel Raynal, On the Respective Power of ◊P and ◊S to Solve One-Shot Agreement Problems, IEEE Transactions on Parallel and Distributed Systems, v.18 n.5, p.589-597, May 2007
	Prasad Jayanti , Sam Toueg, Every problem has a weakest failure detector, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Mohssen Abboud , Carole Delporte-Gallet , Hugues Fauconnier, Agreement and consistency without knowing the number of processes, Proceedings of the 8th international conference on New technologies in distributed systems, June 23-27, 2008, Lyon, France
	Christian Cachin , Idit Keidar , Alexander Shraer, Fork sequential consistency is blocking, Information Processing Letters, v.109 n.7, p.360-364, March, 2009
	Vicent Cholvi , Ernesto Jiménez , Antonio Fernández Anta, Interconnection of distributed memory models, Journal of Parallel and Distributed Computing, v.69 n.3, p.295-306, March, 2009
	Hany E. Ramadan , Indrajit Roy , Maurice Herlihy , Emmett Witchel, Committing conflicting transactions in an STM, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
	Robert Colvin , Brijesh Dongol, A general technique for proving lock-freedom, Science of Computer Programming, v.74 n.3, p.143-165, January, 2009
	Thomas Ridge, Verifying distributed systems: the operational approach, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA
	Hany E. Ramadan , Christopher J. Rossbach , Emmett Witchel, Dependence-aware transactional memory for increased concurrency, Proceedings of the 2008 41st IEEE/ACM International Symposium on Microarchitecture, p.246-257, November 08-12, 2008
	Eli Gafni , Achour Mostéfaoui , Michel Raynal , Corentin Travers, From adaptive renaming to set agreement, Theoretical Computer Science, v.410 n.14, p.1328-1335, March, 2009
	Lorenz Froihofer , Karl M. Goeschka , Johannes Osrael, Middleware support for adaptive dependability, Proceedings of the ACM/IFIP/USENIX 2007 International Conference on Middleware, November 26-30, 2007, Newport Beach, California
	Atul Singh , Pedro Fonseca , Petr Kuznetsov , Rodrigo Rodrigues , Petros Maniatis, Defining weakly consistent Byzantine fault-tolerant services, Proceedings of the 2nd Workshop on Large-Scale Distributed Systems and Middleware, September 15-17, 2008, Yorktown Heights, New York
	William N. Scherer, III , Doug Lea , Michael L. Scott, Scalable synchronous queues, Communications of the ACM, v.52 n.5, May 2009
	Marco Serafini , Neeraj Suri, Reducing the costs of large-scale BFT replication, Proceedings of the 2nd Workshop on Large-Scale Distributed Systems and Middleware, September 15-17, 2008, Yorktown Heights, New York
	Archana Kale , Ujwala Bharambe, Highly available fault tolerant distributed computing using reflection and replication, Proceedings of the International Conference on Advances in Computing, Communication and Control, January 23-24, 2009, Mumbai, India
	Atul Singh , Pedro Fonseca , Petr Kuznetsov , Rodrigo Rodrigues , Petros Maniatis, Zeno: eventually consistent Byzantine-fault tolerance, Proceedings of the 6th USENIX symposium on Networked systems design and implementation, p.169-184, April 22-24, 2009, Boston, Massachusetts
	Liqiang Wang , Scott D. Stoller, Runtime Analysis of Atomicity for Multithreaded Programs, IEEE Transactions on Software Engineering, v.32 n.2, p.93-110, February 2006
	Christian Cachin , Idit Keidar , Alexander Shraer, Trusting the cloud, ACM SIGACT News, v.40 n.2, June 2009
	Alexandru Nicolau , Guangqiang Li , Alexander V. Veidenbaum , Arun Kejariwal, Synchronization optimizations for efficient execution on multi-cores, Proceedings of the 23rd international conference on Supercomputing, June 08-12, 2009, Yorktown Heights, NY, USA
	Marcos Kawazoe Aguilera , Idit Keidar , Dahlia Malkhi , Alexander Shraer, Dynamic atomic storage without consensus, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Marcos K. Aguilera , Ram Swaminathan, Remote storage with byzantine servers, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada
	Hagit Attiya , Eshcar Hillel , Alessia Milani, Inherent limitations on disjoint-access parallel implementations of transactional memory, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada
	Danny Hendler , Philipp Woelfel, Randomized mutual exclusion in O(log N / log log N) RMRs, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Patric Kabus , Alejandro P. Buchmann, Design of a cheat-resistant P2P online gaming system, Proceedings of the 2nd international conference on Digital interactive media in entertainment and arts, September 19-21, 2007, Perth, Australia
	Hagit Attiya , Rachid Guerraoui , Danny Hendler , Petr Kuznetsov, The complexity of obstruction-free implementations, Journal of the ACM (JACM), v.56 n.4, p.1-33, June 2009

INDEX TERMS

Primary Classification:
D. Software
D.2 SOFTWARE ENGINEERING
D.2.4 Software/Program Verification
Subjects: Correctness proofs

Additional Classification:
D. Software
D.1 PROGRAMMING TECHNIQUES
D.2 SOFTWARE ENGINEERING

F. Theory of Computation
F.1 COMPUTATION BY ABSTRACT DEVICES
F.3 LOGICS AND MEANINGS OF PROGRAMS
F.3.1 Specifying and Verifying and Reasoning about Programs
Subjects: Pre- and post-conditions; Specification techniques

General Terms:
Design, Theory, Verification

REVIEW

"Jan Hendrik Jongejan : Reviewer"

Linearizability is a new concept that can be applied when correctness proofs are needed for operations on data objects that are shared by concurrent processes. Operations on data objects take place sometime between a corresponding invocation a more...

Collaborative Colleagues:

Maurice P. Herlihy: colleagues

Jeannette M. Wing: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player