This paper presents an algorithm with which to achieve mutual exclusion in distributed systems, which the author claims has better performance characteristics than the algorithm of Suzuki and Kasami [1]. The algorithm uses state information that each site maintains about the other sites in the system. The state information is used to deduce from a subset of sites which site is likely to have the token required to enter the critical section (CS). The algorithm sends token request messages to this subset only rather than to all the sites when entering the CS. Consequently, the number of messages exchanged for a critical section invocation is a number between 0 and n. The author argues that this algorithm achieves mutual exclusion while being free of deadlock and starvation.

The author claims that the proposed algorithm demonstrates that heuristic techniques can be advantageously applied to handle uncertainty in systems that must satisfy strong and sharply defined constraints. The author believes that in other problem domains that have sharply defined constraints, similar heuristics can be effectively applied. Clearly, similar heuristic techniques are used in problem domains in AI in which the uncertainty of state information is common, and some strong constraint is often required for the problem to be solved. Numerous examples can be found in the AI literature.

The paper is complete in its presentation and discussion of implementing the algorithm in real systems. It also discusses at length the issues of site crash, communication medium failure, and recovery.

One must carefully examine the extra overhead required to improve on the Suzuki-Kasami algorithm with the simple heuristic. When traffic of CS requests is low to medium, the performance of the proposed algorithm is better than that of the Suzuki-Kasami algorithm. However, the performance degrades as the traffic of CS requests increases. At the extreme, the performance is comparable to that of the Suzuki-Kasami algorithm because the performance of the heuristic is diminished. This occurs because the system state changes at a much faster pace than can be disseminated. One disadvantage is that additional state information must be maintained for the heuristic.