---
title: "Linearizability and Checking a History"
description: "Linearizability says every operation appears to take effect at one instant between its call and its return, so a replicated store can be reasoned about as a single object. Whether a recorded history s"
canonical: https://lightmysky.com/learn/computing/linearizability-and-checking-a-history-mt_lTaHmlGtuo
source: https://lightmysky.com/learn/computing/linearizability-and-checking-a-history-mt_lTaHmlGtuo.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Linearizability and Checking a History

Linearizability says every operation appears to take effect at one instant between its call and its return, so a replicated store can be reasoned about as a single object. Whether a recorded history satisfies it is a decidable question, and the check is expensive.

Subject: Computing · Area: Networks & Security · Ages 22 to 23
Page: https://lightmysky.com/learn/computing/linearizability-and-checking-a-history-mt_lTaHmlGtuo

## Ready when they can

- Decide whether a short recorded history is linearizable and give the ordering or the conflict
- Say how linearizability differs from serializability and from a weaker consistency model
- Explain why the client-observed history, not the server's internal order, is what gets checked

## Lesson: One instant per operation

Every operation has a call, when you invoke it, and a return, when you get the answer. Linearizability says each operation appears to take effect at one single instant between its call and its return. The whole history then reads as if the operations ran one after another on a single object.

**Example.** A write of x = 1 starts and finishes. Then a read of x starts and returns 1. Place the write instant before the read instant and every answer makes sense. That order, write then read, is the single-object explanation.

To check a history, slide each instant inside its own call to return window until every read returns the latest write placed before it. Real-time order is law: an operation that finished before another started must come first, while overlapping operations may sit in either order. If no placement explains some read, that read is the conflict.

**Tip.** Judge only what clients saw: call and return times, never the server private order. Note the scope too: linearizability covers one object and honors real-time order. Serializability covers many objects inside transactions but ignores real-time gaps, while weaker models allow stale reads.

**Recap.** Each operation takes effect once inside its window, and the history must read as one real-time order.

## Practice

8 questions on this page, each with its working shown.

## Needs first

- [Quorums, Leases and Changing the Membership](https://lightmysky.com/learn/computing/quorums-leases-and-changing-the-membership-mt_2uRmRqFutD)
- [Consistency Models and the CAP Trade-off](https://lightmysky.com/learn/computing/consistency-models-and-the-cap-trade-off-mt_j6qtpYPHsr)

## Opens up

- [Distributed Transactions and the Blocking Case of Two-Phase Commit](https://lightmysky.com/learn/computing/distributed-transactions-and-the-blocking-case-of-two-phase-commit-mt_MP_B_a_EwW)