On the generalized dining philosophers problem

O. M. Herescu; C. Palamidessi

doi:10.1145/383962.383994

On the generalized dining philosophers problem

O. M. Herescu
, C. Palamidessi

Penn State University

Research output: Contribution to conference › Paper › peer-review

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.

Original language	English
Pages	81-89
Number of pages	9
DOIs	https://doi.org/10.1145/383962.383994
Publication status	Published - 1 Jan 2001
Externally published	Yes
Event	20th Annual ACM Symposium on Principles of Distributed Computing - Newport, Rhode Island, United States Duration: 26 Aug 2001 → 29 Aug 2001

Conference

Conference	20th Annual ACM Symposium on Principles of Distributed Computing
Country/Territory	United States
City	Newport, Rhode Island
Period	26/08/01 → 29/08/01

Access to Document

10.1145/383962.383994

Cite this

@conference{d0bdcc046dd340a69991596afa822cb9,

title = "On the generalized dining philosophers problem",

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.",

author = "Herescu, \{O. M.\} and C. Palamidessi",

year = "2001",

month = jan,

day = "1",

doi = "10.1145/383962.383994",

language = "English",

pages = "81--89",

note = "20th Annual ACM Symposium on Principles of Distributed Computing ; Conference date: 26-08-2001 Through 29-08-2001",

}

TY - CONF

T1 - On the generalized dining philosophers problem

AU - Herescu, O. M.

AU - Palamidessi, C.

PY - 2001/1/1

Y1 - 2001/1/1

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0034777358

U2 - 10.1145/383962.383994

DO - 10.1145/383962.383994

M3 - Paper

AN - SCOPUS:0034777358

SP - 81

EP - 89

T2 - 20th Annual ACM Symposium on Principles of Distributed Computing

Y2 - 26 August 2001 through 29 August 2001

ER -

On the generalized dining philosophers problem

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this