Comparisons and explanations · Intermediate

Sequential consistency versus linearizability

Compare sequential consistency and linearizability through register histories, per-client order, real-time precedence and compositional reasoning.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Both seek a legal sequential explanation
  2. A later read by another participant
  3. Per-participant order remains a real constraint
  4. Composition is another important distinction
  5. Progress and timing remain separate axes
  6. Turn a short history into a requirement
  7. Ask Logeia about this articleCheck your understanding

Both seek a legal sequential explanation

Sequential consistency asks for one sequential ordering of concurrent operations that preserves each participant’s program order. Linearizability also uses a legal sequential explanation but places an operation within its invocation-response interval and preserves real-time order between nonoverlapping operations. Neither is adequately described as values eventually becoming equal. Check whether returned reads fit the locations of writes in one valid order. The scope here is operations on shared memory or objects; atomic grouping into database transactions is a separate boundary. Name the sequential specification first so that a discussion of stronger ordering does not conceal disagreement about the object’s actual behavior.

A later read by another participant

Start a register at zero. A writes one, receives its response, and only then does B invoke its first read. With no other write, a linearizable register cannot return zero: A’s completion precedes B’s invocation. In a sequential-consistency model with no additional constraints beyond per-participant order, B’s read can sometimes be placed before A’s write. B having no earlier operation is an important premise. A history containing further communication or synchronization can introduce more constraints. The example therefore does not mean that sequential consistency permits every arbitrarily old value in every execution; a single valid order must still explain the complete relevant history.

Per-participant order remains a real constraint

If A performs write(1) and then reads the same register, with no other write, sequential consistency cannot explain zero by moving A’s own read before its write. A’s program order must be preserved. Omitting that rule makes sequential consistency sound like an unconstrained store of arbitrarily stale values, which it is not. For several variables, write down each participant’s operation sequence and the observed read values, then seek a valid global order. The order in a performance trace, the order lines reached a log file, and the order required by the specification are not necessarily interchangeable evidence about that history.

Composition is another important distinction

Linearizability has an important locality property: verifying the property for the appropriate objects supports reasoning about their composition. With sequential consistency, separate valid explanations for individual variables do not necessarily produce one valid order across all variables and participants. A history where A writes x then reads y while B writes y then reads x must respect both per-variable results and participant order together. Conversely, making individual operations linearizable does not turn an application’s separate read-compute-write sequence into one transaction. The useful composition theorem has a precise scope; it is not a promise that arbitrary application invariants become atomic automatically.

Progress and timing remain separate axes

Neither ordering condition directly guarantees that every operation completes within a fixed time. An implementation may require communication or waiting to maintain the chosen result order. Under failures or partitions, specify where operations wait, fail, or use an explicitly weaker read path. Low observed latency does not identify the guarantee, and a strong label does not establish that every implementation must be slow. Measure under the same object specification, operating conditions, and required correctness. The histories in this article illustrate contracts rather than report the speed of any particular implementation. This separation avoids mistaking a weaker response for a faster implementation of the original task.

Turn a short history into a requirement

Record participants, operation IDs, arguments, return values, and invocation-response relationships. Evidence distinguishing overlap from one operation beginning after another completes is especially useful. If clocks across machines cannot simply be compared, identify which communication or observation establishes precedence. A requirement to see one’s own previous write differs from a requirement to see every relevant completed write by others. Replace an ambiguous demand for consistency with small examples of permitted and forbidden reads. Those histories can then be compared with a product contract and the real access path, rather than selecting a consistency label whose scope the application has not actually defined.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Understand the systems behind the web · STEP 17

Choose a learning path