Randomized Dining Philosophers without Fairness Assumption
Marie Duflot, Laurent Fribourg, Claudine Picaronny · 2002
We consider Lehmann-Rabin’s randomized solution to the well-known problem of the dining philosophers. Up to now, such an analysis has always required a “fairness” assumption on the scheduler: if a philosopher is continuously hungry then he must eventually be scheduled. In contrast here, we modify the algorithm in order to get rid of the fairness assumption. We claim that the spirit of the original algorithm is preserved. We prove that, for any (possibly unfair) scheduler, the modified algorithm converges: every computation reaches with probability 1 a configuration where some philosopher eats. Furthermore, we are now able to evaluate the expected time of convergence as a number of transitions. We show that, for some “malicious” scheduler, this expected time is at least exponential in the number N of philosophers. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.