License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2016.6
URN: urn:nbn:de:0030-drops-61809
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6180/
Haas, Andreas ;
Henzinger, Thomas A. ;
Holzer, Andreas ;
Kirsch, Christoph M. ;
Lippautz, Michael ;
Payer, Hannes ;
Sezgin, Ali ;
Sokolova, Ana ;
Veith, Helmut
Local Linearizability for Concurrent Container-Type Data Structures
Abstract
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.
BibTeX - Entry
@InProceedings{haas_et_al:LIPIcs:2016:6180,
author = {Andreas Haas and Thomas A. Henzinger and Andreas Holzer and Christoph M. Kirsch and Michael Lippautz and Hannes Payer and Ali Sezgin and Ana Sokolova and Helmut Veith},
title = {{Local Linearizability for Concurrent Container-Type Data Structures}},
booktitle = {27th International Conference on Concurrency Theory (CONCUR 2016)},
pages = {6:1--6:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-017-0},
ISSN = {1868-8969},
year = {2016},
volume = {59},
editor = {Jos{\'e}e Desharnais and Radha Jagadeesan},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6180},
URN = {urn:nbn:de:0030-drops-61809},
doi = {10.4230/LIPIcs.CONCUR.2016.6},
annote = {Keywords: (concurrent) data structures, relaxed semantics, linearizability}
}
|
Keywords: |
|
(concurrent) data structures, relaxed semantics, linearizability |
|
Collection: |
|
27th International Conference on Concurrency Theory (CONCUR 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
24.08.2016 |
