Correctness of concurrent executions of closed nested transactions in transactional memory systems

摘要

A generally agreed upon requirement for correctness of concurrent executions in transactional memory is that all transactions including the aborted ones read consistent values. Opacity is a commonly accepted correctness criterion that satisfies the above requirement. Our first contribution in this paper is extending the opacity definition for closed nested transactions. Second, we define a restricted class, again for closed nested transactions, that preserves conflicts. This is akin to conflict-serializable class for traditional database transactions. Our conflict definition is appropriate for optimistic executions which are most common in Software Transactional Memory (STM) systems. We show that membership in the new class can be checked in polynomial time. With opacity, an aborted transaction (considering only the read steps that were executed before aborting) may affect the consistency for the transactions that are executed subsequently. This property is not desirable in general and may be harmful for closed nested transactions in the sense that the abort of a sub-transaction may make committing its top-level transaction impossible. As our third contribution, we propose a correctness criterion that defines a class of schedules where aborted transactions do not affect consistency for other transactions. We define a conflict-preserving subclass of this class as well. Then we give the outline of a scheduler that implements this subclass. Both the class definitions and the conflict definition are new for nested transactions.