# Linearizability > Linearizability makes operations on shared state behave as if they happened one at a time, with each operation taking effect somewhere between its request and response. Once a write succeeds, any later read must see that write or a newer one, not an older value. In system design interviews, it matters when stale state could authorize a second booking, allocate an extra slot, or let an obsolete leader keep making changes. Source: https://sysround.com/concepts/linearizability Updated: 2026-11-05 ## How linearizability works Start with an object's rules: a register supports reads and writes; a seat supports an atomic claim if available. Linearizability requires a single ordering of operations that follows those rules and respects real time: if operation A finishes before B starts, A must appear before B. Overlapping operations can appear in either order, as long as their results fit one valid sequence. If two clients concurrently try to claim the same available seat, an atomic, linearizable claim lets one succeed and makes the other fail. Two separate linearizable operations, read availability, then write ownership, do not make that whole sequence atomic. Each operation has a conceptual linearization point between invocation and response. This is where it appears to take effect, not necessarily a timestamp recorded by the system. Linearizability does not require perfectly synchronized client clocks. A common replicated implementation uses a leader and a consensus protocol to establish an agreed operation order. Writes succeed only after the protocol's commit requirements are met, and replacement leaders must preserve committed state. A single leader without safe replication and failover is not enough. Reads need protection too. An isolated former leader or a lagging follower can return old state, so a linearizable read needs a protocol that establishes current authority and reads through the required committed position. Depending on the system, this can use a quorum check, a read barrier, or a lease with explicit timing assumptions. During a network partition, replicas that cannot safely establish authority must reject requests or wait rather than return potentially stale results. In an interview, apply this cost to the smallest necessary boundary, such as one seat or account, rather than requiring every feed, search result, and analytics counter to be linearizable. ## Worked example: Two buyers claim one seat Seat A12 starts as available in a three-replica consensus group. Buyers X and Y concurrently submit claim(A12, buyer, requestId). The service evaluates each claim as one atomic state transition in the committed order. X's claim commits with support from two replicas and succeeds; Y's claim then finds the seat held and fails. A read starting after X receives success must show X's hold or a later valid state, never the earlier available state. If the leader becomes isolated, it cannot safely accept another claim. If X's response is lost, retrying the same request ID returns the recorded result rather than creating another hold. ## Trade-offs - **Coordination adds latency.** Replicated writes and linearizable reads may require network coordination, which becomes especially expensive across regions. - **Partitions reduce availability.** A replica unable to establish safe authority cannot keep completing every operation while preserving linearizability. - **Contention limits per-object throughput.** Operations competing for one seat, account, or counter need an agreed order, so adding shards does not eliminate contention on that object. - **Every serving path must honor the guarantee.** A stale cache, unsafe follower read, or obsolete leader can violate linearizability even when the main write path is correct. - **Multi-object invariants need more.** Linearizable operations on individual keys do not make a multi-key workflow atomic; it may require transactions or a different data model. - **Timeouts still leave uncertain outcomes.** An operation may commit before its response is lost, so retries still need idempotency keys or a way to retrieve the original outcome. ## When to use it in a system design interview - Two concurrent requests must not both acquire the same seat, driver assignment, worker lease, or account-wide stream slot. - A hard limit must hold across clients, such as a strict admission counter or a fixed-stock giveaway. - A completed state change must affect all subsequent decisions immediately, such as an ownership transfer or a security-sensitive revocation with no allowed staleness. - Leader failover must preserve acknowledged operations and prevent obsolete owners from continuing to act. - The interviewer asks exactly what a successful write acknowledgment guarantees to another client reading immediately afterward. ## How to bring it up in the interview - Name the invariant and operation first: “The seat claim must be an atomic, linearizable transition from available to held.” This is more precise than saying the whole database needs strong consistency. - Explain both concurrency and real-time ordering: overlapping requests may be ordered either way, but a request starting after a completed update cannot act on older state. - Describe the read path as well as the write path. Expect follow-ups about lagging replicas, old leaders, quorum checks, leases, and what happens during failover. - State the partition policy explicitly: requests that cannot reach a safe authority wait or fail. Contrast this with search and display paths where bounded staleness may be acceptable. - Separate the storage guarantee from application correctness. Interviewers may probe read-then-write races, multi-key transactions, ambiguous retries, and fencing of external side effects. ## Common mistakes - Equating linearizability with serializability: serializability orders transactions but does not by itself require that order to respect real time. - Assuming linearizable reads and writes make a separate read-check-write sequence atomic instead of using compare-and-set, a conditional update, or a suitable transaction. - Claiming that a leader or the formula R + W > N automatically proves linearizability without explaining concurrent writes, read behavior, and safe leader changes. - Serving reads from an asynchronous replica or cache while promising that every read sees completed writes. - Treating a linearizable lock as sufficient to stop a paused former owner from writing to another system; the destination may also need to enforce fencing tokens. ## Interview questions where it comes up - [Design a distributed key-value store](https://sysround.com/questions/design-key-value-store): The consistency contract determines whether completed writes must be visible to subsequent reads and which requests can succeed during partitions. - [Design a ticket booking system like Ticketmaster](https://sysround.com/questions/design-ticketmaster): An atomic, linearizable seat-claim operation prevents concurrent buyers from both acquiring the same available seat. - [Design Netflix's concurrent screen limit](https://sysround.com/questions/design-netflix-screen-limit): Account-wide slot allocation must have one authoritative order so concurrent regional starts cannot exceed the stream limit. - [Design a flash giveaway: 6 million burgers in an hour](https://sysround.com/questions/design-flash-sale): Scarce-stock claims need atomic allocation and failover behavior that preserves acknowledged successes. - [Design a control plane for a distributed database](https://sysround.com/questions/design-database-control-plane): Failover authority must be ordered consistently so competing controllers cannot both authorize themselves as the current owner. - [Design a ride hailing app like Uber](https://sysround.com/questions/design-uber): Exclusive driver assignment needs an atomic ownership transition rather than decisions based on stale availability reads. - [Design a distributed rate limiter](https://sysround.com/questions/design-rate-limiter): A strict distributed limit needs atomic admission decisions across clients, with an explicit availability policy when coordination fails. ## FAQ ### What is the difference between linearizability and serializability? Linearizability makes operations appear atomic and preserves the real-time order of non-overlapping operations. Serializability makes transactions equivalent to some serial execution, but that order need not respect real time. Strict serializability combines serializable transactions with real-time ordering. ### Is linearizability the same as strong consistency? Linearizability is one precise consistency guarantee; “strong consistency” is an ambiguous label unless the API contract defines it. Ask whether a read beginning after a successful write must observe that write or a newer one, and which operations and data boundaries the guarantee covers. ### Do quorum reads and writes guarantee linearizability? Not by themselves. Overlapping read and write quorums help replicas encounter common state, but a complete protocol must also handle concurrent writes, incomplete operations, and failures correctly. A quorum-backed consensus protocol with a safe read procedure is a common way to provide linearizable operations. ## Related concepts - [Serializability](https://sysround.com/concepts/serializability) - [Consensus algorithms](https://sysround.com/concepts/consensus) - [CAP theorem](https://sysround.com/concepts/cap-theorem) - [Quorums](https://sysround.com/concepts/quorums) --- SysRound (https://sysround.com) is an AI practice tool for system design interviews: a voice or typed AI interviewer, a shared whiteboard, then feedback on every skill and a model answer. Its feedback is AI-generated and can be wrong.