Editing Non-blocking algorithm (section)

== Obstruction-freedom ==
Obstruction-freedom is the weakest natural non-blocking progress guarantee. An algorithm is obstruction-free if at any point, a single thread executed in isolation (i.e., with all obstructing threads suspended) for a bounded number of steps will complete its operation.<ref name="awilliams" /> All lock-free algorithms are obstruction-free.

Obstruction-freedom demands only that any partially completed operation can be aborted and the changes made rolled back. Dropping concurrent assistance can often result in much simpler algorithms that are easier to validate. Preventing the system from continually [[livelock|live-locking]] is the task of a contention manager.

Some obstruction-free algorithms use a pair of "consistency markers" in the data structure.  Processes reading the data structure first read one consistency marker, then read the relevant data into an internal buffer, then read the other marker, and then compare the markers.  The data is consistent if the two markers are identical.  Markers may be non-identical when the read is interrupted by another process updating the data structure.  In such a case, the process discards the data in the internal buffer and tries again.