Comparisons and explanations · Intermediate

Serializability versus linearizability

Compare transaction serializability with operation linearizability using histories that distinguish atomic grouping from real-time order.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Choose the unit being ordered
  2. Real-time precedence makes a difference
  3. Serializability alone does not prescribe wall-clock order
  4. Correct individual operations do not make a transaction
  5. Separate safety from progress and availability
  6. Record enough history to test the claim
  7. Ask Logeia about this articleCheck your understanding

Choose the unit being ordered

Serializability concerns transactions whose concurrent effects are equivalent to some serial execution. Linearizability concerns operations on an object that can be explained as taking effect at one point between invocation and response while respecting real-time precedence. First decide whether the unit is a transaction or an individual read or write. Comparing guarantees only with stronger and weaker labels obscures that difference. Atomic grouping of several steps and observations after a completed operation solve related but separate problems. A history should identify operation boundaries, transaction boundaries, and what each response promises before either correctness condition can be applied.

Real-time precedence makes a difference

Start a register at zero. A writes one and receives success before B invokes a read. With no intervening write, B must return one if the register is linearizable. Explaining a zero result by placing B before A would violate real-time precedence. When their invocation-response intervals overlap, more than one ordering can instead be permitted by the object specification. This reasoning does not require every client to share a perfectly synchronized wall clock. It uses the precedence visible in the operation history. Distinguish nonoverlap from overlap before interpreting two different observed values as either a fault or a permitted concurrent outcome.

Serializability alone does not prescribe wall-clock order

Serializability asks for an equivalent serial order; that condition alone does not define the order as every transaction’s real-time completion order. Strict serializability adds a real-time constraint at the transaction level. If the requirement is that a transaction started after a successful update must observe its effect, describe both the transactional unit and the external ordering requirement. A product offering an isolation level named Serializable does not automatically extend that guarantee to a separate application cache or an asynchronously replicated read path. Include the actual route used for each operation rather than reasoning only about the primary database’s configuration name.

Correct individual operations do not make a transaction

Consider two clients that read a balance, add ten locally, and write the computed replacement. Even if each read and each write is linearizable, both reads can observe the same old value before either write occurs. Two later replacement writes can then lose one increment. Atomic individual operations do not make the whole read-compute-write sequence atomic. An atomic increment, conditional update, or suitable transaction addresses a different boundary. Stating that the store is linearizable is insufficient to establish every multi-operation business invariant. Identify which operations must be grouped and which external ordering the grouped result must satisfy.

Separate safety from progress and availability

Linearizability constrains whether returned results fit the object specification; it does not promise that every request finishes within a deadline or succeeds during every network partition. A serializable database can also abort transactions on conflict, requiring application retry handling. When inspecting successful histories, preserve what happened to canceled, failed, or unknown-outcome requests as well. A design that waits to preserve an ordering guarantee and one that permits older reads to remain responsive make different trade-offs. Describe result correctness and operating conditions separately. Otherwise a latency comparison can accidentally count a weaker contract as an implementation improvement of the original requirement.

Record enough history to test the claim

For a small verification, record operation IDs, invocation and response events, object identifiers, inputs, outputs, and transaction boundaries. Ask whether a legal ordering exists rather than checking only a final value that can hide incorrect intermediate reads. If machine clocks differ, explain what evidence establishes nonoverlapping real-time precedence. The register and increment examples here are explanatory histories, not reported product measurements. After choosing the desired contract, verify that database, cache, replica, and application operation boundaries actually align with it. A familiar consistency label is useful only when its scope matches the path exercised by the user’s request.

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

Learn this in order

Understand the systems behind the web · STEP 13

Choose a learning path