View Related Documents

Abstract

We consider Lehmann-Rabinrsquos randomized solution to the well-known problem of the dining philosophers. Up to now, such an analysis has always required a ldquofairnessrdquo 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 ldquomaliciousrdquo scheduling, this expected time is at least exponential in the number N of philosophers.
Received: 14 June 2002, Accepted: 1 October 2003, Published online: 6 February 2004
This paper is a revised and extended version of a communication given by the same authors, at 2nd IFIP Int. Conf. on Theoretical Computer Science (TCS@2002).

Fulltext Preview

Image of the first page of the fulltext document