What does linearizable mean in a distributed system?

In this article

1. Before you start
2. Why interviewers ask this
3. Linearizable from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page belongs to the distributed systems and system design learning path.

Why interviewers ask this

Any design with replicated data forces a choice about what a reader may see after a write, so the word linearizable comes up in storage, locking and database rounds. It can arrive as a follow-up to a question about caches, databases or coordination services.

A weak answer says "it means strongly consistent" and stops. A strong answer defines it through real time, gives a small example of a legal and an illegal history, and states the cost: Jepsen notes that the model cannot stay available through a network partition. A Staff-level answer also separates it from serializable and sequential consistency, because those are the neighbours interviewers mix up.

Linearizable from first principles

Linearizable

Linearizable is a property of a system in which every operation on an object appears to happen atomically at a single instant, and the order of those instants respects real time, so an operation that finishes before another starts is ordered first.

Linearization point

A linearization point is the single instant, between an operation's start and its finish, at which the operation appears to take effect, which lets a concurrent run be explained as a one-at-a-time sequence.

History

A history is the record of every operation in one run of a system, with each operation's start time, finish time and result, which is what a linearizability check examines.

In plain words

Picture one whiteboard in an office with one number on it. Anyone can read it or overwrite it. Once someone finishes writing 7, every later reader must see 7. Nobody may see the old number again. The analogy breaks in one place. In a real system the whiteboard is copied on many machines, and keeping the copies behaving like one board is the hard part.

In one precise sentence, a system is linearizable when its operations can be put in one line, each at a single instant inside its own start and finish, so that the line matches what clients saw and never reverses real-time order.

A register is a single storage cell that supports read and write; it is the usual object in these examples. Linearizability is a single-object model, and the scope of "an object" varies, for example one key in a key-value store. Herlihy and Wing introduced it in 1990, as Jepsen records.

Step 1: Every operation is an interval

A client sends a request at one time and gets the response at a later time. Between those two moments the operation is in flight. So an operation is an interval, not a point.

Input: the start and finish time of each call. Output: a set of intervals on a timeline. Two operations whose intervals overlap are concurrent. Two whose intervals do not overlap have a clear before and after. In the diagram, the write is a long interval that stays open while both reads happen. You now know what the checker looks at: intervals and results. The checker never needs to know how the system works inside; it only needs the recorded start, finish and result of each call.

Step 2: Each operation gets one instant inside its interval

Linearizable means each interval can be shrunk to a single instant, its linearization point, without changing what clients saw. The write takes effect at one instant. Each read takes effect at one instant. A read returns whatever value the register held at its instant.

Input: the intervals and the results. Output: a choice of one point per operation. This is the step that turns overlapping, messy activity into a tidy sequence. In the diagram, two reads join the write. Both reads overlap it, so for now nothing contradicts anything. The freedom to pick any instant inside the interval is what lets a concurrent run be explained as a simple sequence.

Step 3: Real time fixes some of the order

The order of the points may not contradict the clock. Jepsen states the rule: if A completes before B begins, B should logically take effect after A. This is what separates linearizable from weaker models.

Input: which intervals do not overlap. Output: forced pairs, "A before B". In the diagram the first read ends before the second read starts, so the first read must come first. Overlapping operations get no forced order. The write overlaps both reads, so it is free to go before, between or after them, as long as the results still make sense. Real time therefore removes some candidate orders but rarely all of them, and the remaining freedom is where the checking work lies.

Step 4: One order must explain every result

Now try to build the line. The first read returned 1, so the write must come before it. The second read must come after the first read, so it comes after the write too. It therefore has to return 1. If it returned 0, as in the diagram, no line works and the history is not linearizable.

Jepsen's formal version, after Viotti and Vukolić, has three constraints: one total order, the real-time rule, and results that obey the single-threaded laws of the object's datatype. For a register, a read returns the latest write before it in the line. You now have the full test: pick points, respect real time, and check that every result is what a single-threaded register would return.

1 · One write2 · Two reads3 · Real time4 · One orderReplay

Step-by-step description

1. An operation is an interval, not a point.
2. Both reads overlap the write.
3. The second read starts after the first ends.
4. No single order fits all three results.

• The write runs from time 0 to 6.
• The first read ends at time 3 and returns 1.
• The second read starts at time 4 and returns 0, so the history is not linearizable.

Worked example

Four small histories show the test by hand. The register starts at 0, client A writes 1 and client B reads. All times are illustrative units.¹

Take history H2: the write runs from time 0 to 3 and a read runs from 4 to 6 and returns 0. The write finished before the read began, so the write must come first, and the read should return 1. It returned 0, so no legal order exists.¹ History H3 differs in one way: the write runs from 0 to 6 and the read from 2 to 4 returns 0. The two overlap, so two orders respect real time and one of them, read then write, is legal.¹

History H2 is the useful contrast. Sequential consistency is a model that keeps one total order of operations (across all objects), and each client's own order, but drops the real-time rule. H2 passes it, because the read can be placed before the write. H2 fails linearizability, because a stale read after a finished write breaks real time.¹ Jepsen draws the same line between the two models.

