@article{lamport1986the,
author = {Lamport, Leslie},
title = {The Mutual Exclusion Problem - Part I: A Theory of Interprocess Communication},
year = {1986},
month = {January},
abstract = {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].)},
url = {https://www.microsoft.com/en-us/research/publication/mutual-exclusion-problem-part-theory-interprocess-communication/},
pages = {313-348},
journal = {Journal of the Association for Computing Machinery},
volume = {33},
number = {2},
}