The theory developed in Part I is used to state the mutual exclusion problem and several additional fairness and failure-tolerance requirements. Four “distributed” N-process solutions are given, ranging from a solution requiring only one communication bit per process that permits individual starvation, to one requiring about N] communications bit per process that satisfies every reasonable fairness and failure-tolerance requirement that we can conceive of.

--From the Author’s Abstract

This paper not only demonstrates the adequacy of the theory presented in its companion paper (see the previous review, Rev. 8704-0279) for expressing and proving many correctness (including robustness and fairness) properties of parallel programs with nonatomic reads and writes, but does so by proving the correctness of new and interesting mutual exclusion algorithms. These algorithms are interesting not only because of their nonatomic operations, but also because of their robustness. In particular, all of the algorithms are “fail-safe”; i.e., they will satisfy their respective “correctness properties” even if one of the processes temporarily sets one of its communication variables to arbitrary values, but then resumes normal execution in its noncritical section. Mutual exclusion algorithms such as the ones given in [1] are not fail-safe in this sense (although, unlike Lamport’s algorithms, they are proven resilient under an infinite number of “shut-downs”).

The algorithms are also interesting because they supply the number of bits sufficient to satisfy a set of correctness conditions with nonatomic reads and writes. For example, the algorithm (on p. 34) that is deadlock-free and lockout-free takes three bits per process (i.e., 8n values) while the algorithm in [2] (see p. 192), which uses a powerful test-and-set operation, takes [n/2] + 9 values. (Peterson [3] presents a deadlock-free and lockout-free algorithm with nonatomic operations that uses only 4n values, but is not proven to be as robust as Lamport’s algorithm.)

Through his two papers, Lamport presents a unique and interesting approach to modeling the execution of parallel programs, and he provides insights into the notion of mutual exclusion. The papers are highly recommended to anyone interested in parallel computation.