Petr Kuznetsov received his Ph.D. in computer science from EPFL in 2005 (Distributed Programming Lab, Prof. Rachid Guerraoui) and did a postdoc at Max Planck Institute for Software Systems (the group of Prof. Peter Druschel) in 2005-2008. Since 2008, he is a senior research scientist at Deutsche Telekom Laboratories and Technical University of Berlin. His research interests are in foundations of distributed systems, in particular, synchronization and fault-tolerance, transactional memory, complexity and computability bounds in concurrent systems.
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 efficiency at the end?
We introduce a correctness criterion for a
transformation that enables the use of a sequential data structure
in a concurrent system. We then evaluate the performance of resulting
concurrent implementations in terms of the sets of concurrent schedules
(interleavings of steps of the sequential code) they accept.
Intuitively, this captures the amount of concurrency that a given
implementation can stand.
This allows us to analyze relative power of seemingly different
synchronization techniques, such as various forms of locking and
transactional memory