Detail

Sharing a Sequential Program: Correctness and Concurrency Analysis

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 incomparable synchronization techniques, such as various
forms of locking and transactional memory.

Joint work with Vincemnt Gramoli (U Sydney) and Srivatsan Ravi (TU Berlin)