A Fast Distributed Modular Algorithm for Resource Allocation

This paper concerns resource allocation in distributed message passing systems, i.e., the scheduling of accesses to system resources shared among concurrent processes. It presents an efficient modular resource allocation algorithm that uses any arbitrary resource allocation algorithm as a subroutine. It improves the performance of the subroutine by letting each process wait only for its currently conflicting processes, and therefore, allows more concurrency. For appropriate choices of the subroutine, we obtain the fastest known resource allocation algorithms in terms of the worst case response time. Simulation studies were conducted which also indicate that on average, our algorithms perform faster and require a smaller number of messages than other previously known algorithms, especially when resource contention among processes is high and the average time that a process remains in the critical region is large.

Index: Distributed Algorithm, Dining Philosophers, Resource Allocation and Scheduling, Modular Construction, Concurrency, Response Time, Message Passing Distributed Systems.

PS COPY