Title
On the generalized dining philosophers problem
Authors
Oltea Mihaela Herescu and Catuscia Palamidessi
Abstract
We consider a generalization of the dining
philosophers problem to arbitrary connection topologies. We
focus on symmetric, fully distributed systems, and we address
the problem of guaranteeing progress and lockout-freedom,
even in presence of adversary schedulers, by
using randomized algorithms. We show that the well-known
algorithms of Lehmann and Rabin do not work in the generalized
case, and we propose an alternative algorithm based on the idea of
letting the philosophers assign a random priority to their
adjacent forks.