CaltechAUTHORS
  A Caltech Library Service

The drinking philosophers problem

Chandy, K. M. and Misra, J. (1984) The drinking philosophers problem. ACM Transactions on Programming Languages and Systems (TOPLAS), 6 (4). pp. 632-646. ISSN 0164-0925. https://resolver.caltech.edu/CaltechAUTHORS:20190111-153432743

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190111-153432743

Abstract

The problem of resolving conflicts between processes in distributed systems is of practical importance. A conflict between a set of processes must be resolved in favor of some (usually one) process and against the others: a favored process must have some property that distinguishes it from others. To guarantee fairness, the distinguishing property must be such that the process selected for favorable treatment is not always the same. A distributed implementation of an acyclic precedence graph, in which the depth of a process (the longest chain of predecessors) is a distinguishing property, is presented. A simple conflict resolution rule coupled with the acyclic graph ensures fair resolution of all conflicts. To make the problem concrete, two paradigms are presented: the well-known distributed dining philosophers problem and a generalization of it, the distributed drinking philosophers problem.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1145/1780.1804DOIArticle
Additional Information:© 1984 ACM. Received May 1983; revised February 1984; accepted May 1984. Lecture notes in computer science Vol. 174. This work was supported by the Air Force Office of Scientific Research under grant AFOSR 81-0205. We thank W.H.J. Feijen and A.J.M. Van Gasteren of Eindhoven University of Technology and Greg Andrews of the University of Arizona for their detailed comments. We are grateful to three unknown referees and to Susan Graham for detailed comments. Conversations with E.W. Dijkstra on this problem were most helpful.
Funders:
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)81-0205
Subject Keywords:Asymmetry, dining philosophers problem
Issue or Number:4
Record Number:CaltechAUTHORS:20190111-153432743
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190111-153432743
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:92227
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:12 Jan 2019 05:56
Last Modified:03 Oct 2019 20:42

Repository Staff Only: item control page