Mutual Exclusion in Asynchronous Systems with Failure Detectors

http://authors.elsevier.com/sd/article/S0743731504002230This paper considers the fault-tolerant mutual exclusion problem in a message-passing asynchronous system and determines the weakest failure detector to solve the problem, given a majority of correct processes. This failure detector, which we call the trusting failure detector, and which we denote by , is strictly weaker than the perfect failure detector but strictly stronger than the eventually perfect failure detector . The paper shows that a majority of correct processes is necessary to solve the problem with . Moreover, is also the weakest failure detector to solve the fault-tolerant group mutual exclusion problem, given a majority of correct processes