TY - GEN
T1 - Conflict abstractions and shadow speculation for optimistic transactional objects
AU - Dickerson, Thomas
AU - Koskinen, Eric
AU - Gazzillo, Paul
AU - Herlihy, Maurice
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2019.
PY - 2019
Y1 - 2019
N2 - 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].
AB - 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].
UR - http://www.scopus.com/inward/record.url?scp=85076696171&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85076696171&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-34175-6_16
DO - 10.1007/978-3-030-34175-6_16
M3 - Conference contribution
AN - SCOPUS:85076696171
SN - 9783030341749
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 313
EP - 331
BT - Programming Languages and Systems - 17th Asian Symposium, APLAS 2019, Proceedings
A2 - Lin, Anthony Widjaja
T2 - 17th Asian Symposium on Programming Languages and Systems, APLAS 2019
Y2 - 1 December 2019 through 4 December 2019
ER -