On Register Linearizability and Termination
Vassos Hadzilacos, Xing Hu, Sam Toueg · 2021
It is well-known that, for deterministic algorithms, linearizable objects can be used as if they were atomic objects. As pointed out by Golab, Higham, and Woelfel, however, a randomized algorithm that works with atomic objects may lose some of its properties if we replace the atomic objects that it uses with objects that are only linearizable. It was not known whether the properties that can be lost include the all-important property of termination (with probability 1). In this paper, we first show that a randomized algorithm can indeed lose its termination property if we replace the atomic registers that it uses with linearizable ones.