License
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://drops.dagstuhl.de/opus/volltexte/2016/6180/
Go to the corresponding LIPIcs Volume Portal


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

pdf-format:
LIPIcs-CONCUR-2016-6.pdf (0.6 MB)


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
Seminar: 27th International Conference on Concurrency Theory (CONCUR 2016)
Issue Date: 2016
Date of publication: 16.08.2016


DROPS-Home | Fulltext Search | Imprint Published by LZI