Linearizability

Linearizability requires each operation to appear to take effect at one instant between its invocation and response. The resulting order must respect non-overlapping operations: if one operation completes before another starts, the first must precede the second in that order. Return values must also follow the object’s sequential rules.

For a register initially holding 0, suppose a read starts, a write of 1 starts and completes, and then the read returns 0. This can be linearizable: the read and write overlap, so the read can take effect before the write even though its response arrives afterward. A read that starts after that write completes cannot return 0 unless another intervening write makes 0 the appropriate value. The guarantee concerns an order within operation intervals, not the order in which responses happen to arrive.

It is also the consistency used in the formal statement of the CAP result — Gilbert and Lynch’s proof used atomic, or linearizable, consistency, as Abadi’s paper restates. That detail matters when reading CAP arguments, because weaker models are not what the theorem constrains.

Replicated implementations must establish enough authority and ordering to answer safely, but they need not perform a fresh quorum round trip for every read. The Raft paper describes confirming leadership with a majority before serving a read, and an alternative lease approach that relies on bounded clock skew. A valid lease can support reads without a new round trip on each request; acquiring or renewing that authority still has a cost, and reads must stop when the implementation can no longer establish their safety. The latency trade-off discussed by PACELC depends on the operation and protocol.

The scope of the object matters. A key-value store might guarantee linearizability for each key, while another interface treats a table or database operation as one abstract operation. Individually linearizable key operations do not automatically make a transaction across keys atomic. Serializability constrains transaction outcomes to a serial order; adding real-time order gives strict serializability. Read the product’s operation and transaction scope before equating these guarantees. Operation histories can expose violations, as in Jepsen testing, but a successful finite test does not prove all executions correct.

Where the weaker models sit relative to this one, and when the coordination is worth paying for, is worked through in Replication, Consistency, and Time.

References

• Jepsen, Linearizability
• Daniel J. Abadi, Consistency Tradeoffs in Modern Distributed Database System Design (2012)
• Diego Ongaro and John Ousterhout, In Search of an Understandable Consensus Algorithm (2014), sections 2, 5.6 and 8