Localizing Failures in Distributed Synchronization

We investigate the fault-tolerance of distributed algorithms in asynchronousmessage passing systems with undetectable process failures. We introducefailure locality as a measure of the fault-tolerance of distributedalgorithms. This measure captures the general idea of allowing part of asystem to continue to function despite the failure of other parts of thesystem. We concentrate on two problems, the dining philosophers problem andthe committee coordination problem, and present algorithms with an optimalfailure locality.