The Mutual Exclusion Problem – Part I: A Theory of Interprocess Communication

For some time I had been looking for a mutual exclusion algorithm that satisfied my complete list of desirable properties. I finally found one–the N!-bit algorithm described in this paper. The algorithm is wildly impractical, requiring N! bits of storage for N processors, but practicality was not one of my requirements. So, I decided to publish a compendium of everything I knew about the theory of mutual exclusion.

The 3-bit algorithm described in this paper came about because of a visit by Michael Rabin. He is an advocate of probabilistic algorithms, and he claimed that a probabilistic solution to the mutual exclusion problem would be better than a deterministic one. I believe that it was during his brief visit that we came up with a probabilistic algorithm requiring just three bits of storage per processor. Probabilistic algorithms don’t appeal to me. (This is a question of aesthetics, not practicality.) So later, I figured out how to remove the probability and turn it into a deterministic algorithm.

The first part of the paper covers the formalism for describing nonatomic operations that I had been developing since the 70s, and that is needed for a rigorous exposition of mutual exclusion. (See the discussion of [70].)