obstruction-free progress

Picture two people trying to write on the same whiteboard. If they keep bumping elbows, neither finishes a sentence. But if one of them simply steps away — stops interfering — the other can finish cleanly. Obstruction-freedom captures exactly that weakest useful kind of promise: any thread will finish IF it gets to run alone for a while, with no one else touching the shared structure.

Precisely: an algorithm is obstruction-free if a thread completes its operation in a bounded number of steps whenever it runs in isolation — that is, when all other threads are paused. It says nothing about what happens under active contention; two obstruction-free threads can interfere with each other forever, each repeatedly undoing the other's progress. This is the well-known livelock failure mode. Obstruction-freedom is strictly weaker than lock-freedom: every lock-free algorithm is obstruction-free, but an obstruction-free one can livelock and so is not lock-free.

Why define such a weak property at all? Because it is easier to achieve, and it cleanly separates the correctness of the algorithm from its progress under contention. An obstruction-free algorithm is correct on its own; you then bolt on a contention manager — typically randomized exponential backoff — that makes threads step out of each other's way often enough to break livelocks in practice. Software transactional memory systems were a famous early home for this idea: get the algorithm obstruction-free first, then manage contention separately.