Concepts and theorems · Intermediate

Consistency models: what a read is allowed to observe

Use operation histories to distinguish sequential consistency, linearizability, and eventual convergence.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Specify permitted histories
  2. Separate process order from real time
  3. Work through a register history
  4. Choose guarantees for the actual operation
  5. Ask Logeia about this articleCheck your understanding

Specify permitted histories

A consistency model describes which histories of operations an implementation may expose. Agreement between two replicas at one instant is not enough to establish the model. Record invocation and response events, the process issuing each operation, and the returned values. Shared-memory systems and distributed storage have different failure assumptions, but both benefit from separating the abstract contract from the mechanism used to implement it.

Separate process order from real time

Sequential consistency requires an explanation using one total order that preserves each process’s program order. It need not preserve every real-time relationship between different processes. Linearizability adds a real-time requirement: if one operation finishes before another begins, their abstract order must reflect that relationship. Each operation should appear to take effect at a point between its invocation and response. Overlapping operations can still be ordered either way when the object specification permits it.

Work through a register history

Consider a register initially holding zero. Client A writes one and receives success. Only afterward does client B invoke a read and receive zero. Assume there are no other writes. This is not a linearizable history of that register because the completed write must precede the later read. Under sequential consistency alone, with no additional ordering constraint connecting A and B, a total order placing B’s read before A’s write may explain the observations. Always state these assumptions before judging a trace; a different object specification or an intervening write can change the conclusion.

Choose guarantees for the actual operation

Eventual consistency concerns convergence when updates stop and the relevant delivery and reconciliation conditions hold. By itself it does not specify a maximum convergence delay, the values returned during convergence, or whether a client immediately reads its own writes. Inventory reservation, configuration distribution, and activity aggregation can therefore require different guarantees even within one application. Describe the required operation, its dependencies on previous results, and its behavior during a partition. The label strong or weak is too vague to replace that contract, and a benchmark cannot establish a universal guarantee merely by failing to observe a counterexample.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Understand the systems behind the web · STEP 17

Choose a learning path