Comment by gpderetta

I need to re-read the paper, but:

>"LP" is not obstruction-free but is wait-free

As far as I know, wait-free is a superset of lock-free and lock-free is a superset of obstruction-free. How can LP be wait-free but not obstruction free?

In any case a wait-free algorithm can't live-lock by definition (progress and fairness of all threads is guaranteed), but the catch is that while the STM runtime itself might have this property, it doesn't necessarily translate to an algorithm implemented in the runtime (which makes sense, you should be able to implement a lock with an STM).

So, yes, the paper is interesting, but probably not relevant for this discussion and I shouldn't have brought it up.

Now the question again remains, do concrete STM implementations actually provide the guarantee you mentioned earlier, i.e. does a transaction aborting guarantees that another succeeds? I would think it doesn't as I think it would be very costly to implement: both transactions might end up aborting when detecting conflict.

Maybe what concrete runtimes actually guarantee is that there is an upper bound on the spurious aborts and restarts as worst case you can fall back on a single global lock for serialization when the upper bound is reached.