3
$\begingroup$

The wikipedia article for the 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?

$\endgroup$
3
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.