<p>Well, if the philosophers are following the exact same strategy and there is nothing to distinguish them (like who is closest to the door etc.) then they will do exactly the same and deadlock must occur: Whenever one (Aristotle) picks up the left fork then the philosopher on the right (Beauvoir) takes Aristotle's right fork.</p>

<p>If you allow access to a source of randomness this should be easily fixable, however (everyone eats for a short time when possible and waits for a long, random, time thereafter).</p>

CC BY-SA 3.0
2017-11-11T03:58:05.340Z
2017-11-11T03:58:05.340Z
Bjørn Kjos-Hanssen
<p>The <a href="https://en.wikipedia.org/wiki/Dining_philosophers_problem" rel="nofollow noreferrer">wikipedia article for the Dining Philosophers Problem</a> lists some solutions which are dependent on external information, i.e.:</p>

<ol>
<li>Numbering of forks</li>
<li>A waiter to act as mutex</li>
<li>Messaging between philosophers</li>
</ol>

<p>If we restrict the problem to the bare essentials, i.e.:</p>

<ol>
<li>No information encoded in the table/forks</li>
<li>No prior meeting between philosophers, and hence no ordering/numbering</li>
<li>No communication between philosophers at the table</li>
</ol>

<p>Is it provably impossible for every philosopher to have a strategy that avoids deadlock/starvation?  Is there a good understanding of the "minimal" conditions necessary for a solution to exist?</p>

<concurrency><synchronization>
Under what conditions is the Dining Philosophers Problem unsolvable?
donnyton
# Under what conditions is the Dining Philosophers Problem unsolvable?

(Asked by: username_0 on 2017-11-10)

The [wikipedia article for the Dining Philosophers Problem](https://en.wikipedia.org/wiki/Dining_philosophers_problem) lists some solutions which are dependent on external information, i.e.:

1. Numbering of forks
2. A waiter to act as mutex
3. Messaging between philosophers

If we restrict the problem to the bare essentials, i.e.:

1. No information encoded in the table/forks
2. No prior meeting between philosophers, and hence no ordering/numbering
3. No communication between philosophers at the table

Is it provably impossible for every philosopher to have a strategy that avoids deadlock/starvation? Is there a good understanding of the "minimal" conditions necessary for a solution to exist?

**Tags:** concurrency, synchronization

---

## 1 answers

### Answer by username_1 on 2017-11-11. Score: 3

Well, if the philosophers are following the exact same strategy and there is nothing to distinguish them (like who is closest to the door etc.) then they will do exactly the same and deadlock must occur: Whenever one (Aristotle) picks up the left fork then the philosopher on the right (Beauvoir) takes Aristotle's right fork.

If you allow access to a source of randomness this should be easily fixable, however (everyone eats for a short time when possible and waits for a long, random, time thereafter).


---

