Hagit Attiya
Jennifer L. Welch
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.
- 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.Google Scholar
- ADVE, S., ANn HILL, M. 1990b. Weak ordering--A new definition. In Proceedings of the 17th International Symposium on Computer Architecture (Seattle, Wash., May 21-31). IEEE, Los Angeles, pp. 2-14. Google Scholar
- AFEK, Y., BROWN, G., AND MERRITT, M. 1993. Lazy caching. ACM Trans. Program. Lang. Syst. 15, i (Jan.), 182 205. Google Scholar
- 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.Google Scholar
- ARCHIBALD, J., AND BAER, J.-L. 1986. Cache coherence protocols: Evaluation using a multiprocessor simulation model, ACM Trans. Comput. Syst. 4, 4 (Nov.), 273-298. Google Scholar
- ATT~YA, H. 1991. Implementing FIFO queues and stacks. In Proceedings of the 5th Internatwnal Workshop on Distributed Algorithms. Lecture Notes in Computer Science, vol. 579, Springer-Verlag, New York, pp. 80 94. (Also, Tech. Rep. 672, Dept. of Computer Science, The Technion, Haifa, May). Google Scholar
- ATTIYA, H., ANn FRIEDMAN, R. 1992. A consistency condition for high-performance multiprocessors. In Proceedings of the 24th ACM Symposium on Theory of Computing (Victoria, B.C., May 4-6). ACM, New York, pp. 679-690. (Also, Tech. Rep. 719, Dept. of Computer Science, The Technion, Haifa, June 1992). Google Scholar
- ATTIYA, H., AND WELCH, J.L. 1991. Sequential consistency versus linearizability. In Proceedings of the 3rd ACM Symposium on Parallel Algorithms and Architectures (Hilton Head, S.C., July 21-24). ACM, New York, pp. 304-315. Google Scholar
- ATTIYA, H., CHAUDHURI, S., FRIEDMAN, R., AND WELCH, J.L. 1993. Non-sequential consistency conditions for shared memory. In Proceedings of the 5th ACM Symposium on Parallel Algorithms and Architectures (Velen, Germany, June 30-July 2). ACM, New York, pp. 241-250. Google Scholar
- BENNETT, J., CARTER, J., AND ZWAENEPOEL, W. 1990. Munin: Distributed shared memory based on type-specific memory coherence. In Proceedings of the 2nd ACM Symposium on Principles and Practice of Parallel Processing (Seattle, Wash., Mar. 14-16). ACM, New York, pp. 168 176. Google Scholar
- BERNSTEIN, P., HADZILACOS, V., AND GOODMAN, H. 1987. Concurrency Control and Recovery in Database Systems. Addison-Wesley, Reading, Mass. Google Scholar
- BIRMAN, K., AND JOSEPH, T. 1987. Reliable communication in the presence of failures. ACM Trans. Comput. Syst. 5, i (Feb.), 47-76. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- CHANG, J., AND MAXEMCHUK, N.F. 1984. Reliable broadcast protocols. ACM Trans. Comput. Syst. 2, 3 (Aug.), 251-273. Google Scholar
- COLLIER, W. W. 1984. Architectures for systems of parallel processes. Tech. Rep. 00.3253, IBM, Poughkeepsie, N.Y., Jan.Google Scholar
- DUBOIS, M., AND SCHEURICH, C. 1990. Memory access dependencies in shared-memory multiprocessors. IEEE Trans. Softw. Eng. 16, 6 (June), 660 673. Google Scholar
- DUBOIS, M., SCHEURICH, C., AND BRIGGS, F.A. 1986a. Memory access buffering in multiprocessors. In Proceedings of the 13th International Symposium on Computer Architecture (June), pp. 434 442. Google Scholar
- DUBOIS, M., SCHEURICH, C., AND BRIGGS, r.A. 1956b. Synchronization, coherence and event ordering in multiprocessors. Computer 21, 2 (June), 9-21. Google Scholar
- FRIEDMAN, R. 1993. Implementing hybrid consistency with highdevel synchronization operations, Proceedings of the 12th ACM Symposium on Principles of D~strzbuted Computing (Ithaca, N.Y., Aug. 15 18). ACM, New York. pp. 229-240. Google Scholar
- 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.Google Scholar
- GHARACHORLOO, K., LENOSKI, D., LAUDON, J., GIBBONS, P., GUPTA, A., AND HENNESSEY, J. 1990. Memory consistency and event ordering in scalable shared-memory multiprocessors In Proceedings of the 17th International Symposium on Computer Architecture (Seattle, Wash., May 28-31). IEEE, Los Angeles, pp. 15 26. Google Scholar
- GIBBONS, P., MERRITT, M., AND GHARACHORLOO, K. 1991 Proving sequential consistency of high-performance shared memories. In Proceedings of the 3rd ACM Symposium on Parallel Algorzthms and Architectures (Hilton Head, S.C., July 21 24). ACM, New York, pp. 292-303. Google Scholar
- 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.Google Scholar
- HENNESSY, J., AND PATTERSON, D. 1990. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, San Mateo, Calif. Google Scholar
- HERLIHY, M. 1988. Wait-free implementations of concurrent objects. In Proceedings of the ACM Symposium on Principles of D~str~buted Compuhng (Toronto, Ont., Aug. 15 17). ACM, New York, pp 276-290. Google Scholar
- HERLIHY, M., AND WING, J. 1990. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12, 3 (July), 463 492. Google Scholar
- 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.Google Scholar
- KOSA, M. 1994. Consistency conditions for concurrent shared objects: Upper and lower bounds. Ph.D. dissertation, Dept. of Computer Science, Univ. of North Carolina, Chapel Hill. Feb. Google Scholar
- LAMPORT, L. 1979. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Trans. Comput. C-28, 9 (Sept.), 690-691.Google Scholar
- LAMPORT, L. 1986. On interprocess communication. Parts I and II. Distr~b. Comput. 1, 2, 77 101.Google Scholar
- 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.Google Scholar
- LUNDELIUS, J., AND LYNCH, N. 1984. An upper and lower bound for clock synchronization. Inf. Control 62, 2 3 (Aug/Sept.), 190 204.Google Scholar
- MAVRONICOLAS, M., AND ROTH, D. 1992 Efficient, strong consistent implementations of shared memory. In Proceedings of the 6th International Workshop on Distributed Algorithms. Lecture Notes in Computer Science, vol. 647, Springer-Verlag, New York, pp 346-361 Google Scholar
- 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.Google Scholar
- MISRA, J. 1986. Axioms for memory access in asynchronous hardware systems. ACM Trans. Program. Lang. Syst. 8, 1 (Jan.), 142-153. Google Scholar
- PAPADIMITRIOU, C 1986 The Theory of Concurrency Control. Computer Science Press, Rockville, Md. Google Scholar
- 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.Google Scholar
- SCHEURICH, C., AND DUBOIS, M. 1987. Correct memory operation of cache-based multiprocessors. In Proceedings of the 14th Internatmnal Symposium on Computer Architecture (Pittsburgh, Pa., June 2-5) IEEE, Los Angeles, pp. 234-243. Google Scholar
Index Terms
- Sequential consistency versus linearizability
Recommendations
Linearizability: a correctness condition for concurrent objects
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 ...
Sequential Consistency as Lazy Linearizability
EurAsia-ICT '02: Proceedings of the First EurAsian Conference on Information and Communication TechnologyThis paper shows that actually sequential consistency is a form of "lazy" atomic consistency. More precisely, it proposes a new particularly simple sequential consistency protocol that orders the conflicting operations on each object separately, and ...
Regular Sequential Serializability and Regular Sequential Consistency
SOSP '21: Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems PrinciplesStrictly serializable (linearizable) services appear to execute transactions (operations) sequentially, in an order consistent with real time. This restricts a transaction's (operation's) possible return values and in turn, simplifies application ...
Reviews
David Michael Bowen
Two different conditions for modeling concurrent access to shared data are in common use: sequential consistency and linearizability. The two are quite similar and, at times, have even been confused, but linearizability is a stronger condition than sequential consistency. Until now, there had been no research as to whether the theoretical difference in strength made any difference in practice. This paper answers the question in two different ways, depending on the assumptions about the communication and synchronization between the individual processors. When the processors' clocks are perfectly synchronized, the authors provide algorithms that show that the conditions impose equal costs. When the clocks are unsynchronized, however, the authors show that the extra burden of linearizability imposes a higher cost on the system's performance. The algorithms they give are for concurrent readers and writers, a concurrent queue, and a concurrent stack, but the techniques they use could be applied to other shared data structures. While the paper will be of greatest interest to specialists in concurrent systems, the explanations, both of what the paper proves and of the proofs themselves, are clear enough that people with only a passing interest in the subject could benefit from reading it. The algorithms are an added benefit—since they concretize what could otherwise have been a totally abstract presentation—and provide insight into the proofs.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments