EFFICIENT FAULT-TOLERANT ALGORITHMS FOR DISTRIBUTED RESOURCE-ALLOCATION

Solutions to resource allocation problems and other related synchroniz ation problems in distributed systems are examined with respect to the measures of response tame, message complexity, and failure locality. Response time measures the time it takes for an algorithm to respond t o the requests of a process; message complexity measures the number of messages sent and received by a process; and failure locality charact erizes the size of the network that is affected by the failure of a si ngle process. An algorithm for the resource allocation problem that ac hieves a constant failure locality of four along with a quadratic resp onse time and a quadratic message complexity is presented. Application s of the algorithm to other process synchronization problems in distri buted systems are also demonstrated.