Alice writes value X to a linearizable key-value store and the write completes. She calls Bob and tells him to read the key. Bob issues a read. What does linearizability guarantee?
ANothing — linearizability only applies to operations from the same client
BBob will see value X, because Alice's write completed before Bob's read began, and linearizability ensures reads reflect all prior completed writes
CBob may or may not see X — linearizability only guarantees eventual consistency
DBob will see X only if Alice and Bob contact the same server replica
This is the defining scenario for linearizability. Alice's write completed (in real wall-clock time) before Bob's read began. Linearizability requires that Bob's read must observe Alice's write, because the write's linearization point precedes the start of the read. Sequential consistency would not guarantee this — it only requires some legal ordering, not one that respects actual real-time causality across clients.
Question 2 Multiple Choice
A distributed lock service requires that if client A releases a lock and client B then acquires it, B is guaranteed to see all state written by A before the release. Which consistency model is required?
AEventual consistency — the data will propagate to B eventually
BSequential consistency — any total ordering is sufficient for lock correctness
CLinearizability — real-time ordering must be preserved so B is guaranteed to see A's writes
DCausal consistency — tracking causally related operations is sufficient
Lock release and acquisition are real-time-ordered events from different clients. Linearizability guarantees that B's read after acquiring the lock reflects everything completed before B's operation began. Eventual consistency provides no timing guarantee. Sequential consistency does not require respecting real wall-clock time, so B might read stale data even after properly acquiring the lock. Only linearizability provides the required guarantee.
Question 3 True / False
A linearizable distributed system is expected to use a single physical server to maintain its 'single copy' behavioral guarantee.
TTrue
FFalse
Answer: False
Linearizability is a property of observable behavior, not implementation. Distributed systems achieve linearizability using consensus protocols like Raft or Paxos, which coordinate among multiple physical replicas to ensure every operation appears atomic at a single point in time. The 'single copy' semantics is an illusion maintained by the protocol — the physical implementation always involves multiple nodes.
Question 4 True / False
Sequential consistency and linearizability both produce a total order of operations, so they provide identical guarantees to distributed system clients.
TTrue
FFalse
Answer: False
Both produce a total order, but linearizability adds a critical constraint: that total order must respect real wall-clock time for non-overlapping operations. Sequential consistency only requires that some legal total order exists. The Alice-calls-Bob scenario illustrates the gap: sequential consistency does not guarantee Bob sees Alice's completed write; linearizability does, because it respects the actual real-time ordering.
Question 5 Short Answer
Why does achieving linearizability in a distributed system require consensus protocols like Paxos or Raft, and what does this cost?
Think about your answer, then reveal below.
Model answer: To ensure every operation appears atomic at a single point in time across all replicas, replicas must agree on a total order of operations — which requires consensus. Consensus requires multiple network round-trips between replicas, adding latency. More critically, the CAP theorem forces a tradeoff: during a network partition, a linearizable system must refuse requests from the isolated partition (sacrificing availability) to preserve consistency.
Every write must be confirmed by a quorum of replicas before being considered complete. This eliminates stale reads but means any replica outage or network partition can cause writes to stall. Systems like ZooKeeper and etcd accept this tradeoff for coordination tasks where correctness is paramount; they sacrifice availability to preserve linearizable semantics.