EFFICIENT FAULT-TOLERANT ALGORITHMS FOR DISTRIBUTED RESOURCE-ALLOCATION

Solutions to resource allocation problems and other related synchronization 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 to the requests of a process; message complexity measures the number of messages sent and received by a process; and failure locality characterizes the size of the network that is affected by the failure of a single process. An algorithm for the resource allocation problem that achieves a constant failure locality of four along with a quadratic response time and a quadratic message complexity is presented. Applications of the algorithm to other process synchronization problems in distributed systems are also demonstrated.