Sequential consistency versus linearizability

ABSTRACT

The power of two well-known consistency conditions for shared-memory multiprocessors, sequential consistency and linearizability, is compared. The cost measure studied is the worst-case response time in distributed implementations of virtual shared memory supporting one of the two conditions. Three types of shared-memory objects are considered: read/write objects, FIFO queues, and stacks. If clocks are only approximately synchronized (or do not exist), then for all three object types it is shown that linearizability is more expensive than sequential consistency. We show that, for all three data types, the worst-case response time is very sensitive to the assumptions that are made about the timing information available to the system. Under the strong assumption that processes have perfectly synchronized clocks, it is shown that sequential consistency and linearizability are equally costly. We present upper bounds for linearizability and matching lower bounds for sequential consistency. The upper bounds are shown by presenting algorithms that use atomic broadcast in a modular fashion. The lower-bound proofs for the approximate case use the technique of “shifting,” first introduced for studying the clock synchronization problem.

REFERENCES

• 1: ADVE, S., AND HILL, M. 1990a. Implementing sequential consistency in cache-based systems. In Proceedings of the International Conference on Parallel Processing. Pennsylvania State University, University Park, pp. 1-47-I-50.
• 2: 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
• 3: Yehuda Afek , Geoffrey Brown , Michael Merritt, Lazy caching, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.1, p.182-205, Jan. 1993 [doi>10.1145/151646.151651]
• 4: AHAMAD, M., Hu~ro, P. AND JOHN, R. 1990. Implementing and programming causal distributed shared memory, Tech. Rep. GIT-CC-90-49, Georgia Inst. of Technology, Atlanta, Dec.
• 5: James Archibald , Jean-Loup Baer, Cache coherence protocols: evaluation using a multiprocessor simulation model, ACM Transactions on Computer Systems (TOCS), v.4 n.4, p.273-298, Nov. 1986 [doi>10.1145/6513.6514]
• 6: Hagit Attiya, Implementing FIFO Queus and Stacks (Extended Abstract), Proceedings of the 5th International Workshop on Distributed Algorithms, p.80-94, October 07-09, 1991
• 7: 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 [doi>10.1145/129712.129778]
• 8: 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 [doi>10.1145/113379.113407]
• 9: 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 [doi>10.1145/165231.165263]
• 10: 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
• 11: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 12: 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]
• 13: BISIANI, R., NOWATZYK, A., AND RAVISHANKAR, M. 1989. Coherent shared memory on a distributed memory machine. In Proceedings of the International Conference on Parallel Processing. Pennsylvania State University, University Park, pp. 1-133-I-141.
• 14: BRANTLEY, W., McAULIFFE, K., AND WEISS, J. 1985. RP3 processor-memory element. In Proceedings of the International Conference on Parallel Processing (Aug. 20-23). Pennsylvania State University, University Park, pp. 782 789.
• 15: CENSIER, L. M., AND FEAUTRIER, P. 1978. A new solution to coherence problems in multicache systems. IEEE Trans. Comput. C~27, 12 (Dec.), 1112 1118.
• 16: Jo-Mei Chang , N. F. Maxemchuk, Reliable broadcast protocols, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.251-273, Aug. 1984 [doi>10.1145/989.357400]
• 17: COLLIER, W. W. 1984. Architectures for systems of parallel processes. Tech. Rep. 00.3253, IBM, Poughkeepsie, N.Y., Jan.
• 18: 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]
• 19: 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
• 20: 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]
• 21: 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 [doi>10.1145/164051.164077]
• 22: GARCIA-MOLINA, H., AND SPAUSTER, A. 1989. Message ordering in a multicast environment. In Proceedings of the Internatmnal Conference on Distributed Computing Systems (Newport Beach, Calif., June 5-9). IEEE, Los Angeles, pp. 354-361.
• 23: Kourosh Gharachorloo , Daniel Lenoski , James Laudon , Phillip Gibbons , Anoop Gupta , John Hennessy, Memory consistency and event ordering in scalable shared-memory multiprocessors, Proceedings of the 17th annual international symposium on Computer Architecture, p.15-26, May 28-31, 1990, Seattle, Washington, United States
• 24: Phillip B. Gibbons , Michael Merritt , Kourosh Gharachorloo, Proving sequential consistency of high-performance shared memories (extended abstract), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.292-303, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113406]
• 25: GOTTLmB, A ~ GRISHMAN, R., KRUSKAL~ C. K., MCAULIFFE, K. P., RUDOLPh, L., AND SNm, M. 1983. The NYU ultracomputer--Designing a MIMD shared-memory parallel computer. IEEE Trans. Comput. C-32 3 (Feb.) 175-189.
• 26: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 27: 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]
• 28: 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]
• 29: HUTTO, r., AND AHAMAD, M. 1989. Slow memory: Weakening consistency to enhance concurrency in distributed shared memories. Tech. Rep. GIT-ICS-89/39, Georgia Inst. of Technology, Atlanta, Oct.
• 30: Martha Jane Kosa, Consistency guarantees for concurrent shared objects: upper and lower bounds, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1995
• 31: LAMPORT, L. 1979. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Trans. Comput. C-28, 9 (Sept.), 690-691.
• 32: LAMPORT, L. 1986. On interprocess communication. Parts I and II. Distr~b. Comput. 1, 2, 77 101.
• 33: LmTON, R., AND SANDBERG, J. 1988. PRAM. A scalable shared memory. Tech. Rep. CS-TR-180- 88, Dept. of Computer Science, Princeton Univ., Princeton, N.J., Sept.
• 34: LUNDELIUS, J., AND LYNCH, N. 1984. An upper and lower bound for clock synchronization. Inf. Control 62, 2 3 (Aug/Sept.), 190 204.
• 35: Marios Mavronicolas , Dan Roth, Efficient, Strongly Consistent Implementations of Shared Memory (Extended Abstract), Proceedings of the 6th International Workshop on Distributed Algorithms, p.346-361, November 02-04, 1992
• 36: MIN, S.. AND BAER, J. 1989 A tlmestamp-based cache coherence scheme. In Proceedings of the International Conference on Parallel Processing Pennsylvania State University, Umversity Park, pp. 1-23-I-32.
• 37: 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]
• 38: Christos Papadimitriou, The theory of database concurrency control, Computer Science Press, Inc., New York, NY, 1986
• 39: RAMACHANDRAN, U., AHAMAD, J., AND K~ALIDI, M.Y. 1989. Coherence of distributed shared memory: Uniiying synchronization and data transfer In Proceedings of the International Conference on Parallel Processing. Pennsylvania State University, University Park, pp. II-160-II-169.
• 40: 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]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Distributed memories

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases; Concurrency

General Terms:
Algorithms, Design, Performance