Transactional Data Structures with Orthogonal Metadata

Abstract

Transactional Data Structure Programming Systems (TD-SPSs) let programmers compose method invocations on concurrent data structures into coarse-grained, isolated transactions. They detect conflicts among concurrent transactions and recover when operations do not commute.

We present Harmony, a new TDSPS design that orchestrates two categories of metadata: one for synchronization and another for transaction management. By separating these responsibilities, Harmony avoids unnecessary conflicts and simplifies the implementation of complex data structures like skip lists, resizable arrays, deques, and hash tables. These data structures support both read-only and mutating range queries efficiently.