Local linearizability for concurrent container-type data structures

Haas, Andreas and Henzinger, Thomas A and Holzer, Andreas and Kirsch, Christoph M and Lippautz, Michael and Payer, Hannes and Sezgin, Ali and Sokolova, Ana and Veith, Helmut (2016) Local linearizability for concurrent container-type data structures. In: CONCUR: Concurrency Theory, August 23-26, 2016, Quebec City, Canada.

[img] Text
LIPIcs-CONCUR-2016-6.pdf - Published Version
Available under License Creative Commons Attribution.
Download (575Kb)
Official URL: http://dx.doi.org/10.4230/LIPIcs.CONCUR.2016.6


The semantics of concurrent data structures is usually given by a sequential specification and a consistency condition. Linearizability is the most popular consistency condition due to its simplicity and general applicability. Nevertheless, for applications that do not require all guarantees offered by linearizability, recent research has focused on improving performance and scalability of concurrent data structures by relaxing their semantics. In this paper, we present local linearizability, a relaxed consistency condition that is applicable to container-type concurrent data structures like pools, queues, and stacks. While linearizability requires that the effect of each operation is observed by all threads at the same time, local linearizability only requires that for each thread T, the effects of its local insertion operations and the effects of those removal operations that remove values inserted by T are observed by all threads at the same time. We investigate theoretical and practical properties of local linearizability and its relationship to many existing consistency conditions. We present a generic implementation method for locally linearizable data structures that uses existing linearizable data structures as building blocks. Our implementations show performance and scalability improvements over the original building blocks and outperform the fastest existing container-type implementations.

Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: data structures, linearizability, relaxed semantics
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 004 Data processing & computer science
Research Group: Henzinger Group
SWORD Depositor: Sword Import User
Depositing User: Sword Import User
Date Deposited: 16 Mar 2017 07:59
Last Modified: 16 Mar 2017 07:59
URI: https://repository.ist.ac.at/id/eprint/793

Actions (login required)

View Item View Item