A modular drinking philosophers algorithm

DOI10.1007/BF02242711MaRDI QIDQ1261112zbMATH OpenOpenAlexFDO

Authors Jennifer L. Welch, Nancy Lynch

Publication date 16 September 1993

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02242711

zbMATH Keywords

allocationconcurrencydining philosophersdrinking philosophers

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Review text

A variant of the drinking philosophers algorithm of Chandy and Misra is described and proved correct in a modular way. The algorithm uses an arbitrary dining philosophers algorithm as a subroutine. For \(O(1)\) time subroutine, the worst-case waiting time of the presented algorithms is shown to be \(O(1)\). Definitions that distinguish the drinking and dining philosophers problem and that specify varying degrees of concurrency are provided.

Recommendations

• scientific article; zbMATH DE number 4064453
• A priority dynamics for generalized drinking philosophers
• An optimal distributed solution to the dining philosphers problem
• On the generalized dining philosophers problem
• Randomized dining philosophers without fairness assumption

Cites work

• scientific article; zbMATH DE number 4064453 (Why is no real title available?)
• Rankers: A classification of synchronization problems
• Upper bounds for static resource allocation in a distributed system

Cited in

(5)

• A priority dynamics for generalized drinking philosophers
• Dynamic input/output automata: a formal and compositional model for dynamic systems
• A distributed resource allocation algorithm for many processes
• scientific article; zbMATH DE number 4064453 (Why is no real title available?)
• From drinking philosophers to asynchronous path-following robots

This page was built for publication: A modular drinking philosophers algorithm

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