Which value may a later reader see?

A product’s price is 20. The shop updates it to 25, receives a success reply, and then reads the price from another server. That server returns 20.

Before calling this a bug, we must specify the promise. A distributed service can offer different rules about how operations appear to readers. These rules are its consistency model.

Draw the operations in time

For now, treat the price as one register: an object supporting write(value) and read(). We are not yet combining multiple rows into a transaction.

A linearizable register behaves as though each operation took effect at one instant between its request and response. That imagined order must respect real-time order: if a write finishes before a read begins, the read cannot be ordered before that write.

Initial value: 20
No other writes are in progress.
Write 25 completes
The client receives success.
A later read begins
For a linearizable register, this read must return 25.

The completed write precedes the later read. Returning the old value would violate this particular promise.

If the read overlaps the write, either 20 or 25 may be explainable: the read could take effect before or after the write’s imagined instant. Overlap creates freedom; it does not permit arbitrary values such as 19.

Change the promise rather than the vocabulary

A lagging replica may intentionally serve older data. Under an eventual-convergence promise, copies should converge when updates stop and communication and processing succeed. That promise alone gives no fixed maximum staleness or guarantee that this client’s next read will observe its write.

Read-your-writes adds a narrower guarantee: later reads in a defined client session reflect that session’s completed writes. It does not by itself establish one real-time order for every client. Routing the session to a sufficiently advanced copy is one possible mechanism, with failure handling still required.

This differs from the transaction isolation problem. A price read can be individually current while a report combining price and stock still needs rules about which combinations are allowed. Single-object consistency and multi-operation transaction isolation answer related but different questions.

Predict an overlapping read

The write of 25 starts at time 10 and finishes at 14. A read starts at 12, returns 20 at 13, and no other writes occur. Is that history necessarily non-linearizable?

Place the operations in an allowed order

No. The read overlaps the write. We can place the read’s effect at time 12.5 and the write’s effect at time 13.5, both inside their own request/response intervals. A read that begins after time 14 could not use that explanation to return 20.

A clear promise lets us evaluate replication choices. The next page asks what must reach another machine before a write can be acknowledged.

Source and exercises: MIT’s consistency and linearizability teaching materials.

Extended reference

The extended chapter preserves the original technical coverage, additional examples, and citations. The explanation above supplies the concepts needed for this page; the reference develops the specialist cases.

Find a section from the original chapter