# Concurrency cheatsheet

See Kir Fraser's dissertation "Practical Lock Freedom".

## Structure properties

**Lock-freedom**: A data structure is lock-free iff *some* operation on the
structure completes after a finite number of steps have been executed system-wide.

**Wait-freedom**: A data structure is wait-free iff *every* operation on the
structure completes after a finite number of steps. Livelock is impossible and worst-case
execution is known for every operation.

**Obstruction-freedom**: A data structure is obstruction-free iff *every* operation
on the structure completes after executing a finite number of steps that do not contend with
any concurrent operation for access to any memory location.

## Operation properties

**Disjoint-access parallelism**: A set of operations are disjoint-access parallel iff
any pair of operation invocations which access disjoint sets of memory locations do not directly
affect each others' execution.

**Linearizability**: If an operation is implemented as a synchronous procedure, a call to that procedure
is an invocation and the eventual return from that procedure is a response. An operation is linearizable iff
it *appears* to execute instantaneously at some point between its invocation and its response.

**Serializability**: A series of operation is serializable iff invocations and responses can be reordered to yield
a sequential history, and such history would be compatible with each operation precedence. This is less strict than
linearizability, because such compatible reordering can exist without instantaneous operations.