形式陈述

历史 $H$$H$ 是线性一致的，若可先为部分 pending 调用补上响应、删除其余 pending 调用，得到完整历史 $H'$$H^{\prime }$，并存在一个合法顺序历史 $S$$S$，使：

1. $S$$S$ 与 $H'$$H^{\prime }$ 对每个进程的投影等价；
2. 若操作 $op_1$$o{p}_1$ 的响应在 $H$$H$ 中先于 $op_2$$o{p}_2$ 的调用，则 $op_1$$o{p}_1$ 在 $S$$S$ 中先于 $op_2$$o{p}_2$。

等价地，每个已完成操作可被视为在其调用与响应之间某个瞬间原子发生；该点称线性化点，但证明不一定要预先给出固定代码位置。

直觉

线性一致性把重叠操作自由排序，却绝不颠倒现实中已经完全结束后才开始的操作。使用者可把并发对象当作符合顺序规范的原子对象来推理。

例子与边界

若一次 write(1) 已返回，之后才调用 read()，线性一致寄存器不能让该读返回旧值。若读与写时间上重叠，则二者任一顺序都可能合法。线性化点可以依赖未来执行，甚至在帮助机制中由另一线程完成，不能机械等同于某一条本线程指令。

横线表示从调用到返回的操作区间；蓝点只是这段历史所选的线性化见证。非重叠操作保持实时顺序，重叠操作可按顺序规格与返回值选择合法顺序。

推论与应用

线性一致性是局部的：每个对象历史都线性一致时，组合历史也线性一致。它还保持实时顺序，因此通常适合模块化对象规范；但它是安全性质，不保证任何操作最终返回。

参考资料

• Maurice P. Herlihy and Jeannette M. Wing, “Linearizability: A Correctness Condition for Concurrent Objects,” ACM TOPLAS 12(3), 1990，Full paper, §§2–3。
• Hagit Attiya and Jennifer Welch, Distributed Computing: Fundamentals, Simulations, and Advanced Topics, 2nd ed., Wiley, 2004，Ch. 3。