A possible approach for avoiding deadlock without incurring starvation is to introduce the concept of altruistic philosopher, that is a philosopher which drops the fork that it holds when it realises that he can not eat because the other fork is already used.
Having just one altruistic philosopher is sufficient in order to avoid deadlock, and thus all other philosophers can continue being greedy and attempt to grab as many forks as possible.
However, if you never change who is the altruistic philosopher during your execution, then you might end up with that guy starving himself to death. Thus, the solution is to change the altruistic philosopher infinitely often. A fair strategy is to change it in a round robin fashion each time that one philosopher acts altruistically. In that way, no philosopher is penalised and you can actually verify that no philosopher starves under the fairness condition that the scheduler gives a chance to every philosopher to execute infinitely often.
I was intrigued by this solution because I hadn't heard it before. However, I can find no references to it anywhere in the existing literature.
- I did a quick check, and saw that it isn't listed on Wikipedia as a standard solution.
- Googling 'altruistic philosopher dining' yields only one result from Google Books that does not discuss the round robin strategy and only vaguely alludes to the altruistic philosopher to talk about the perils of starvation.
- I tried looking up altruistic philosopher on ArXiv, only to return no results.
- Trentin cites a book about nuXmv, a symbolic model checker, as his source but only provides a link to his own lab slides.
So my question: does this naive yet seemingly remarkable solution actually work? Or are there pitfalls that have been overlooked? I find it hard to believe that, if it works, it wouldn't have at least some mention somewhere - but at the same time I can't see why it wouldn't work, as it's a fairly naive solution.
If it does work, can I either a) have a reference to a proof, or b) an actual proof that this solves the dining philosopher's problem? If it doesn't, same standards apply, except for the negation of a proof. :)