On Linearizability and the Termination of Randomized Algorithms
On Linearizability and the Termination of Randomized Algorithms
We study the question of whether the "termination with probability 1" property of a randomized algorithm is preserved when one replaces the atomic registers that the algorithm uses with linearizable (implementations of) registers. We show that in general this is not so: roughly speaking, every randomized algorithm A has a …