On the Implementation of Concurrent Objects

The implementation of objects shared by concurrent processes, with provable safety and liveness guarantees, is a fundamental issue of concurrent programming in shared memory systems. It is now largely accepted that linearizability (or atomicity) is an appropriate consistency condition for concurrent objects. On the liveness side, progress conditions (mainly absence of deadlock or the stronger absence of starvation) have been stated and investigated since a long time and are now well-mastered. The situation is dierent in asynchronous shared memory systems prone to process failures. This paper visits three progress conditions suited to concurrent objects in presence of failures, namely obstruction-freedom, non-blocking and wait-freedom. To that end, the paper visits also appropriate com- putation models and paradigm problems to illustrate this family of progress conditions. The paper has consequently an introductory and survey avor. Its aim is to help people better understand the diculties, subtleties and beauties encountered when one has to implement concurrent objects despite the net eect of asynchrony and failures