Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2012-03-21
Computer Science
Distributed, Parallel, and Cluster Computing
Scientific paper
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? In this paper, 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 \emph{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 \emph{linearizable} with respect to the \emph{object type} of the data structure. We then evaluate the performance of different concurrent (locally sequential) implementations in terms of the sets of \emph{schedules} (interleavings of steps of the sequential code) they \emph{accept}. Intuitively, this captures the amount of concurrency that a given implementation can stand. This allowed us to analyze relative power of seemingly incomparable synchronization techniques, such as various forms of locking and transactional memory.
Gramoli Vincent
Kuznetsov Petr
Ravi Srivatsan
No associations
LandOfFree
From Sequential to Concurrent: Correctness and Relative Efficiency does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with From Sequential to Concurrent: Correctness and Relative Efficiency, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and From Sequential to Concurrent: Correctness and Relative Efficiency will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-488721