How free is your linearizable concurrent data structure?

T.A. Henzinger, A. Sezgin, How Free Is Your Linearizable Concurrent Data Structure?, IST Austria, 2013.

Download
OA 249.79 KB

Technical Report | Published | English
Department
Series Title
IST Austria Technical Report
Abstract
Linearizability requires that the outcome of calls by competing threads to a concurrent data structure is the same as some sequential execution where each thread has exclusive access to the data structure. In an ordered data structure, such as a queue or a stack, linearizability is ensured by requiring threads commit in the order dictated by the sequential semantics of the data structure; e.g., in a concurrent queue implementation a dequeue can only remove the oldest element. In this paper, we investigate the impact of this strict ordering, by comparing what linearizability allows to what existing implementations do. We first give an operational definition for linearizability which allows us to build the most general linearizable implementation as a transition system for any given sequential specification. We then use this operational definition to categorize linearizable implementations based on whether they are bound or free. In a bound implementation, whenever all threads observe the same logical state, the updates to the logical state and the temporal order of commits coincide. All existing queue implementations we know of are bound. We then proceed to present, to the best of our knowledge, the first ever free queue implementation. Our experiments show that free implementations have the potential for better performance by suffering less from contention.
Publishing Year
Date Published
2013-06-12
Page
16
ISSN
IST-REx-ID

Cite this

Henzinger TA, Sezgin A. How Free Is Your Linearizable Concurrent Data Structure? IST Austria; 2013. doi:10.15479/AT:IST-2013-123-v1-1
Henzinger, T. A., & Sezgin, A. (2013). How free is your linearizable concurrent data structure? IST Austria. https://doi.org/10.15479/AT:IST-2013-123-v1-1
Henzinger, Thomas A, and Ali Sezgin. How Free Is Your Linearizable Concurrent Data Structure? IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-123-v1-1.
T. A. Henzinger and A. Sezgin, How free is your linearizable concurrent data structure? IST Austria, 2013.
Henzinger TA, Sezgin A. 2013. How free is your linearizable concurrent data structure?, IST Austria, 16p.
Henzinger, Thomas A., and Ali Sezgin. How Free Is Your Linearizable Concurrent Data Structure? IST Austria, 2013, doi:10.15479/AT:IST-2013-123-v1-1.
Main File(s)
Access Level
OA Open Access
Last Uploaded
2018-12-12T11:53:19Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar