Under what conditions is the Dining Philosophers Problem unsolvable? The wikipedia article for the Dining Philosophers Problem lists some solutions which are dependent on external information, i.e.:


Numbering of forks
A waiter to act as mutex
Messaging between philosophers


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


No information encoded in the table/forks
No prior meeting between philosophers, and hence no ordering/numbering
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?
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).