Mutual Exclusion in Asynchronous Systems with Failure Detectors

This paper defines the fault-tolerant mutual exclusion problem in a message-passing asynchronous system and determines the weakest failure detector to solve the problem. This failure detector, which we call the trusting failure detector, and which we denote by T, is strictly weaker than the perfect failure detector P but strictly stronger than the eventually perfect failure detector P. The paper shows that a majority of correct processes is necessary to solve the problem with T. Moreover, T is also the weakest failure detector to solve the fault-tolerant group mutual exclusion problem.

Related material