How could a system implement this? One approach uses a quorum. A quorum is a group of nodes large enough that any two such groups share a node. A majority is such a group, since two majorities of n nodes overlap in at least one node.¹ Overlap alone is not enough.

In the Attiya–Bar-Noy–Dolev (ABD) algorithm a reader also writes the value it returns back to a majority before answering (Attiya, Bar-Noy and Dolev, 1995). Many systems instead run a consensus protocol such as Raft, which serves linearizable reads (Ongaro and Ousterhout, 2014). A majority of 3 nodes is 2 and tolerates 1 failure. A majority of 5 nodes is 3 and tolerates 2 failures. A majority of 7 nodes is 4 and tolerates 3 failures.¹

Text description of the diagram

• A majority of 3 nodes is 2 and tolerates 1 failure.
• A majority of 5 nodes is 3 and tolerates 2 failures.
• A majority of 7 nodes is 4 and tolerates 3 failures.

For sizing the cluster, see back-of-the-envelope estimation.

Trade-offs and edge cases

Linearizable systems pay in availability. Jepsen states that the model cannot be totally or sticky available: during a network partition, some or all nodes will be unable to make progress. A network partition is a failure in which some machines in a cluster cannot talk to others. This is the choice described by the CAP (consistency, availability, partition tolerance) trade-off, whose consistency is linearizability (Gilbert and Lynch, 2002): during a partition a linearizable store refuses some requests rather than return a stale answer.

Scope is the second edge. A linearizable property covers one object, so two linearizable keys do not give a consistent view across both. In practice, strict serializability is a model that combines serializable transactions over many objects with linearizability's real-time order. When you need linearizability across multiple objects, Jepsen suggests strict serializability. Under it, Jepsen describes the database as a single linearizable object whose state is the whole database (Jepsen, strong serializability). A payment system design is where that difference matters.

Third, a read served from a cache or a lagging replica may return an old value, so it is not linearizable unless the system proves the copy is current. Fourth, a request that times out may or may not have taken effect, so a checker cannot assume it failed.

Text description of the diagram

• Linearizable is a single-object model that respects real time.
• Sequential consistency keeps one total order but drops real time.
• Strict serializability adds real time to serializable transactions.

How to answer it in an interview

The spoken structure: say the definition, give the real-time rule, name the cost, then name the neighbour model.

Common mistakes

• "Linearizable is the same as serializable." (wrong) Serializable is about multi-object transactions with no real-time rule. (right) "Linearizable is single-object with real time; strict serializable joins the two."
• "Linearizable is sequential consistency." (wrong) Sequential consistency drops the real-time rule. (right) "Both give one total order, but only linearizable respects the clock."
• "A linearizable store stays up during a partition." (wrong) Some or all nodes cannot make progress. (right) "It trades availability for the stronger property."
• "Each read looked fine, so the system is linearizable." (wrong) Two reads can each be legal alone and contradict each other. (right) "I check the whole history for one order."

Follow-up questions

Is linearizable the same as serializable?

No. Linearizable orders operations on a single object by real time. Serializable orders multi-object transactions with no real-time rule. Their combination is strict serializability.

Is linearizable the same as sequential consistency?

No. Sequential consistency is a model that keeps one total order but drops the real-time constraint, so the stale read in history H2 is allowed there and not here.

Can a linearizable system stay available during a network partition?

Not fully. Jepsen states that some or all nodes will be unable to make progress. The trade-off is the CAP choice.

How do you check that a history is linearizable?

Try to build one legal order. For a tiny history you can try every order that respects real time, as the worked example does; real histories need a smarter search. See concurrency interview questions for related reasoning.

Does linearizable mean the same as ACID consistency?

No. ACID (atomicity, consistency, isolation, durability) uses consistency to mean that a transaction keeps the application's invariants true, and that says nothing about real-time order. The word names different ideas in different fields. Linearizability is a statement about how operations on one object are ordered in real time. More on related questions is in the backend interview questions.

What changes if the second read in history H4 overlaps the first?

Then real time no longer forces the first read before the second. The order "second read, write, first read" gives every read a legal value, so that variant is linearizable.

Sources

1. Linearizability — Jepsen (Kyle Kingsbury), 26 Oct 2026
2. Strong Serializability — Jepsen (Kyle Kingsbury), 26 Oct 2026
3. Linearizability: A Correctness Condition for Concurrent Objects — ACM Transactions on Programming Languages and Systems (Herlihy and Wing), 1 Jul 1990
4. Sharing Memory Robustly in Message-Passing Systems — Journal of the ACM (Attiya, Bar-Noy and Dolev), 1 Jan 1995
5. In Search of an Understandable Consensus Algorithm — USENIX ATC (Ongaro and Ousterhout), 19 Jun 2014
6. Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services — ACM SIGACT News (Gilbert and Lynch), 1 Jun 2002