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 …

Date

2012

Authors

Vincent Gramoli, Petr Kuznetsov, Srivatsan Ravi

Book

Proceedings of the 2012 ACM symposium on Principles of distributed computing

Pages

241-242