Conflict abstractions and shadow speculation for optimistic transactional objects

Thomas Dickerson, Eric Koskinen, Paul Gazzillo, Maurice Herlihy

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

Concurrent data structures implemented with software transactional memory (STM) perform poorly when operations which do not conflict in the definition of the abstract data type nonetheless incur conflicts in the concrete state of an implementation. Several works addressed various aspects of this problem, yet we still lack efficient, general-purpose mechanisms that allow one to readily integrate black-box concurrent data-structures into existing STM frameworks. In this paper we take a step further toward this goal, by focusing on the challenge of how to use black-box concurrent data structures in an optimistic transactional manner, while exploiting an off-the-shelf STM for transaction-level conflict detection. To this end, we introduce two new enabling concepts. First, we define data-structure conflict in terms of commutativity but, unlike prior work, we introduce a new format called conflict abstractions, which is kept separate from the object implementation and is fit for optimistic conflict detection. Second, we describe shadow speculation for wrapping off-the-shelf concurrent objects so that updates can be speculatively and opaquely applied—and even return values observed—but then later dropped (on abort) or else atomically applied (on commit). We have realized these concepts in a new open-source transactional system called ScalaProust, built on top of ScalaSTM and report encouraging experimental results. Further detail and experimental results can be found in the extended version of this paper [8].

Original languageEnglish
Title of host publicationProgramming Languages and Systems - 17th Asian Symposium, APLAS 2019, Proceedings
EditorsAnthony Widjaja Lin
Pages313-331
Number of pages19
DOIs
StatePublished - 2019
Event17th Asian Symposium on Programming Languages and Systems, APLAS 2019 - Bali, Indonesia
Duration: 1 Dec 20194 Dec 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11893 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th Asian Symposium on Programming Languages and Systems, APLAS 2019
Country/TerritoryIndonesia
City Bali
Period1/12/194/12/19

Fingerprint

Dive into the research topics of 'Conflict abstractions and shadow speculation for optimistic transactional objects'. Together they form a unique fingerprint.

Cite this