5
$\begingroup$

In a question on Stack Overflow, the answer by Patrick Trentin lists the following solution to the dining philosopher's problem:

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

$\endgroup$
  • 1
    $\begingroup$ Coffman in 1971 wrote about four simultaneous conditions for deadlock - if you break at least one of them - it is like tie breaker. With alteuist there is no more circular wait and your system become preemptive. $\endgroup$ – Evil Jul 14 '16 at 5:27
  • $\begingroup$ A formal proof can be quite tedious, see for example cs.stackexchange.com/questions/45763/… The techniques are similar here, try proving this yourself. If you are still stuck, i will try to add a proof later, but see the linked post to realize what you are asking (and don't be disappointed if the proof is full of indexes and doesn't give you any special insight, "formal" proofs for the correctness of even supposedly trivial concurrent protocols might surprise you). $\endgroup$ – Ariel Jul 14 '16 at 15:47
  • $\begingroup$ The word formal appears in quotation since treating concurrent algorithms formally is an entire field, and one must define precisely all the basic notions (e.g. how is time represented). $\endgroup$ – Ariel Jul 14 '16 at 15:50
  • $\begingroup$ @Ariel Then I will settle for knowledge that a proof or falsification of the validity of the solution exists. :) $\endgroup$ – Akshat Mahajan Jul 14 '16 at 16:25

Your Answer

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

Browse other questions tagged or ask your own question.