Abstract
Transactional memory is perceived as an appealing alternative to critical sections for general purpose concurrent programming. Despite the large amount of recent work on transactional memory implementations, however, its actual specification has never been precisely defined. This paper presents opacity, a new correctness criterion for transactional memory systems. Opacity extends the notion of strict serializability, itself a strong form of the classical serializability property, with the requirement that even non-committed transactions are prevented from accessing inconsistent state. Yet opacity does not preclude versioning, invisible reads and lazy updates, often used by modern TM implementations. In fact, most transactional memory systems we know of ensure opacity. We prove a tight bound on the inherent cost of implementing opacity. The bound highlights a trade-off that explains some of the differences between current transactional memory systems, and also draws a sharp complexity line between opacity on one hand, and the combination of strict serializability and strict recoverability on the other hand.
Introduction
Transactional Memory (TM) emerged as a promising paradigm to simplify concurrent programming by allowing developers to wrap code blocks in atomic transactions. However, by 2007, while many implementations existed, the field lacked a rigorous mathematical definition of what "correctness" meant for a TM system. In their foundational paper, Rachid Guerraoui and Michał Kapałka introduced Opacity, a formal safety property that has since become the standard for TM correctness.
The Need for Opacity: Beyond Serializability
In traditional database systems, Serializability is the gold standard: the final outcome of concurrent transactions must be equivalent to some sequential execution. However, the authors argue that serializability is insufficient for general-purpose programming.
In a database, if a transaction observes an inconsistent state, it is simply aborted. In a programming environment (like C++ or Java), an inconsistent state—such as seeing a partial update to a pointer—could cause a "zombie" transaction to crash the application with a segmentation fault or enter an infinite loop before the system can trigger an abort.
As shown in Figure 1, transaction $T_2$ reads $x=1$ from $T_1$ and then $y=2$ from $T_3$. If $T_1$ and $T_3$ were intended to update $x$ and $y$ atomically (e.g., maintaining an invariant $x=y$), $T_2$ has seen a "garbage" state. Opacity ensures that even transactions that eventually abort, like $T_2$, must always observe a consistent snapshot of memory.
Formalizing the TM Interface
To define Opacity, the authors first establish a formal trace-based model of how transactions interact with a TM manager (TM).
Figure 2 illustrates this interface: a transaction $T_i$ invokes an operation ($inv_i$), the TM returns a value ($ret_i$), and the transaction eventually tries to commit ($tryC_i$), resulting in either a commit or an abort ($A_i$). A history is "opaque" if there exists a sequential execution of all transactions (committed, aborted, or live) that preserves the real-time order of non-overlapping transactions and ensures every transaction is "legal" according to the sequential specification of the objects it accesses.
Complexity and the "Performance Tax"
The paper doesn't just define a property; it explores the cost of enforcing it. The authors use their model to prove a lower bound on the time complexity of TM operations, identifying a fundamental trade-off between three desirable properties:
- Invisible Reads: Readers do not modify shared memory (improving scalability).
- Progressiveness: Transactions are only aborted if they truly conflict with another live transaction.
- Efficiency: Low time complexity for validation.
The authors prove that any single-version TM system using invisible reads that is also progressive must spend $\Omega(k)$ steps to validate a transaction, where $k$ is the number of objects accessed. This explains why systems like DSTM and ASTM have $\Theta(k)$ complexity. Conversely, it explains why the TL2 algorithm achieves constant-time complexity by sacrificing progressiveness—it aborts transactions more aggressively based on timestamps to avoid the validation tax.
Conclusion and Legacy
Opacity provides the "zombie protection" necessary for safe general-purpose programming. While the original paper focused on flat transactions and managed environments, its influence is pervasive. It drew a sharp line between Opacity and weaker properties like Strict Serializability, proving that the requirement to protect uncommitted transactions adds fundamental complexity to the system. Future work has since extended these concepts to nested transactions and systems with mixed transactional and non-transactional access.
Summary updated