Linearizability

Linearizability is defined per-object (or per-key), not per-system. Formally, given a history of operations with invocation and response timestamps, a linearizable history requires that there exists a total order over all operations such that: (1) the order is consistent with the real-time precedence of non-overlapping operations (if op A completes before op B is invoked, A must precede B in the order), and (2) each read observes the value written by the most recent write in that order. This is stricter than serializability, which only guarantees a total order without the real-time constraint — a serializable system can reorder non-overlapping transactions arbitrarily, a linearizable one cannot.

Under the hood, achieving linearizability requires either a single authoritative writer (e.g., a leader elected via Raft or Paxos) or a quorum protocol where reads and writes intersect on at least one common replica (R + W > N), combined with mechanisms to prevent stale reads from a deposed leader — typically a lease or fencing token. Without such a mechanism, a partitioned former leader can serve a read after a new leader has already committed a conflicting write, violating the real-time ordering guarantee even though each individual replica is internally consistent.

• Read-side cost: Naive linearizable reads often require a full consensus round-trip (e.g., a no-op Raft log entry) to confirm leadership before serving data, which is why systems like etcd offer a distinct --consistency=linearizable flag versus a cheaper, potentially stale local read.
• CAP interaction: Linearizability is the ‘C’ in CAP. Under a network partition, a linearizable system must sacrifice availability on the minority side (return errors or block) rather than risk serving divergent state — this is the direct architectural tension PACELC formalizes for the non-partitioned case.
• Composability trap: Linearizability of individual operations does NOT imply linearizability of multi-object transactions across those operations; combining two linearizable single-key stores does not yield a linearizable multi-key system without additional coordination (e.g., 2PC or a Saga).

In practice, most “strongly consistent” databases (CockroachDB, Spanner, etcd, ZooKeeper) advertise linearizability only for specific operation classes — typically single-key reads/writes or explicit transactions — while defaulting other paths to weaker models like sequential or causal consistency for latency reasons. Engineers must audit client libraries carefully: a driver’s default read mode silently downgrading to a local replica read (common in multi-region deployments to cut tail latency) breaks the linearizability guarantee even if the underlying consensus layer is fully capable of providing it, leading to subtle bugs that only manifest during leader failover or network jitter.