Linearizability

Formal definition

A replicated register is linearizable iff every operation can be placed on a single global timeline such that:

1. Real-time order respected

   If op A’s response is observed before op B’s invocation, then A → B on that timeline.

2. Single-copy illusion

   Reads return the value of the latest preceding write on that timeline.

Think of a debugger that single-steps through a distributed execution.

You must be able to insert a vertical tick mark for each op so that the ticks never run backwards.

Internals:

• Each op has a linearization point between its RPC send and its RPC reply.
• Leader-based systems choose the point when an entry becomes durable on a quorum (Raft: once matchIndex ≥ majority).

Performance limits

Let u = worst-case uncertainty of one-way network delay.

Any algorithm that gives linearizable reads or writes must sometimes stall for ≥ u.

If the WAN’s 99-th percentile RTT = 600 ms, strong reads cannot always be faster than that.

Interview sound-bytes

• “Linearizability = single-copy + real-time ordering. If you can’t afford the latency budget, drop to causal or timeline consistency.”
• “Exactly once semantics?—first make your write linearizable, then de-dupe on the consumer side.”

Causality and its weaker-but-faster world

The happened-before relation