conference paper
A Thrifty Universal Construction
2015
NETYS 2015: Networked Systems
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.
Type
conference paper
Author(s)
Date Issued
2015
Published in
NETYS 2015: Networked Systems
Start page
444
End page
455
Note
Best paper award
Editorial or Peer reviewed
REVIEWED
Written at
EPFL
EPFL units
Event name | Event place |
Agadir, Morocco | |
Use this identifier to reference this record