@inproceedings{golan-gueta2013concurrent,
author = {Golan-Gueta, Guy and Ramalingam, G. and Sagiv, Mooly and Yahav, Eran and Ramalingam, G.},
title = {Concurrent libraries with foresight},
booktitle = {Programming Language Design and Implementation (PLDI)},
year = {2013},
month = {June},
abstract = {Linearizable libraries provide operations that appear to execute
atomically. Clients, however, may need to execute a sequence of operations
(a composite operation) atomically. We consider the problem
of extending a linearizable library to support arbitrary atomic
composite operations by clients. We introduce a novel approach in
which the concurrent library ensures atomicity of composite operations
by exploiting information (foresight) provided by its clients.
We use a correctness condition, based on a notion of dynamic rightmovers,
that guarantees that composite operations execute atomically
without deadlocks, and without using rollbacks.
We present a static analysis to infer the foresight information
required by our approach, allowing a compiler to automatically
insert the foresight information into the client. This relieves the
client programmer of this burden and simplifies writing client code.
We present a generic technique for extending the library implementation
to realize foresight-based synchronization. This technique
is used to implement a general-purpose Java library for Map
data structures — the library permits composite operations to simultaneously
work with multiple instances of Map data structures.
We use the Maps library and the static analysis to enforce atomicity
of a wide selection of real-life Java composite operations. Our
experiments indicate that our approach enables realizing efficient
and scalable synchronization for real-life composite operations.},
url = {http://approjects.co.za/?big=en-us/research/publication/concurrent-libraries-with-foresight/},
pages = {263-274},
edition = {Programming Language Design and Implementation (PLDI)},
}