Series: Penn State Logic Seminar

Date: Tuesday, November 28, 2000

Time: 2:30 - 3:20 PM

Place: 307 Boucke Building

Speaker: Catuscia Palamidessi, Computer Science, Penn State

Title: How to rescue the dining philosophers from starvation in case
of overbooking

ABSTRACT: In this talk I present joint work with Mihaela Herescu.
Consider a generalization of the dining philosophers problem where the
number of philosophers can exceed the number of forks.  Will the
classic algorithm of Lehman and Rabin still work in this situation?
We show that the answer is "No": in some cases, a malicious scheduler
can induce a livelock (all philophers will starve).  We then show a
randomized solution, essentially different from the one of Lehman and
Rabin, which works for any number of "overbooked" philosophers and in
a fully distributed, symmetric way. Our solution guarrantees deadlock
freedom, livelock freedom and lockout freedom (no philosophers will
starve), with probability 1.