Sequential Consistency versus LinearizabilityFIAGIT ATTIYAThe TechnionandJENNIFER L. WELCHUniversity of North Carolina at Chapel HillThe power of two well-known consistency conditions for shared-memory multiprocessors, sequen-tial consistency and lineariza bility, is compared. The cost measure studied is the worst-caseresponse time in distributed implementations of virtual shared memory supporting one of thetwo conditions. Three types of shared-memory objects are considered: read/write objects, FIFOqueues, and stacks. If clocks are only approximately synchronized (or do not exist), then for allthree object types it is shown that linearizability is more expensive than sequential consistency:We present upper bounds for sequential consistency and larger lower bounds for linearizability.We show that, for all three data types, the worst-case response time is very sensitive to theassumptions that are made about the timing information available to the system. Under thestrong assumption that processes have perfectly synchronized clocks, it is shown that sequentialconsistency and linearizability are equally costly: We present upper bounds for linearizabilityand matching lower bounds for sequential consistency. The upper bounds are shown by present-ing algorithms that use atomic broadcast in a modular fashion. The lower-bound proofs for theapproximate case use the technique of“shifting,” first introduced for studying the clock synchro-nization problem.Categories and Subject Descriptors: B.3.2 [Memory Structures]: Design Styles—cache memo-rzes; shared memory; C. 1.2 [Processor Architectures]: Multiple Data Stream Architectures—This paper combines and unifies results that appear in preliminary form in Attiya and Welch1991 and Attiya 1991. H. Attiya’s research was supported in part by the B. and G. GreenbergResearch Fund (Ottawa), by Technion V.P.R. funds, and by the fund for the promotion ofresearch at the Technion. J. L. Welch’s research was supported in part by NSF grant CCR-9010730, an IBM Faculty Development Award, and an NSF Presidential Young InvestigatorAward. Part of the work by Attiya was performed while visiting the DEC Cambridge ResearchLaboratory and the Laboratory for Computer Science, MIT, supported by ONR contract NOOO14-85-K-0168, by NSF grants CCR-8611442 and CCR-8915206, and by DARPA contracts NOOO14-89-J-1988 and NOO014-87-K-0825.Authors’ addresses: H. Attiya, Department of Computer Science, The Technion, Haifa 32000,Israel; J. L. Welch, Department of Computer Science, Texas A & M University, College Station,TX 77843-3112.This paper was originally submitted to ACM TOPLAS, where it was reviewed and accepted forpublication. It was subsequently transferred to TOCS, with the agreement of the authors, to takeadvantage of the shorter delay to publication for TOCS.Permission to copy without fee all or part of this material is granted provided that the copies arenot made or distributed for direct commercial advantage, the ACM copyright notice and the titleof the publication and its date appear, and notice is given that copying is by permission of theAssociation for Computing Machinery. To copy otherwise, or to republish, requires a fee and/orspecific permission.01994 ACM 0164-0925/94/0500-0091 $03.50ACM Transactions on Computer Systems, Vol 12, No 2, May 1994, Pages 91-122.92 .H, Attiya and J. L. Welchparallel processors; D.3.3 [Programming Techniques]: Language Constructs—abstract datatypes; concurrent programming structures;D.4 2 [Operating Systems]: Storage Man-agement—distnbuted memorzes; F.1.2 [Computation by Abstract Devices]: Modes of Com-putatlon—parallelum and concurrencyGeneral Terms: Algorithms, DesignAdditional Key Words and Phrases: Cache coherence, hnearizabdity, sequential consmtency.shared memory1. INTRODUCTION1.1 OverviewWe present a quantitative comparison of the inherent costs of two well-knownconsistency conditions for concurrently accessed shared data: sequential con-sistency and linearizability. Our main conclusion is that under realistictiming assumptions it is strictly more expensive to provide linearizabilitythan sequential consistency in distributed (message-passing) implementa-tions, where the cost measure is the worst-case time for a data access.Because their definitions are very similar, linearizability and sequentialconsistency are often confused, but our work shows that there can be aconsiderable cost to such confusion. For example, Dubois and Scheurich[1990; Scheurich and Dubois 1987] define a sufficient condition for sequentialconsistency (cf. Dubois and Scheurich [ 1990, clef. 6.3]); however, this conditionimplies linearizability.1 Implementing linearizability imposes more cost thanis necessary to support the target condition of sequential consistency. To ourknowledge, this is the first time sequential consistency is shown to be morecostly than linearizability.We also study the worst-case access time for the two conditions under morestringent timing assumptions, namely, when processes have perfectly syn-chronized clocks. We show several lower bounds for sequential consistency inthis model; these lower bounds carry over to more realistic models in whichweaker assumptions hold about the clock behavior. We also present matching“counterexample” algorithms for linearizability in this model. They demon-strate that no improved lower bounds for either condition are possible with-out weakening the timing assumptions. The fact that sequential consistencyand linearizability are equally costly in this model (for our measure) issomewhat surprising. It indicates the importance of exphcitly and carefullyspecifying system timing assumptions, and the nontriviality of separatingsequential consistency from linearizability.1.2 Detailed DescriptionManaging concurrent accesses to shared data by several processes is aproblem that arises in many contexts, ranging from cache coherence for] Techmcally, the definition of Dubois and Scheurich [1990] rehes on the notion of “performing anoperation,” which can only be interpreted in a specdic architectural model Under a naturalinterpretation (e.g , as m Gibbons et al. 1991), the definition implies linearizabilityACM TransactIons on Computer Systems, Vol 12, No, 2. May 1994Sequential Consistency versus Linearizability . 93multiprocessors to distributed file systems and transaction systems. A consis-tency condition must specify what guarantees are provided about the valuesreturned by data accesses in