On the Time Complexity of the Dining Philosophers Problem

A tight bound on the response time for the dining philosophers problem in distributed systems is obtained. Also shown is that any (distributed) dining philosophers algorithm with the optimal response time is transformable in polynomial time into a sequential algorithm for an NP-complete problem. It suggests that an execution of any dining philosophers algorithm with the optimal response time may require a large (perhaps exponential) amount of local computation in acquiring resources.

PS COPY