|Title:||LOFT: Lock-Free Transactional Data Structures
|Currently accessibly only within the Technion network|
|Abstract:||Concurrent data structures are widely used in modern multi-core architectures, providing atomicity (linearizability) for each concurrent operation. However, it is often desirable to execute several operations on multiple data structures atomically. This requirement cannot be easily supported by concurrent data structures, and requires the use of a locking mechanism or some sort of transactional framework. We present a design of such a transactional framework supporting linearizable transactions of multiple operations on multiple data structures in a lock-free manner. Our design is comprised of concurrent lock-free data structures supporting a transactional API, and a transaction engine responsible for executing operations as an atomic transaction. We employ a helping mechanism to obtain lock-freedom, and an advanced lock-free contention management mechanism to mitigate the effects of aborting transactions. When cyclic helping conflicts are detected, the contention manager reorders the conflicting transactions execution allowing all transactions to complete with minimal delay. Our design supports operation dependencies, i.e., results of operations can affect the inputs of subsequent operations or their control flow. To exemplify this framework we implement a transactional set using a skip-list, a transactional queue, and a transactional register. We present an evaluation of the system showing that we outperform general software transactional memory, and are competitive with lock-based transactional data structures, while providing an additional (lock-free) progress guarantee.|
|Copyright||The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information|
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2019/MSC/MSC-2019-01), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the MSC technical reports of 2019
To the main CS technical reports page
Computer science department, Technion