Obstructionfree

Obstruction-free is a liveness property in concurrent computing, describing progress guarantees for shared data structures and algorithms. An operation is obstruction-free if it can complete in a finite number of steps when it runs in isolation, i.e., with no interference from other processes. This makes obstruction-free algorithms more practical in high-contention environments than strictly wait-free approaches, while still avoiding blocking behavior associated with locks.

Formal definition: In any execution where all other processes become quiescent after some point, a process performing the operation should complete after a finite number of its own steps. The property focuses on progress under isolation; it does not require progress guarantees when contention persists, and it can permit retries or restarts under interference.

Relation to other progress properties: Obstruction-free is weaker than wait-free, which guarantees finiteness of an operation regardless of contention. It is different in emphasis from lock-free or wait-free designs, which aim to guarantee system-wide progress under arbitrary scheduling. Obstruction-free is often easier to implement than wait-free, and can yield better performance in practice, but at the cost of possible starvation under contention.

History and usage: The term originated in the non-blocking synchronization literature, notably in the work of researchers like Maurice Herlihy and Nir Shavit. It is commonly discussed in texts on concurrent data structures, such as The Art of Multiprocessor Programming. Obstruction-free designs are used as building blocks for scalable, non-blocking implementations, including stacks and queues, where simple isolation progress is a reasonable assumption and contention is managed via retries.