Bipartite Double-Word Compare-and-Swap
Date
2020-11-27
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Multi-word compare-and-swap operations have always been in demand and have applications in several complex distributed data structures [5,10]. These operations are not offered by any modern architectures, so researchers have to implement their own versions of them using the primitives that are available in hardware. In this research, we implement a lock-free linearizable bipartite double-word compare-and-swap operation. This operation can be used on its own as a restricted version of the double-word compare-and-swap operation. However, the most significant feature of our algorithm is that our design has the potential to be expanded to implement an expected wait-free double-word compare-and-swap operation with sub-linear step complexity. To the best of our knowledge, this is the first result of this kind that achieves sub-linear step complexity.
Description
Keywords
Distributed Algorithms, Compare-and-Swap, Double Compare-and-Swap, Lock-free
Citation
Jafarigiv, M. (2020). Bipartite Double-Word Compare-and-Swap (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.