The Taub Faculty of Computer Science Events and Talks

It seems to be generally accepted that designing correct and efficient concurrent software is a sophisticated task that can only be held by experts. A crucial challenge then is to convert sequential code produced by a ``mainstream' programmer into concurrent one. Various synchronization techniques may be used for this, e.g., locks or transactional memory, but what does it mean for the resulting concurrent implementation to be correct? And which synchronization primitives provide more efficiencyat the end? In this talk, we introduce a correctness criterion for a transformation that enables the use of a sequential data structure in a concurrent system. Informally, we require that the resulting concurrent implementation is locally sequential: concurrent threads simply run the given sequential code and let the implementation worry about the potential conflicts. To make sense globally, the implementation should also be linearizable with respect to the object type of the data structure. We then evaluate the performance of different concurrent (locally sequential) implementations in terms of the set of schedules (interleavings of steps of the sequential code) they accept. Intuitively, this captures the amount of concurrency that a given implementation can stand. This allowed us to analyze relative power of seemingly different synchronization techniques, such as various forms of locking and transactional memory.