How Free is Your Linearizable Concurrent Data Structure?

Henzinger, Thomas A and Sezgin, Ali (2013) How Free is Your Linearizable Concurrent Data Structure? Technical Report. IST Austria.

[img] Text
main-concur2013.pdf - Published Version
Available under License All rights reserved.
[IST-2013-123-v1+1]
Download (243Kb)

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.

Item Type: Monograph (Technical Report)
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems
000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 004 Data processing & computer science
Research Group: Henzinger Group
Depositing User: Ali Sezgin
Date Deposited: 12 Jun 2013 14:12
Last Modified: 31 Dec 2016 14:47
URI: https://repository.ist.ac.at/id/eprint/123

Actions (login required)

View Item View Item