On the Implementation of Concurrent Objects

Michel Raynal 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : 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.
Type de document :
[Research Report] PI-1968, 2011, pp.22
Liste complète des métadonnées

Littérature citée [50 références]  Voir  Masquer  Télécharger

Contributeur : Ist Rennes <>
Soumis le : jeudi 17 mars 2011 - 11:38:27
Dernière modification le : vendredi 16 novembre 2018 - 01:40:28
Document(s) archivé(s) le : samedi 18 juin 2011 - 03:10:30


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00577736, version 1


Michel Raynal. On the Implementation of Concurrent Objects. [Research Report] PI-1968, 2011, pp.22. 〈inria-00577736〉



Consultations de la notice


Téléchargements de fichiers