Strongly linearizable implementations
Maryam Helmi, Lisa Highám, Philipp Woelfel · 2012
Herlihy and Wing [11] established that the set of possible outcomes of a shared memory distributed algorithm remains unchanged when atomic objects are replaced by their linearizable implementations. Since then, linearizability has been the correctness condition of choice for distributed algorithm designers. In 2011, however, Golab, Higham and Woelfel [9] showed that, if an algorithm employs randomization, then the probability distribution over the set of possible outcomes can differ between the atomic and implemented versions. They also proved that a stronger condition, called strong linearizability, is necessary and sufficient to guarantee the same probability distributions for these two cases when the randomized algorithm is under the control of an adaptive adversary. Therefore, we are motivated to construct strongly linearizable implementations of common distributed objects whenever possible. In this paper we prove