Lock-free shared data structures in the setting of distributed
computing have received a fair amount of attention. Major motivations
of lock-free data structures include
increasing fault tolerance of a (possibly heterogeneous) system and getting rid of the problems
associated with critical sections such as priority inversion
and deadlock. For parallel computers with closely-coupled
processors and shared memory, these issues are no longer major concerns. While many of the
results are applicable especially when the model used is shared memory
multiprocessors, no prior studies have considered improving the
performance of a parallel implementation by way of lock-free
programming. As a matter of fact, often times in practice lock free
data structures in a distributed setting
do not perform as well as those that use locks. As the data
structures and algorithms for parallel computing are often
drastically different from those in distributed computing, it is possible
that lock-free programs perform better. In this paper we compare the similarity and difference of
lock-free programming in both distributed and parallel
computing environments and explore the possibility of adapting lock-free
programming to parallel computing to improve performances. Lock-free
programming also provides a new way of simulating PRAM and asynchronous
PRAM algorithms on current parallel machines.
