On the generalized dining philosophers problem

DOI10.1145/383962.383994MaRDI QIDQ2787669zbMATH OpenOpenAlexFDO

Authors Oltea Mihaela Herescu, Catuscia Palamidessi

Publication date 4 March 2016

Published in Proceedings of the twentieth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0109003

Mathematics Subject Classification ID

Randomized algorithms (68W20) Distributed algorithms (68W15) Distributed systems (68M14)

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.

Recommendations

• scientific article; zbMATH DE number 4039953
• An optimal distributed solution to the dining philosphers problem
• Randomized dining philosophers without fairness assumption
• A distributed self-stabilizing solution to the dining philosophers problem
• Categorial Semantics of a Solution to Distributed Dining Philosophers Problem
• On Bellman's and Knuth's problems and their generalizations
• Publication:3027633
• scientific article; zbMATH DE number 4034376
• The generalized assignment problem
• scientific article; zbMATH DE number 3918100

Cited in

(13)

• Cloud conveyors system: a versatile application for exploring cyber-physical systems
• The philosophers' process: An ergodic reversible nearest particle system
• A modular drinking philosophers algorithm
• An optimal distributed solution to the dining philosphers problem
• A priority dynamics for generalized drinking philosophers
• A randomized encoding of the \(\pi\)-calculus with mixed choice
• Sharing resources at nonuniform access rates
• Wait-Free Dining Under Eventual Weak Exclusion
• The Driving Philosophers
• Randomized dining philosophers without fairness assumption
• A distributed self-stabilizing solution to the dining philosophers problem
• scientific article; zbMATH DE number 4039953 (Why is no real title available?)
• scientific article; zbMATH DE number 4043213 (Why is no real title available?)

This page was built for publication: On the generalized dining philosophers problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2787669)