A resilient mutual exclusion algorithm for computer networks

The authors present an extension to the work of I. Suzuki and T. Kasami (see Proc. 3rd Int. Conf. Distributed Compact Syst., p.365-70 (1982)), where a mutual exclusion algorithm uses a message called a token to transfer the privilege of entering a critical region among the participating sites. The proposed algorithm checks whether the token is lost during network failure, and regenerates it if necessary. The mutual exclusion requirement is satisfied by guaranteeing regeneration of only one token in the network. Failures in a computer network are classified into three types: processor failure, communication controller failure, and communication link failure. To detect failures, a time-out mechanism based on message delay is used. The execution of the algorithm is described for each type of failure; each site follows a rather simple execution procedure. Each site is not required to observe the failure of other sites or communication links