Linearizability

Linearizability is a strong consistency property in which each operation appears to take effect atomically at one point between its invocation and response, while preserving real-time order. It gives clients the illusion that a replicated or concurrent object behaves like one correct single-copy object.

The property is useful for locks, configuration changes, account balances, inventory reservations, leader metadata, safety commands and other state where stale observations can cause incorrect action. It is also expensive because reads and writes may need coordination rather than local cache access.

Linearization Point

For an operation:

let invocation time be:

and response time be:

Linearizability requires a logical effect time:

such that:

The operation appears to take effect at that point, even if the implementation uses messages, retries, locks, logs or compare-and-swap loops internally.

Real-Time Order

If operation:

finishes before operation:

begins, then the linearized order must preserve that real-time order:

This is what makes a completed write visible to later reads under the same object contract.

Read-After-Write

If a write sets:

and completes before a read begins, then a linearizable read must return 7 or a later value in the same object history. Returning the older value is a stale read.

The rule is simple at the interface and difficult in a distributed implementation. Follower reads, caches, asynchronous replication and read replicas can all violate it unless they are covered by a quorum, lease, commit index or freshness check.

Boundary With Serializability

Linearizability is usually an object-level or operation-level property with real-time order. Serializability is usually a transaction property: concurrent transactions must appear equivalent to some serial order, but that order may not preserve real-time order unless the system provides strict serializability.

Sequential consistency also allows a single order that respects each process’s program order, but it does not necessarily preserve real-time order across processes. For engineering claims, the exact consistency term matters.

Implementation Cost

Linearizable writes often require consensus, quorum commit, a leader, or a compare-and-swap style atomic update. Linearizable reads may need to contact the leader, confirm a current lease, perform a read quorum, or prove that the local replica has observed the committed index.

A simplified latency screen is:

If commit confirmation is:

and a later read confirmation costs:

then the screened read-after-write path is:

Follower Lag Screen

If a follower is behind by:

seconds and writes arrive at rate:

then the approximate number of unseen writes is:

For:

the follower may be behind by:

Serving an unconstrained read from that follower should not be called linearizable.

Boundary With CAP

During a partition, a system that preserves linearizability may have to reject operations that cannot reach the required authority. That is a CP-style choice in CAP terminology. A system that keeps serving every partitioned client may provide availability, but it needs weaker semantics or a reconciliation rule.

Linearizability is therefore a product contract, not only a storage detail. The user-facing API should state which operations are linearizable and which are eventually consistent, cached, best effort or stale-safe.

Validation

Validation should record operation histories with invocation time, response time, value, node, term, commit index, read source, cache state, retry identity and failure injection. Linearizability checkers can search for a legal serial order that fits the observed history.

Useful tests include concurrent reads and writes, leader failover, follower reads, cache invalidation, clock skew, delayed messages, duplicate retries, partition and heal, snapshot restore, log compaction and client timeout followed by retry.

Failure Modes

Common failure modes include claiming strong consistency while serving follower reads, using wall-clock timestamps as proof of order, acknowledging writes before durable commit, losing the linearization point during retry, reading through stale caches, mixing linearizable and non-linearizable paths under one API name, and validating only single-client histories.

A credible linearizability claim should identify the object boundary, the linearization point, the read path, the failure cases that were tested and the operational evidence that stale paths are rejected or clearly labeled.