Abstract

How to turn a sequential implementation of a data structure (a hash table, a list, a tree, etc.) into a correct and, preferably, efficient concurrent one? What if we provide an environment in which a user can locally run the sequential code so that the resulting execution is globally correct.
One way to do this is to use locks to make sure that critical parts of a sequential program can only be accessed in an exclusive mode. An implementation that grabs a lock on the whole data structure before executing a sequential operation imposes a serial order but ignores all the benefits provided by the multiprocessing power of modern machines. Efficient fine-grained locking requires lots of intelligence, since it must be based on good understanding of which parts of the sequential code to protect at what time. A more automated approach is to use transactional memory (TM) and treat each (sequential) operation as a transaction. If the transaction commits, the corresponding operation returns the response computed based on the values read in the course of the transaction. Otherwise, if the transaction aborts, the operation does not take effect. This approach promises to make use of the hardware concurrency at low intellectual cost. But does this simplicity bring a considerable efficiency degradation with respect to fine-grained locking? To tackle this question, we first define the very meaning of a correct transformation of a sequential program into a concurrent one. More precisely, we model an execution of a concurrent implementation as a sequence of invocations and responses of the high-

Date

September 10, 2025

Authors

PK Vincent Gramoli, S Ravi

Journal

4th Workshop on the Theory of Transactional Memory, Madeira, Portugal