Linearizability is the usual correctness bar for concurrent data structures. Define it precisely, explain why "the final state is correct" is not a sufficient standard, and contrast it with sequential consistency.

## The definition, carefully Model an execution as a **history**: a sequence of *invocation* events (the call) and *response* events (the return) for operations on an object, tagged with the thread that issued them. Operations overlap when one's invocation falls between another's invocation and response. A history is **linearizable** if it can be extended (by completing or discarding pending operations) and reordered into a *sequential* history — one where every invocation is immediately followed by its response — such that: 1. the sequential history is **legal** for the object's single-threaded specification (a FIFO queue returns items in insertion order, a counter returns the number of increments so far, and so on); and 2. the order **respects real time**: if operation A returned before operation B was invoked, A precedes B in the sequential order. Operations that overlap in time may be ordered either way — that freedom is what makes concurrency possible — but non-overlapping operations may not be reordered. Equivalently and more usably: each operation has a **linearization point**, an instant between its invocation and its response at which it appears to take effect atomically. An object is linearizable if all its histories are. ## Why this is the useful bar Linearizability is a **safety** property (nothing bad happens) and is entirely separate from **liveness/progress** properties like lock-freedom. A mutex-guarded structure is typically linearizable; so is a good lock-free one. The two axes answer different questions: linearizability asks *is the answer right*, progress asks *will I get an answer*. The practical payoff is that linearizability lets you reason about a concurrent object using its **sequential specification**. You can state invariants like "every enqueued item is dequeued exactly once, in order" and rely on them without enumerating interleavings. The second payoff is **composability** (locality). If every object in a system is individually linearizable, the system as a whole is linearizable. This is unusual and extremely valuable: it means correctness can be established one component at a time. Sequential consistency lacks this property, so components proven correct in isolation can compose into something that is not sequentially consistent. ## Why "the final state is correct" fails End-state reasoning is a batch-processing intuition that does not survive contact with concurrency, for three reasons. 1. **Observations happen during execution.** A stack whose pop briefly returns an element that a concurrent pop also returned is broken the moment a caller acts on it, whatever the final state. 2. **There may be no final state.** Long-running servers never quiesce. 3. **Intermediate states leak into the outside world.** A dequeued message is sent, an allocated identifier is written to a database. There is no undo. A telling example: a size operation implemented by summing per-shard counters while items move between shards can return a number that never corresponded to any real state of the structure at any instant — it is not linearizable even if it is eventually consistent with the true count. Whether that is acceptable is a design decision, but it should be a conscious one. ## Sequential consistency and serializability **Sequential consistency** requires that some total order over all operations exists that is legal for the object and consistent with each thread's own program order. Real time is not constrained, so a write may become visible to other threads arbitrarily later than its return, provided the resulting order is coherent. It is a weaker, cheaper condition often used to describe memory models. Its fatal practical weakness is non-composability. **Serializability** comes from databases and concerns **transactions** — groups of operations, possibly across several objects — appearing to execute in some serial order. It says nothing about real time. **Strict serializability** is roughly the transactional analogue of linearizability: serializable plus real-time order. So linearizability is about single objects and single operations; serializability is about multi-operation transactions. ## Establishing and testing it The usual proof technique is to identify each operation's linearization point and argue that ordering by those points always yields a legal sequential history. In compare-and-set-based algorithms the point is typically the successful atomic update; in lock-based code it is somewhere inside the critical section. Some operations have linearization points that depend on the execution — for instance an emptiness check whose point falls at the read that observed the empty state — which is a sign the proof needs care. Empirically, linearizability checkers generate randomised concurrent histories, record invocations and responses with timestamps, and search for a valid sequential ordering; a failure is a concrete counterexample interleaving. This is far more effective than stress tests that only assert on final state, because it checks exactly the property that end-state assertions miss. ## The interview answer Give the instantaneous-effect definition with the real-time constraint, name the linearization point, say why intermediate observations matter, and close with composability as the reason linearizability rather than sequential consistency is the standard for concurrent objects.