A dining philosophers algorithm with polynomial response time

Baruch Awerbuch, Michael Saks

Research output: Contribution to journalConference articlepeer-review

30 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)65-74
Number of pages10
JournalIEEE Transactions on Industry Applications
Issue number1 pt 1
StatePublished - Jan 1991
Externally publishedYes
Event1989 Industry Applications Society Annual Meeting - San Diego, CA, USA
Duration: Oct 1 1989Oct 5 1989

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Industrial and Manufacturing Engineering
  • Electrical and Electronic Engineering


Dive into the research topics of 'A dining philosophers algorithm with polynomial response time'. Together they form a unique fingerprint.

Cite this