of invocations and responses made of an object by a set of threads or processes. An invocation can be thought of as the start of an operation, and the response being the signaled end of that operation. Each invocation of a function will have a subsequent response. This can be used to model any use of an object. Suppose, for example, that two threads, A and B, both attempt to grab a lock, backing off if it's already taken. This would be modeled as both threads invoking the lock operation, then both threads receiving a response, one successful, one not. A sequential history is one in which all invocations have immediate responses; that is the invocation and response are considered to take place instantaneously. A sequential history should be trivial to reason about, as it has no real concurrency; the previous example was not sequential, and thus is hard to reason about. This is where linearizability comes in. A history is linearizable if there is a linear order of the completed operations such that: For every completed operation in , the operation returns the same result in the execution as the operation would return if every operation was completed one by one in order . If an operation op1 completes (gets a response) before op2 begins (invokes), then op1 precedes op2 in . In other words: its invocations and responses can be reordered to yield a sequential history; that sequential history is correct according to the sequential definition of the object; if a response preceded an invocation in the original history, it must still precede it in the sequential reordering. (Note that the first two bullet points here match serializability: the operations appear to happen in some order. It is the last point which is unique to linearizability, and is thus the major contribution of Herlihy and Wing.) Let us look at two ways of reordering the locking example above. Reordering B's invocation below A's response yields a sequential history. This is easy to reason about, as all operations now happen in an obvious order. Unfortunately, it doesn't match the sequential definition of the object (it doesn't match the semantics of the program): A should have successfully obtained the lock, and B should have subsequently aborted. This is another correct sequential history. It is also a linearization! Note that the definition of linearizability only precludes responses that precede invocations from