Prompt and use cases
Explain the difference between linearizability and sequential consistency, give a read/write history where they differ, and explain the trade-off among consistency, latency, and availability in distributed systems. This is a useful follow-up for system-design, backend, data, and infrastructure roles.
This is not a vocabulary test. The interviewer wants one verifiable history that combines latest values, real-time order, per-client order, and replica delay.
What the interviewer evaluates
- Whether you say that a linearizable operation appears to take effect instantaneously between invocation and response.
- Whether you say sequential consistency requires one global order preserving each thread’s program order, but not real-time order across threads.
- Whether you can prove the difference with a counterexample instead of saying only that one is “stronger.”
- Whether you connect the models to read modes and costs in systems such as etcd.
Clarifications before answering
Ask whether the discussion concerns one object or a transaction, one client or many, and whether invocation and response times are known. Linearizability usually describes a concurrent object; multi-object transactions additionally need atomicity and isolation guarantees.
A 30-second answer
Linearizability requires a global order that respects real time: a completed write must be visible to a read that starts afterward. Sequential consistency preserves only each thread’s program order, so operations from different threads may be reordered. A post-write stale read violates linearizability; when calls overlap, a global order may still place the read first and satisfy sequential consistency. Stronger models require more coordination, which costs latency and partition-time availability.
Step-by-step explanation
Describe an operation history
Record invocation time, response time, thread, arguments, and result for every operation. Linearizability chooses a point between each invocation and response so that all operations form a legal single-threaded execution and completed operations retain their real-time order.
Sequential-consistency rule
Sequential consistency requires one global sequence in which each thread’s operations appear in its own program order. Operations from different threads may be reordered even when wall-clock order exists, as long as the history has no required real-time constraint.
A counterexample timeline
Thread A: write(x=1) returns; thread B then invokes read(x) and gets 0. For the same object, that history cannot be linearized. If the call intervals overlap, a system may place B’s read before A’s write in the global sequence, satisfying sequential consistency while violating real-time order.
~~~text Linearizable: A: write(1) ---- returns B: read() -> 1
Not linearizable: A: write(1) ---- returns B: read() -> 0
Sequentially consistent but not necessarily linearizable: A: write(1) ========= B: read() -> 0 ========= Global order may place B before A when the calls overlap. ~~~
Contrast with eventual consistency
Eventual consistency promises convergence after writes stop and enough time passes. It allows stale reads and does not automatically provide read-your-writes or monotonic reads. Linearizability gives stronger real-time semantics, usually by routing reads and writes through a leader or quorum.
Model answer
I describe linearizability as the illusion of one real-time copy: every operation has a linearization point between invocation and response, all operations form a legal sequential history, and completed operations keep their real-time order. Sequential consistency only requires a global history that preserves each thread’s program order, so cross-thread real-time order may be lost.
If A writes 1 and returns before B starts reading, B returning 0 violates linearizability. If the call intervals overlap, B’s read can appear before A’s write in the global history and still satisfy sequential consistency. Choose the model from the business need: locks, leases, and conditional updates often need linearizability; search indexes and analytics replicas may accept weaker semantics for lower latency and higher availability.
Common mistakes
- Calling a system “strongly consistent” without specifying real-time order.
- Describing sequential consistency as server-time sorting instead of a per-thread program-order rule.
- Saying eventual consistency “eventually reads the latest value” without discussing read-your-writes or monotonic reads.
- Assuming quorum automatically means linearizability without checking whether reads join the consensus path.
- Treating single-object linearizability as full isolation for a multi-object transaction.
Follow-up questions and responses
Why does linearizability usually cost more?
Reads may need confirmation from the current leader or a quorum, adding cross-region round trips. During a partition, the system may reject requests rather than return a result that violates real-time order.
Where is sequential consistency weaker?
It does not preserve wall-clock order across threads. Any global sequence that preserves each thread’s program order can be legal, making “a completed write was not visible to a later read” easier to hide.
What are etcd’s read modes?
etcd documents linearizable guarantees by default. A serializable read may return data stale relative to quorum, trading that risk for lower latency and higher throughput. Tie the mode to business risk instead of naming a configuration in isolation.
How do you test linearizability?
Record invocation and response times, thread, input, and result, then search for a legal linearization order. Inject delays, process pauses, and leader changes; a test that only runs sequentially cannot expose the important failures.
When is eventual consistency enough?
Feeds, search indexes, and reports can accept bounded staleness when the product makes that trade explicit. Important writes may still need read-your-writes, version numbers, or an explicit refresh path.
How do you close the answer?
Start with a timeline, state the model’s constraint, and finish with the business guarantee and its latency and availability cost. That demonstrates more understanding than reciting a CAP slogan.