Summary
A variant of the drinking philosophers algorithm of Chandy and Misra is described and proved correct in a modular way. The algorithm of Chandy and Misra is based on a particular dining philosophers algorithm and relies on certain properties of its implementation. The drinking philosophers algorithm presented in this paper is able to use an arbitrary dining philosophers algorithm as a subroutine; nothing about the implementation needs to be known, only that it solves the dining philosophers problem. An important advantage of this modularity is that by substituting a more time-efficient dining philosophers algorithm than the one used by Chandy and Misra, a drinking philosophers algorithm withO(1) worst-case waiting time is obtained, whereas the drinking philosophers algorithm of Chandy and Misra hasO(n) worst-case waiting time (forn philosophers). Careful definitions are given to distinguish the drinking and dining philosophers problems and to specify varying degrees of concurrency.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Awerbuch B, Saks M: A dining philosophers algorithm with polynomial response time. Proc 31st IEEE Symposium on Foundations of Computer Science, pp 65–74 (1990)
Chandy KM, Misra J: The drinking philosophers problem. ACM Trans Program Lang Syst 6 (4):632–646 (1984)
Choy M, Singh AK: Efficient fault-tolerant algorithms for resource allocation in distributed systems. Proc 24th ACM Symp Theo Comput, pp 593–602 (1992)
Dijkstra EW: Hierarchical ordering of sequential processes. Acta Inf 1 (2):115–138 (1971)
Ginat D, Shankar AU, Agrawala AK: An efficient solution to the drinking philosophers problem and its extensions. Proc 3rd International Workshop on Distributed Algorithms. Lect Comput Sci, vol 392. Springer, Berlin Heidelberg New York 1989, pp 83–93
Lehmann D, Rabin M: On the advantages of free choice: a symmetric and fully distributed solution to the dining philosophers problem. Proc 8th ACM Symposium on Principles of Programming Languages, pp 133–138 (1981)
Lynch NA: Upper bounds for static resource allocation in a distributed system. J Comput Syst Sci 23 (2):254–278 (1981)
Lynch NA, Tuttle MR: Hierarchical correctness proofs for distributed algorithms. Proc 6th ACM Symposium on Principles of Distributed Computing, pp 137–151 (1987). (Also available as Technical Report MIT/LCS/TR-387. Laboratory for Computer Science, Massachusetts Institute of Technology, April 1987.)
Murphy SL, Shankar AU: A note on the drinking philosophers problem. ACM Trans Program Lang Syst 10(1):178–188 (1988)
Peterson GL, Fischer MJ: Economical solutions for the critical section problem in a distributed system. Proc 9th ACM Symposium on Theory of Computing, pp 91–97 (1977)
Singh AK: Ranking in distributed systems. Ph.D. dissertation. Department of Computer Sciences, University of Texas at Austin, 1989
Singh AK, Gouda MG: Rankers: a classification of synchronization problems. manuscript
Welch JL: Topics in distributed computing: the impact of partial synchrony, and modular decomposition of algorithms. Ph.D. thesis. Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1988
Welch JL, Lynch NA: Synthesis of efficient drinking philosophers algorithms. Technical Memorandum MIT/LCS/TM-417. Laboratory for Computer Science, Massachusetts Institute of Technology, 1989
Author information
Authors and Affiliations
Additional information
Jennifer L. Welch received her B.A. in 1979 from the University of Texas at Austin, and her S.M. and Ph.D. from the Massachusetts Institute of Technology in 1984 and 1988 respectively. She has been a member of technical staff at GTE Laboratories Incorporated in Waltham, Massachusetts and an assistant professor at the University of North Carolina at Chapel Hill. She is currently an assistant professor at Texas A&M University. Her research interests include algorithms and lower bounds for distributed computing.
Much of this work was performed while this author was at the Laboratory for Computer Science, Massachusetts Institute of Technology, supported by the Advanced Research Projects Agency of the Department of Defense under contract N00014-83-K-0125, the National Science Foundation under grants DCR-83-02391 and CCR-86-11442, the Office of Army Research under contract DAAG29-84-K-0058, and the Office of Naval Research under contract N00014-85-K-0168. This author was also supported in part by NSF grant CCR-9010730, an IBM Faculty Development Award, and NSF Presidential Young Investigator Award CCR-9158478
This author was supported by the Office of Naval Research under contract N00014-91-J-1046, the Advanced Research Projects Agency of the Department of Defense under contract N00014-89-J-1988, and the National Science Foundation under grant CCR-89-15206. The photograph and autobiography of Professor N.A. Lynch were published in Volume 6, No. 2, 1992 on page 121
Rights and permissions
About this article
Cite this article
Welch, J.L., Lynch, N.A. A modular drinking philosophers algorithm. Distrib Comput 6, 233–244 (1993). https://doi.org/10.1007/BF02242711
Received:
Accepted:
Issue date:
DOI: https://doi.org/10.1007/BF02242711