---
_id: '5402'
abstract:
- lang: eng
  text: "Linearizability requires that the outcome of calls by competing threads to
    a concurrent data structure is the same as some sequential execution where each
    thread has exclusive access to the data structure. In an ordered data structure,
    such as a queue or a stack, linearizability is ensured by requiring threads commit
    in the order dictated by the sequential semantics of the data structure; e.g.,
    in a concurrent queue implementation a dequeue can only remove the oldest element.
    \r\nIn this paper, we investigate the impact of this strict ordering, by comparing
    what linearizability allows to what existing implementations do. We first give
    an operational definition for linearizability which allows us to build the most
    general linearizable implementation as a transition system for any given sequential
    specification. We then use this operational definition to categorize linearizable
    implementations based on whether they are bound or free. In a bound implementation,
    whenever all threads observe the same logical state, the updates to the logical
    state and the temporal order of commits coincide. All existing queue implementations
    we know of are bound. We then proceed to present, to the best of our knowledge,
    the first ever free queue implementation. Our experiments show that free implementations
    have the potential for better performance by suffering less from contention."
alternative_title:
- IST Austria Technical Report
author:
- 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: Ali
  full_name: Sezgin, Ali
  id: 4C7638DA-F248-11E8-B48F-1D18A9856A87
  last_name: Sezgin
citation:
  ama: Henzinger TA, Sezgin A. <i>How Free Is Your Linearizable Concurrent Data Structure?</i>
    IST Austria; 2013. doi:<a href="https://doi.org/10.15479/AT:IST-2013-123-v1-1">10.15479/AT:IST-2013-123-v1-1</a>
  apa: Henzinger, T. A., &#38; Sezgin, A. (2013). <i>How free is your linearizable
    concurrent data structure?</i> IST Austria. <a href="https://doi.org/10.15479/AT:IST-2013-123-v1-1">https://doi.org/10.15479/AT:IST-2013-123-v1-1</a>
  chicago: Henzinger, Thomas A, and Ali Sezgin. <i>How Free Is Your Linearizable Concurrent
    Data Structure?</i> IST Austria, 2013. <a href="https://doi.org/10.15479/AT:IST-2013-123-v1-1">https://doi.org/10.15479/AT:IST-2013-123-v1-1</a>.
  ieee: T. A. Henzinger and A. Sezgin, <i>How free is your linearizable concurrent
    data structure?</i> IST Austria, 2013.
  ista: Henzinger TA, Sezgin A. 2013. How free is your linearizable concurrent data
    structure?, IST Austria, 16p.
  mla: Henzinger, Thomas A., and Ali Sezgin. <i>How Free Is Your Linearizable Concurrent
    Data Structure?</i> IST Austria, 2013, doi:<a href="https://doi.org/10.15479/AT:IST-2013-123-v1-1">10.15479/AT:IST-2013-123-v1-1</a>.
  short: T.A. Henzinger, A. Sezgin, How Free Is Your Linearizable Concurrent Data
    Structure?, IST Austria, 2013.
date_created: 2018-12-12T11:39:07Z
date_published: 2013-06-12T00:00:00Z
date_updated: 2020-07-14T23:04:47Z
day: '12'
ddc:
- '000'
- '004'
department:
- _id: ToHe
doi: 10.15479/AT:IST-2013-123-v1-1
file:
- access_level: open_access
  checksum: ce580605ae9756a8c99d7b403ebb8eed
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T11:53:19Z
  date_updated: 2020-07-14T12:46:45Z
  file_id: '5480'
  file_name: IST-2013-123-v1+1_main-concur2013.pdf
  file_size: 249790
  relation: main_file
file_date_updated: 2020-07-14T12:46:45Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: '16'
publication_identifier:
  issn:
  - 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '123'
status: public
title: How free is your linearizable concurrent data structure?
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...