---
_id: '1095'
abstract:
- lang: eng
  text: ' 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. '
acknowledgement: "This work has been supported by the National Research Network RiSE
  on Rigorous Systems Engineering\r\n(Austrian Science Fund (FWF): S11402-N23, S11403-N23,
  S11404-N23, S11411-N23), a Google\r\nPhD Fellowship, an Erwin Schrödinger Fellowship
  (Austrian Science Fund (FWF): J3696-N26), EPSRC\r\ngrants EP/H005633/1 and EP/K008528/1,
  the Vienna Science and Technology Fund (WWTF) trough\r\ngrant PROSEED, the European
  Research Council (ERC) under grant 267989 (QUAREM) and by the\r\nAustrian Science
  Fund (FWF) under grant Z211-N23 (Wittgenstein Award)."
alternative_title:
- LIPIcs
article_number: '6'
author:
- first_name: Andreas
  full_name: Haas, Andreas
  last_name: Haas
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Andreas
  full_name: Holzer, Andreas
  last_name: Holzer
- first_name: Christoph
  full_name: Kirsch, Christoph
  last_name: Kirsch
- first_name: Michael
  full_name: Lippautz, Michael
  last_name: Lippautz
- first_name: Hannes
  full_name: Payer, Hannes
  last_name: Payer
- first_name: Ali
  full_name: Sezgin, Ali
  id: 4C7638DA-F248-11E8-B48F-1D18A9856A87
  last_name: Sezgin
- first_name: Ana
  full_name: Sokolova, Ana
  last_name: Sokolova
- first_name: Helmut
  full_name: Veith, Helmut
  last_name: Veith
citation:
  ama: 'Haas A, Henzinger TA, Holzer A, et al. Local linearizability for concurrent
    container-type data structures. In: <i>Leibniz International Proceedings in Informatics</i>.
    Vol 59. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:<a href="https://doi.org/10.4230/LIPIcs.CONCUR.2016.6">10.4230/LIPIcs.CONCUR.2016.6</a>'
  apa: 'Haas, A., Henzinger, T. A., Holzer, A., Kirsch, C., Lippautz, M., Payer, H.,
    … Veith, H. (2016). Local linearizability for concurrent container-type data structures.
    In <i>Leibniz International Proceedings in Informatics</i> (Vol. 59). Quebec City;
    Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.CONCUR.2016.6">https://doi.org/10.4230/LIPIcs.CONCUR.2016.6</a>'
  chicago: Haas, Andreas, Thomas A Henzinger, Andreas Holzer, Christoph Kirsch, Michael
    Lippautz, Hannes Payer, Ali Sezgin, Ana Sokolova, and Helmut Veith. “Local Linearizability
    for Concurrent Container-Type Data Structures.” In <i>Leibniz International Proceedings
    in Informatics</i>, Vol. 59. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2016. <a href="https://doi.org/10.4230/LIPIcs.CONCUR.2016.6">https://doi.org/10.4230/LIPIcs.CONCUR.2016.6</a>.
  ieee: A. Haas <i>et al.</i>, “Local linearizability for concurrent container-type
    data structures,” in <i>Leibniz International Proceedings in Informatics</i>,
    Quebec City; Canada, 2016, vol. 59.
  ista: 'Haas A, Henzinger TA, Holzer A, Kirsch C, Lippautz M, Payer H, Sezgin A,
    Sokolova A, Veith H. 2016. Local linearizability for concurrent container-type
    data structures. Leibniz International Proceedings in Informatics. CONCUR: Concurrency
    Theory, LIPIcs, vol. 59, 6.'
  mla: Haas, Andreas, et al. “Local Linearizability for Concurrent Container-Type
    Data Structures.” <i>Leibniz International Proceedings in Informatics</i>, vol.
    59, 6, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:<a href="https://doi.org/10.4230/LIPIcs.CONCUR.2016.6">10.4230/LIPIcs.CONCUR.2016.6</a>.
  short: A. Haas, T.A. Henzinger, A. Holzer, C. Kirsch, M. Lippautz, H. Payer, A.
    Sezgin, A. Sokolova, H. Veith, in:, Leibniz International Proceedings in Informatics,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
conference:
  end_date: 2016-08-26
  location: Quebec City; Canada
  name: 'CONCUR: Concurrency Theory'
  start_date: 2016-08-23
date_created: 2018-12-11T11:50:07Z
date_published: 2016-08-01T00:00:00Z
date_updated: 2025-04-15T06:25:58Z
day: '01'
ddc:
- '004'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.CONCUR.2016.6
ec_funded: 1
file:
- access_level: open_access
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:10:10Z
  date_updated: 2018-12-12T10:10:10Z
  file_id: '4795'
  file_name: IST-2017-793-v1+1_LIPIcs-CONCUR-2016-6.pdf
  file_size: 589747
  relation: main_file
file_date_updated: 2018-12-12T10:10:10Z
has_accepted_license: '1'
intvolume: '        59'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '267989'
  name: Quantitative Reactive Modeling
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z211
  name: Formal methods for the design and analysis of complex systems
publication: Leibniz International Proceedings in Informatics
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '6280'
pubrep_id: '793'
quality_controlled: '1'
scopus_import: 1
status: public
title: Local linearizability for concurrent container-type data structures
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 59
year: '2016'
...