Sequential Consistency

Graduate Depth 68 in the knowledge graph I know this Set as goal
Unlocks 12 downstream topics
consistency ordering formal-semantics

Core Idea

Sequential consistency guarantees that there exists a total order on all operations that respects the program order of each individual process. Unlike linearizability, this total order does not have to correspond to real time—operations can appear to execute in any order as long as each process's sequence is preserved. This weaker model can be more efficient to implement.

Explainer

From your study of consistency models, you know that distributed systems offer different guarantees about the order in which operations appear to execute. Sequential consistency, defined by Leslie Lamport in 1979, occupies an important middle ground: stronger than eventual consistency, weaker than linearizability, and often the best tradeoff between correctness and performance.

The guarantee is best understood through an analogy. Imagine three people — Alice, Bob, and Carol — each writing statements on separate notepads, then handing all three notepads to a judge. The judge must shuffle the statements into a single sequence (a total order) that could explain every observation, with one constraint: the statements from each person's notepad must appear in the same relative order they were written. The judge is free to interleave statements from different people however she likes — she just cannot reorder any individual person's statements. If such an interleaving exists and is consistent with what everyone observed, the execution is sequentially consistent.

What sequential consistency does *not* guarantee is real-time ordering. If Alice finishes writing a value at 3:00 PM and Bob starts reading at 3:01 PM, sequential consistency does not promise Bob sees Alice's write — the total order might place Bob's read before Alice's write, as long as no single process's operations are reordered. This is the key difference from linearizability, which would require Bob to see the write because Alice's operation completed before Bob's began in wall-clock time. The practical consequence is that sequentially consistent systems can batch, buffer, and reorder operations across nodes for better performance, as long as each node's own operations stay in order.

Sequential consistency appears naturally in hardware memory models. Many multiprocessor architectures guarantee something close to sequential consistency for shared memory access (though modern CPUs often relax even this for performance, requiring memory barriers). In distributed databases, sequential consistency means clients always see a progression of states — they never see writes appear and then disappear — but two clients might disagree about the order of concurrent writes from different sources. For applications like social media feeds or collaborative documents where strict real-time ordering is less critical than a coherent narrative, sequential consistency often provides enough correctness at significantly lower latency and higher availability than linearizability.

Practice Questions 5 questions

Prerequisite Chain

Counting to 10Counting to 20Understanding ZeroThe Number ZeroCounting to FiveOne-to-One CorrespondenceCombining Small Groups Within 5Addition Within 10Addition Within 20Two-Digit Addition Without RegroupingTwo-Digit Addition with RegroupingAddition Within 100Repeated Addition as MultiplicationMultiplication Facts Within 100Division as Equal SharingDivision as Grouping (Measurement Division)Division: Grouping (Repeated Subtraction) ModelDivision: Fair Sharing ModelDivision as Equal SharingDivision as GroupingBasic Division FactsDivision Facts Within 100Two-Digit by One-Digit DivisionDivision with RemaindersRemainders and Quotients in DivisionDivision Word ProblemsIntroduction to Long DivisionFactors and MultiplesPrime and Composite NumbersEquivalent FractionsRelating Fractions and DecimalsDecimal Place ValueReading and Writing DecimalsComparing and Ordering DecimalsAdding and Subtracting DecimalsMultiplying DecimalsDividing DecimalsDividing FractionsMixed Number ArithmeticOrder of OperationsOperators and ExpressionsArithmetic Operators and Operator PrecedenceComparison Operators and Boolean TestsLogical Operators and Boolean AlgebraBoolean Algebra and Fundamental LawsCombinational Circuit DesignFlip-Flops and LatchesBinary Counters: Design and AnalysisBinary ArithmeticFixed-Point Number RepresentationTwo's Complement RepresentationOverflow and Underflow DetectionBinary Adders: Half-Adders and Full-AddersFull Adder and Carry PropagationCarry Lookahead Adder DesignHalf Adder Circuit DesignMultiplication Circuit DesignSequential Circuit DesignRegisters and Register FilesInstruction Set Architecture (ISA)Kernel Architecture and OS StructureSystem Calls and User/Kernel ModeProcesses and the Process Control BlockLogical Clocks and Event OrderingVector Clocks and Capturing CausalityHappened-Before Relation and Causal OrderingConsistency Models in Distributed SystemsRead-After-Write ConsistencySequential Consistency

Longest path: 69 steps · 253 total prerequisite topics

Prerequisites (3)

Leads To (2)