A dining philosophers algorithm with polynomial response time

The authors present an efficient distributed online algorithm for scheduling jobs that are created dynamically, subject to resource constraints that require that certain pairs of jobs not run concurrently. The focus is on the response time of the system to each job, i.e., the length of the time interval that starts when the job is created or assigned to a processor and ends at the instant the execution of the job begins. The goal is to provide guarantees on the response time to each job j in terms of the density of arrivals of jobs that conflict with j. The model is completely asynchronous and includes various resource allocation problems that have been studied extensively, including the dining philosophers problem and its generalizations to arbitrary networks. In these versions of the problem, the resource requirements of each new job j determines an upper bound δ_j on the number of jobs that can exist concurrently in the system and conflict with j. It is easy to show that given such upper bounds, no scheduling algorithm can guarantee a response time better than δ_j (times the maximum execution or message transmission time). A simple algorithm that guarantees response time that is essentially polynomial in δ_j is presented. It is based on the notion of a distributed queue and has a compact implementation.