Mutual exclusion deals with the problem of not having more than one process at a time using a section of code (specifically, a critical section). If there are n distributed processes that can ask to use a critical section of code, it is well known that a fair deterministic algorithm requires an &Ohm; ( n )-bit shared variable. This paper shows that the previously known &Ohm; (loglogn ) bits that are required for a fair randomized algorithm are a tight bound.

The number of bits required in mutual exclusion solutions depends on the fairness criteria used. Without any fairness criteria, one bit is sufficient to enforce mutual exclusion (that is, that the program is deadlock-free). For a deterministic solution, if bounded waiting is the fairness criterion, then an &Ohm; ( n )-bit shared variable is required.

For a randomized algorithm, fairness needs to be defined differently. If fairness is linear fairness, which means that the probability of a given process entering the critical section next is &Ohm; ( 1&slash;m ), when m processes are currently trying to enter the critical section, this paper proves that no fewer than &Ohm; (loglogn ) bits will do.

Interestingly, however, if a slightly weaker fairness criterion is used, namely that the probability of any process being chosen is &Ohm; ( 1&slash;m^{( 1 + &egr; )}), &egr; > 0, then an &Ohm; (logloglogn )-bit shared variable is sufficient. The authors also show that, with a constant-size variable, it is possible to guarantee an &Ohm; ( ½^m ) probability of entering the critical section.

To prove these results, a Markov chain analysis is used. This is possible because of the definition of the fairness rules in the probabilistic cases, which depend only on the current state (that is, only on how many processes are currently vying for entry into the critical section).

This important paper furthers our understanding of randomized algorithms, the limits on the number of bits necessary for mutual exclusion, and the application of Markov chains to the analysis of randomized algorithms.