A Thrifty Universal Construction

A universal construction is an algorithm which transforms any sequential implementation of an object into a concurrent implementation of that same object in a linearizable and wait-free manner. Such constructions require underlying low-level universal shared objects such as compare-and-swap and load-linked/store-conditional. In this paper, we present the first universal construction that (a) uses exactly one compare-and-swap object and (b) has time complexity (number of accesses to low-level shared objects) and memory complexity (size of low-level shared objects) that are both independent of the size of the high-level object to be implemented.


Presented at:
NETYS, Agadir, Morocco
Year:
2015
Keywords:
Note:
Best paper award
Laboratories:


Note: The status of this file is: EPFL only


 Record created 2015-06-18, last modified 2018-01-28

External link:
Download fulltext
n/a
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)