1 Search Results for "Khyzha, Artem"


Document
Privatization-Safe Transactional Memories

Authors: Artem Khyzha, Hagit Attiya, and Alexey Gotsman

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)


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.

Cite as

Artem Khyzha, Hagit Attiya, and Alexey Gotsman. Privatization-Safe Transactional Memories. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{khyzha_et_al:LIPIcs.DISC.2019.24,
  author =	{Khyzha, Artem and Attiya, Hagit and Gotsman, Alexey},
  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 =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.24},
  URN =		{urn:nbn:de:0030-drops-113310},
  doi =		{10.4230/LIPIcs.DISC.2019.24},
  annote =	{Keywords: Transactional memory, privatization, observational refinement}
}
  • Refine by Author
  • 1 Attiya, Hagit
  • 1 Gotsman, Alexey
  • 1 Khyzha, Artem

  • Refine by Classification
  • 1 Software and its engineering → Software verification
  • 1 Theory of computation → Concurrency
  • 1 Theory of computation → Program semantics

  • Refine by Keyword
  • 1 Transactional memory
  • 1 observational refinement
  • 1 privatization

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail