# What is the formal statement of the dining philosopher's problem?

I've read about it in a few places and I'm not sure I get it. Are the philosopher's allowed to act simultaneously? Do they each take 1 action simultaneously, then go on to their next action?

• It's up to you (or whoever tasked you with the problem) to define what actions the philosophers have at their disposal. The problem is an educational device. For a bit of history, check EW Dijkstra's papers on the topic. You can search his archive.
– Kai
Nov 30 '18 at 10:30

## 2 Answers

In most models of concurrency, each participant performs one elementary action at a time. This applies both to philosophers and to forks. So if two philosophers try to grab the same fork around the same time, one of them will make the attempt first.

Concurrency models usually do not have a global time, so there is no concept of actions happening “at the same time” if they don't involve the same object. Each participants sees events according to its own notion of time. If an action happens which doesn't involve a particular participant, that participant only learns about it later when it receives some message informing it that the action has taken place.

Think of the participants as nodes in a network (which they often are). If two actions happen on different nodes, it doesn't matter whether they're “exactly” simultaneous. And physically speaking, they wouldn't be exactly simultaneous: without perfectly synchronized clocks, there's always some slight measurement error or reaction delay that means that you can't distinguish perfectly simultaneous actions from actions that happened within an extremely small time frame.

Each philospher decides to pick up and set down forks at their own pace. One philosopher may pick up a fork, eat and set it down before his neighbor has lifted a finger. Or they may race for the same fork, but only one of them will manage to grab it. Meanwhile the other philosophers are doing whatever they please.

Having one timeline per participant, rather than a global timeline, both simplifies the model and makes it closer to the reality of most concurrent systems. The model is simpler because there's never any reason to treat actions as simultaneous, and never any reason to care about the exact order of actions happening in different places. It's closer to the reality of concurrent processes and distributed systems because each thread or each network node does have its own perception of when actions take place.

An exception is the modeling of circuits where all actions happen on a clock cycle. This is one of the fundamental ways in which parallelism differs from concurrency. In a circuit, it often does make a difference that two actions happen at different parts of the system on the same clock cycle (e.g. two inputs change simultaneously), rather than on distinct clock cycles.

Having the philosophers act simultaneously (like if two of them try to pick up the same fork at the same time) would potentially make the d.p.p. even worse.

But with the "bad" algorithm presented on Wikipedia, if all philosophers pick up the fork on their left, at times $$t_1,\dots,t_5$$, then we have deadlock no matter what the times $$t_i$$ are.