Bipartite Double-Word Compare-and-Swap

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.