Linearizability — One Copy of the Data, Atomic Operations, No Going Back
each bar is a request from send to response · the client only knows the database processed it somewhere inside the bar
① A linearizable execution — register x flips from 0 to 1 at one hidden instant (Figures 10-2 / 10-3)
client A
client B
client C
read(x) ⇒ 0
read(x) ⇒ 1
read(x) ⇒ 1
write(x, 1) ⇒ OK
linearization point — x becomes 1 atomically here
ends before the write starts ⇒ must see the old value
overlaps the write ⇒ 0 or 1 both legal; returns 1
starts after A saw 1 ⇒ must see at least 1
real-time order
② The violation — a read goes backwards in real time (Figure 10-1: two fans, one hears the final score first)
reader 1
reader 2
read(x) ⇒ 1 (fresh)
read(x) ⇒ 0 — STALE
2 reloads after 1 reported the result
The recency guarantee
Once any read returns the new value,
every later read — on any client — must
return at least that value until it is
overwritten again.
Concurrent operations (bars overlapping) may be ordered either way — the database may reorder them internally.
But the joined-up linearization points must always move forward in time: real-time-before must stay before.
Serializability is a different axis (grouping ops into transactions); linearizability is about single-object recency.