%T The Weakest Failure Detector to Solve Mutual Exclusion
%A Vibhor Bhatt
%A Nicholas Christman
%A Prasad Jayanti
%R Technical Report TR2008-618
%I Dartmouth College, Computer Science
%C Hanover, NH
%D April 2008
%U http://www.cs.dartmouth.edu/reports/TR2008-618.pdf
%X
 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 we identify the weakest failure
 detector to solve mutual exclusion in any environment, i.e.,
 regardless of the number of faulty processes. 
     We also show a relation between mutual exclusion and
 consensus, arguably the two most fundamental problems in
 distributed computing. Specifically, we show that a failure
 detector that solves mutual exclusion is sufficient to solve
 non-uniform consensus but not necessarily uniform consensus.