Non-Blocking Algorithms

Overview

An algorithm is said to be non-blocking if failure or suspension of any threads cannot cause failure or suspension of another thread.

Wait-freedom

An algorithm is wait-free if it guarantees per-thread progress. In other words, every thread is guaranteed to make progress over an arbitrary period of time, regardless of timing or ordering of thread execution.

Lock-freedom

An algorithm is lock-free if it guarantees system-wide progress. In other words, at least one thread is guaranteed to make progress over an arbitrary period of time.

Obstruction-freedom

An algorithm is obstruction-free if it guarantees thread-level progress if said thread can run in isolation. In other words, so long as other threads do not interfere, any one thread can make progress over an arbitrary period of time.