License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2019.24
URN: urn:nbn:de:0030-drops-113310
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11331/
Go to the corresponding LIPIcs Volume Portal

Khyzha, Artem ; Attiya, Hagit ; Gotsman, Alexey

Privatization-Safe Transactional Memories

pdf-format:
LIPIcs-DISC-2019-24.pdf (0.5 MB)

Abstract

Transactional memory (TM) facilitates the development of concurrent applications by letting the programmer designate certain code blocks as atomic. Programmers using a TM often would like to access the same data both inside and outside transactions, and would prefer their programs to have a strongly atomic semantics, which allows transactions to be viewed as executing atomically with respect to non-transactional accesses. Since guaranteeing such semantics for arbitrary programs is prohibitively expensive, researchers have suggested guaranteeing it only for certain data-race free (DRF) programs, particularly those that follow the privatization idiom: from some point on, threads agree that a given object can be accessed non-transactionally.
In this paper we show that a variant of Transactional DRF (TDRF) by Dalessandro et al. is appropriate for a class of privatization-safe TMs, which allow using privatization idioms. We prove that, if such a TM satisfies a condition we call privatization-safe opacity and a program using the TM is TDRF under strongly atomic semantics, then the program indeed has such semantics. We also present a method for proving privatization-safe opacity that reduces proving this generalization to proving the usual opacity, and apply the method to a TM based on two-phase locking and a privatization-safe version of TL2. Finally, we establish the inherent cost of privatization-safety: we prove that a TM cannot be progressive and have invisible reads if it guarantees strongly atomic semantics for TDRF programs.

BibTeX - Entry

@InProceedings{khyzha_et_al:LIPIcs:2019:11331,
  author =	{Artem Khyzha and Hagit Attiya and Alexey Gotsman},
  title =	{{Privatization-Safe Transactional Memories}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{24:1--24:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Jukka Suomela},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11331},
  URN =		{urn:nbn:de:0030-drops-113310},
  doi =		{10.4230/LIPIcs.DISC.2019.24},
  annote =	{Keywords: Transactional memory, privatization, observational refinement}
}

Keywords: Transactional memory, privatization, observational refinement
Collection: 33rd International Symposium on Distributed Computing (DISC 2019)
Issue Date: 2019
Date of publication: 08.10.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI