Several algorithms reducing the number of messages were presented later (see Ricart and Agrawala [21] and Carvalho and Roucairol [4]). The number of messages was proportional to N. The algorithm presented by Chandy and Misra [6] (in which permission is in the form of a fork) is the most efficient of the three in terms of message complexity per resource. Maekawa [19] introduced the notion of arbitraring process. A process wishing resource access must obtain permission from a fixed set of ͙N arbitraring processes. Each arbitraring process gives permission on behalf of itself and (͙N Ϫ 1) other processes. The amortized message complexity of this algorithm is 3(͙N Ϫ 1).
In this paper, we present an algorithm which relies on a new approach. Every process i maintains two pointers, ''father'' and ''next,'' at any time; the pointer ''father'' indicates the process to which requests for critical section access should be forwarded, and the pointer ''next'' indicates the node to which access permission should be forwarded after process i leaves its critical section. The key point of the algorithm is a very simple dynamic scheme for updating the pointers while processing a sequence of requests.
This paper is organized as follows: In Section 2, we introduce the algorithm; in Section 3, we prove its correctness; and in Section 4, we compute its complexity.
MODEL DESCRIPTION AND SPECIFICATION OF THE ALGORITHM
2.1. General Model
Each process has a local memory and can send messages to any other by using a unique identifier as an address. The communication between processes is assured to be perfect (no losses, duplications, or modifications of messages).
2.2. Description
The algorithm we present here is based on the fact that a process sends its request to only one other process and awaits its permission.
It would be a centralized algorithm if the receiving process were always the same, but the receiving process will change at every request.