The RedBlue family of universal constructions
- PDF / 904,021 Bytes
- 29 Pages / 595.276 x 790.866 pts Page_size
- 19 Downloads / 168 Views
The RedBlue family of universal constructions Panagiota Fatourou1,2 · Nikolaos D. Kallimanis1 Received: 9 January 2016 / Accepted: 26 January 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract A universal construction is a general mechanism for obtaining a concurrent implementation of any shared object from its sequential implementation. We present the family of RedBlue universal constructions which produce adaptive, linearizable, wait-free, concurrent implementations of shared objects. The proposed universal constructions improve upon previous universal constructions in terms of their step and/or space complexity. The first of these universal constructions, which serves as the keystone for the design of the other RedBlue algorithms, produces concurrent implementations with better step complexity than those produced by all previously presented universal constructions but it uses large LL/SC registers. The second universal construction significantly reduces the size of the required registers, whereas the last two are appropriate for the purpose of simulating large objects. Keywords Universal · Wait-free · Linearizable · Shared object · Adaptive · Large object
1 Introduction 1.1 Motivation and contribution A universal construction provides a general mechanism to implement any shared object in an asynchronous system where a number of threads are executed concurrently. We present a family of universal constructions, called RedBlue, which produce wait-free, linearizable implementations of shared objects. An object’s implementation is wait-free [15] if each (non-faulty) thread completes each operation that it initiates on the object within a finite number of its own steps despite the failures or the execution speed of other threads. In shared memory systems, it is often the case that the total number, n, of threads is larger than the actual number, k, of threads that concurrently execute operations on the implemented object. For this reason, a flurry of research
B
Panagiota Fatourou [email protected] Nikolaos D. Kallimanis [email protected]
1
Institute of Computer Science, Foundation for Research and Technology-Hellas, Crete, Greece
2
Department of Computer Science, University of Crete, Crete, Greece
(e.g. [1,2,5,6,17]) has been devoted to the design of adaptive algorithms whose step complexity depends on k, the contention in the system; the step complexity is the maximum number of shared memory accesses performed to apply any operation on the implemented object in any execution. The algorithms of the RedBlue family are adaptive. The RedBlue algorithms use two perfect binary trees of log2 n + 1 levels each. The first tree, which we call the red tree, is employed for estimating the encountered contention, while the second tree, which we call the blue tree, is used for the synchronization with other threads when applying an operation. In each of these trees, a thread is assigned a leaf node (and therefore also a path from this leaf to the root node, or vice versa). A thread that wants
Data Loading...
