What is the difference between lock-free and obstruction-free?

Question

I am reading up on Transactional Memory (TM), and one of the papers I'm reading says[1]:

Indeed, it was two nonblocking algorithms, the obstruction-free DSTM and lock-free FSTM that reinvigorated STM research in the past decade.

I was under the impression that lock implied obstruction. Apparently, I was wrong...

What is the difference between the terms "lock-free" and "obstruction-free"?

Sennet

I described wait-freedom, lock-freedom, obstruction-freedom, blocking guarantees from practical point of view here: 1024cores.net/home/lock-free-algorithms/introduction – Prerogative

Answer 1

Here are the definitions from Herlihy & Shavit's The Art Of Multiprocessor Programing.

A method is wait-free if it guarantees that every call finishes its execution in a finite number of steps.

A method is lock-free if it guarantees that infinitely often some method call finishes in a finite number of steps.

A method is obstruction-free if, from any point after which it executes in isolation, it finishes in a finite number of steps (method call executes in isolation if no other threads take steps).

All wait-free methods are lock-free, and all lock-free methods are obstruction-free.

Axiomatic

According to the paper ["On the nature of progress" by Maurice Herlihy et al@OPODIS'2011 [Fig. 1]](cs.tau.ac.il/~shanir/progress.pdf), I am afraid it is not the case that all lock-free methods are obstruction-free. – Fanya

en.wikipedia.org/wiki/Non-blocking_algorithm has more explanation of the categories. Lock-free can include CAS retry loops. Obstruction free but not lock-free can involve cancelling another thread's attempted operation if they conflict with each other, apparently. – Tigges