Series: Logic Seminar

Date: Tuesday, October 26, 1999

Speaker: Mihaela Herescu (Penn State, Computer Science)

Title: A Symmetric and Fully Distributed Solution to the Dining
Philosophers Problem

Time: 2:30 - 3:20 PM

Place: 122 Thomas Building

Abstract: 

The classical problem of the dining philosophers, proposed by
E. Dijkstra, is a paradigm for a large class of concurrency control
problems.  D.Lehmann and M.O.Rabin showed that there is no
deterministic, truly distributed and symmetric solution to the dining
philosophers that will guarantee the absence of deadlock.  The fully
distributed solution proposed by Lehmann and Rabin is based on
randomized choice for the philosophers, and guarantes that every
hungry philosopher will eat, with probability 1, under any
circumstances (even under an adversary scheduler).