Sequential consistency versus linearizability (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Sequential consistency versus linearizability (extended abstract)

Full text

Pdf (1.09 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the third annual ACM symposium on Parallel algorithms and architectures table of contents

Hilton Head, South Carolina, United States

Pages: 304 - 315

Year of Publication: 1991

ISBN:0-89791-438-4

Authors

Hagit Attiya	Department of Computer Science, The Technion, Haifa 32000, Israel
Jennifer L. Welch	Department of Computer Science, University of North Carolina, Chapel Hill, NC

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 13, Citation Count: 8

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/113379.113407 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	Sarita V. Adve , Mark D. Hill, Weak ordering—a new definition, Proceedings of the 17th annual international symposium on Computer Architecture, p.2-14, May 28-31, 1990, Seattle, Washington, United States
	2	S. Adve and M. Hill, "Implementing Sequentim Consistency in Cache-Based Systems," Proc. ICPP, 1990.
	3	Y. Afek , G. Brown , M. Merritt, A lazy cache algorithm, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.209-222, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72958]
	4	M. Ahamad, P. Hutto, and R. John, Implementing and Programming Causal Distributed Shared Memory, TR GIT-CC-90-49, Georgia Inst. of Tech., December 1990.
	5	H. Attiya, "Implementing FIFO Queues and Stacks," in preparation.
	6	J. K. Bennett , J. B. Carter , W. Zwaenepoel, Munin: distributed shared memory based on type-specific memory coherence, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.168-176, March 14-16, 1990, Seattle, Washington, United States
	7	Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
	8	R. Bisiani, A. Nowatzyk, and M. Ravishankar, "Coherent Shared Memory on a Distributed Memory Machine," Proc. 1CPP, 1989, pp. 1-133-141.
	9	Kenneth P. Birman , Thomas A. Joseph, Reliable communication in the presence of failures, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.47-76, Feb. 1987 [doi>10.1145/7351.7478]
	10	W. Brantley, K. McAuliffe, and J. Weiss, "RP3 Processor-Memory Element," Proc. 1CPP, 1985, pp. 782-789.
	11	L. M. Censier and P. Feautrier, "A New Solution to Coherence Problems in Multicache Systems," 1EEE Trans. on Computers, vol. C-27, no. 12, pp. 1112-1118.
	12	W. W. Collier, "Architectures for Systems of Parallel Processes," IBM TR 00.3253, Poughkeepsie, NY, January 1984.
	13	E. W. Dijkstra, "Hierarchical Ordering Of Sequential Processes," Acta ln}ormatica, 1971, pp. 115- 138.
	14	Michel Dubois , Christoph Scheurich, Memory Access Dependencies in Shared-Memory Multiprocessors, IEEE Transactions on Software Engineering, v.16 n.6, p.660-673, June 1990 [doi>10.1109/32.55094]
	15	M. Dubois , C. Scheurich , F. Briggs, Memory access buffering in multiprocessors, Proceedings of the 13th annual international symposium on Computer architecture, p.434-442, June 02-05, 1986, Tokyo, Japan
	16	Michel, Dubois , Christoph Scheurich , Fayé A. Briggs, Synchronization, Coherence, and Event Ordering in Multiprocessors, Computer, v.21 n.2, p.9-21, February 1988 [doi>10.1109/2.15]
	17	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]
	18	Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
	19	P. Hutto and M. Ahamad, Slow Memory: Weakening Consistency to Enhance Concurrency in Distributed Shared Memories, TR GIT-ICS-89/39, Georgia Inst. of Tech., October 1989.
	20	L. Lamport, "How to Make a Multiprocessor Computer that Correctly Executes Multiprocess Programs," IEEE Trans. on Computers, vol. C.-28, no. 9, pp. 690-691.
	21	L. Lamport, "On Interprocess Communication. Parts I and II," Distributed Computing, vo}. 1, no. 2 (1986), pp. 77-101.
	22	Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.321-359, Nov. 1989 [doi>10.1145/75104.75105]
	23	R. Lipton and J. Sandberg, PRAM: A Scalable Shared Memory, TR CS-TR-180-88, Princeton University, September 1988.
	24	J. Lundelius and N. Lynch, "An Upper and Lower Bound for Clock Synchronization," Information and Control, vol. 62, Nos. 2/3, pp. 190-204.
	25	S. Min and J. Baer, "A Timestamp-Based Cache Coherence Scheme," Proc. 1CPP, 1989, pp. 1-23- 32.
	26	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]
	27	Christos Papadimitriou, The theory of database concurrency control, Computer Science Press, Inc., New York, NY, 1986
	28	U. Ramachandran, M. Ahamad, and M. Y. Khalidi, "Coherence of Distributed Shared Memory: Unifying Synchronization and Data Transfer," Proc. ICPP, 1989, pp. II-160-169.
	29	C. Scheurich , M. Dubois, Correct memory operation of cache-based multiprocessors, Proceedings of the 14th annual international symposium on Computer architecture, p.234-243, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30377]

CITED BY 8

	Soma Chaudhuri , Rainer Gawlick , Nancy Lynch, Designing algorithms for distributed systems with partially synchronized clocks, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.121-132, August 15-18, 1993, Ithaca, New York, United States
	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
	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
	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
	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
	Hagit Attiya , Jennifer L. Welch, Sequential consistency versus linearizability, ACM Transactions on Computer Systems (TOCS), v.12 n.2, p.91-122, May 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
	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