A Wait-free, Transaction Friendly Universal Construction

Faith Ellen, U Toronto


A concurrent data structure is transaction friendly if processes can gracefully
exit an operation, either because a problem has been detected,
or because the operation is taking too long to perform. We present the

first universal construction that transforms any sequential data structure
into a wait-free transaction friendly concurrent data structure.

The resulting concurrent data structure is efficient and allows queries to
be performed in parallel.


This is joint work with Phong Chuong and Vijaya Ramachandran
and it extends our SPAA 2010 paper.