An Analysis of Rabin's Randomized Mutual Exclusion Algorithm: Preliminary Report

Abstract

In 1982, Michael Rabin published a randomized distributed algorithm implementing mutual exclusion for n processes using a read-modify-write primitive on a shared variable with O(log n) values. He claimed that this algorithm satisfied the following informally-stated strong probabilistic no-lockout property. Define the adversary to be the entity controlling the order in which processes take steps; then, for every adversary, any process competing for entrance to the critical section succeeds with probability Ω(1/m), where m is the number of competing processes. In this paper we consider several different ways in which this property can be expressed formally. We express explicitly the dependency of the probability on the adversary and show that this dependency is so strong that the algorithm does not satisfy any of these conditions. In fact, the algorithm does not even satisfya much weaker Ω(1/n) property.