Local linearizability for concurrent container-type data structures Conference Paper

Author(s): Haas, Andreas; Henzinger, Thomas A; Holzer, Andreas; Kirsch, Christoph M; Lippautz, Michael; Payer, Hannes; Sezgin, Ali; Sokolova, Ana; Veith, Helmut
Title: Local linearizability for concurrent container-type data structures
Title Series: LIPIcs
Affiliation IST Austria
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.
Keywords: data structures; linearizability; relaxed semantics
Conference Title: CONCUR: Concurrency Theory
Volume: 59
Conference Dates: August 23-26, 2016
Conference Location: Québec City, Canada
ISBN: 978-3-95977-017-0
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik  
Date Published: 2016-01-01
Start Page: 6:1
End Page: 6:15
Copyright Statement: CC BY
DOI: 10.4230/LIPIcs.CONCUR.2016.6
Notes: This work has been supported by the National Research Network RiSE on Rigorous Systems Engineering (Austrian Science Fund (FWF): S11402-N23, S11403-N23, S11404-N23, S11411-N23), a Google PhD Fellowship, an Erwin Schrödinger Fellowship (Austrian Science Fund (FWF): J3696-N26), EPSRC grants EP/H005633/1 and EP/K008528/1, the Vienna Science and Technology Fund (WWTF) trough grant PROSEED, the European Research Council (ERC) under grant 267989 (QUAREM) and by the Austrian Science Fund (FWF) under grant Z211-N23 (Wittgenstein Award).
Open access: yes (OA journal)
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
  2.  Ali Sezgin
    5 Sezgin
Related IST Austria Work