Editing Linearizability (section)

{{short description|Property of some operation(s) in concurrent programming}}
{{Duplication|date=November 2018|dupe=serializability|dupe2=atomicity (database systems)}}
[[File:Linearlizable Process.svg|thumb|In grey a linear sub-history, processes beginning in {{math|b}} do not have a linearizable history because {{math|b0}} or {{math|b1}} may complete in either order before {{math|b2}} occurs.]]

In [[concurrent programming]], an operation (or set of operations) is '''linearizable''' if it consists of an ordered list of [[Execution (computing)|invocation]] and response [[Event (computing)|events]], that may be extended by adding response events such that:

# The extended list can be re-expressed as a sequential history (is [[serializability|serializable]]). 
# That sequential history is a subset of the original unextended list.

Informally, this means that the unmodified list of events is linearizable [[if and only if]] its invocations were serializable, but some of the responses of the serial schedule have yet to return.<ref name=":0" />

In a concurrent system, processes can access a shared [[Object (computer science)|object]] at the same time. Because multiple processes are accessing a single object, a situation may arise in which while one process is accessing the object, another process changes its contents. Making a system linearizable is one solution to this problem. In a linearizable system, although operations overlap on a shared object, each operation appears to take place instantaneously. Linearizability is a strong correctness condition, which constrains what outputs are possible when an object is accessed by multiple processes concurrently. It is a safety property which ensures that operations do not complete unexpectedly or unpredictably. If a system is linearizable it allows a programmer to reason about the system.<ref>{{Cite journal|last1=Shavit|first1=Nir|last2=Taubenfel|first2=Gadi|year=2016|title=The Computability of Relaxed Data Structures: Queues and Stacks as Examples|url=http://www.faculty.idc.ac.il/gadi/MyPapers/2015ST-RelaxedDataStructures.pdf|journal=Distributed Computing|volume=29|issue=5|pages=396–407|doi=10.1007/s00446-016-0272-0|s2cid=16192696}}</ref>