--- res: bibo_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. @eng' bibo_authorlist: - foaf_Person: foaf_givenName: Andreas foaf_name: Haas, Andreas foaf_surname: Haas - foaf_Person: foaf_givenName: Thomas A foaf_name: Henzinger, Thomas A foaf_surname: Henzinger foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87 orcid: 0000−0002−2985−7724 - foaf_Person: foaf_givenName: Andreas foaf_name: Holzer, Andreas foaf_surname: Holzer - foaf_Person: foaf_givenName: Christoph foaf_name: Kirsch, Christoph foaf_surname: Kirsch - foaf_Person: foaf_givenName: Michael foaf_name: Lippautz, Michael foaf_surname: Lippautz - foaf_Person: foaf_givenName: Hannes foaf_name: Payer, Hannes foaf_surname: Payer - foaf_Person: foaf_givenName: Ali foaf_name: Sezgin, Ali foaf_surname: Sezgin foaf_workInfoHomepage: http://www.librecat.org/personId=4C7638DA-F248-11E8-B48F-1D18A9856A87 - foaf_Person: foaf_givenName: Ana foaf_name: Sokolova, Ana foaf_surname: Sokolova - foaf_Person: foaf_givenName: Helmut foaf_name: Veith, Helmut foaf_surname: Veith bibo_doi: 10.4230/LIPIcs.CONCUR.2016.6 bibo_volume: 59 dct_date: 2016^xs_gYear dct_language: eng dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@ dct_title: Local linearizability for concurrent container-type data structures@ ...