Download now Free registration required
Mutual exclusion is not solvable in an asynchronous message-passing system where processes are subject to crash failures. Delporte-Gallet et.al. determined the weakest failure detector to solve this problem when a majority of processes are correct. Here the authors identify the weakest failure detector to solve mutual exclusion in any environment, i.e., regardless of the number of faulty processes. They also show a relation between mutual exclusion and consensus, arguably the two most fundamental problems in distributed computing. Specifically, they show that a failure detector that solves mutual exclusion is sufficient to solve non-uniform consensus but not necessarily uniform consensus.
- Format: PDF
- Size: 188.4 KB