Three well studied progress conditions for implementing concurrent algorithms without locking are, obstruction-freedom, non-blocking
and wait-freedom. Obstruction-freedom is weaker than non-blocking which, in turn, is weaker than wait-freedom. While obstruction-freedom
and non-blocking have the potential to significantly improve the performance of concurrent applications, wait-freedom (although
desirable) imposes too much overhead upon the implementation.
In [5], Fich, Luchangco, Moir, and Shavit have presented an interesting transformation that converts any obstruction-free
algorithm into a wait-free algorithm when analyzed in the unknown-bound semi-synchronous model. The FLMS transformation uses
n atomic single-writer registers, n atomic multi-writer registers and a single fetch-and-increment object, where n is the number of processes.
We define a time complexity measure for analyzing such transformations, and prove that the time complexity of the FLMS transformation
is exponential in the number of processes n. This leads naturally to the question of whether the time and/or space complexity of the FLMS transformation can be improved
by relaxing the wait-freedom progress condition. We present several efficient transformations that convert any obstruction-free
algorithm into a non-blocking algorithm when analyzed in the unknown-bound semi-synchronous model. All our transformations
have O(1) time complexity. One transformation uses n atomic single-writer registers and a single compare-and-swap object; another transformation uses only a single compare-and-swap
object which is assumed to support also a read operation.