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.