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).
Mathematical Logic at Penn State
Department of Mathematics