Two philosophers A and B, two forks numbered "1", "2"; A needs both "1" and "2" for eating, so does B.

Is this theoretical a dining philosopher problem? I'm questioning about the forks philosopher A needs all come from B. However, the DP problem usually gives an example of 5 philosophers, in which case, for example, philosophers A requests 2 forks from two different neighbors.


Short answer: yes, though it could be considered a "degenerate case" (that is, a case that ends up being somewhat different from most others).

Long answer: the Dining Philosophers problem is really about having $n$ philosophers, and coming up with an algorithm that works for any $n$. A good algorithm should work for even "degenerate cases" like zero philosophers or one philosopher—by hard-coding them if necessary ("if there's only one philosopher, eat whenever you feel like"). So $n=2$ is a perfectly valid Dining Philosophers problem.

  • $\begingroup$ I still can't treat n = 2 as a Dining Philosopher. Consider when n = 2, you can easily allow one philosopher to pick up 2 forks once(not one by one) to solve this problem; however, when it comes to Dining Philosopher, the circumstance gets complicated so that we figure out three ways 1. resource hierarchy 2.arbitrator and 3.Chandy/Misra to solve dining. I mean not because of this problem(n=2) but the Dining Philosopher problem make the scientists conclude the three solutions above. $\endgroup$ Jan 3 '19 at 8:21
  • $\begingroup$ @asapdiablo That's why it's considered a degenerate case. It's not as interesting as with higher $n$, but it's still a dining philosopher problem. It's like how sorting two elements is still a list-sorting problem, it's just a trivially easy one. $\endgroup$
    – Draconis
    Jan 3 '19 at 17:05
  • $\begingroup$ Fine, you've persuaded me $\endgroup$ Jan 4 '19 at 1:04
  • $\begingroup$ In fact, 2-philosophers problem is not degenerate at all in the sense that it can go into deadlock. Allowing each philosopher "to pick up 2 forks once (not one by one)" is a solution to all Dining Philosopher problems whether there are 3, 4, 5 or more philosophers. (It is a solution that cannot be implemented in general, though.) $\endgroup$
    – John L.
    Jan 4 '19 at 5:24

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.