Randomized dining philosophers without fairness assumption

摘要

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 scheduling mechanism: if a philosopher is continuously hungry then he must eventually be scheduled. In contrast, we modify here the algorithm in order to get rid of the fairness assumption, and we claim that the spirit of the original algorithm is preserved. We prove that, for any (possibly unfair) scheduling, 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 in terms of the number of transitions. We show that, for some malicious scheduling, this expected time is at least exponential in the number N of philosophers.