Skip to Main content Skip to Navigation

Looking for Efficient Implementations of Concurrent Objects

Achour Mostefaoui 1 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 : As introduced by Taubenfeld, a contention-sensitive implementation of a concurrent object is an implementation such that the overhead introduced by locking is eliminated in the common cases, i.e., when there is no contention or when the operations accessing concurrently the object are non-interfering. This paper, that can be considered as an introductory paper to this topic, presents a methodological construction of a contention-sensitive implementation of a concurrent stack. In a contention-free context a push or pop operation does not rest on a lock mechanism and needs only six accesses to the shared memory. In case of concurrency a single lock is required. Moreover, the implementation is starvation-free (any operation is eventually executed). The paper, that presents the algorithms in an incremental way, visits also a family of liveness conditions and important concurrency-related concepts such as the notion of an abortable object.
Document type :
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Ist Rennes Connect in order to contact the contributor
Submitted on : Tuesday, March 15, 2011 - 12:32:05 PM
Last modification on : Thursday, January 20, 2022 - 4:20:17 PM
Long-term archiving on: : Thursday, June 16, 2011 - 2:50:12 AM


Files produced by the author(s)


  • HAL Id : inria-00576742, version 1


Achour Mostefaoui, Michel Raynal. Looking for Efficient Implementations of Concurrent Objects. [Research Report] PI-1969, 2011, pp.10. ⟨inria-00576742⟩



Record views


Files downloads