A MODULAR DRINKING PHILOSOPHERS ALGORITHM Academic Article

abstract

• 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 with O(1) worst-case waiting time is obtained, whereas the drinking philosophers algorithm of Chandy and Misra has O(n) worst-case waiting time (for n philosophers). Careful definitions are given to distinguish the drinking and dining philosophers problems and to specify varying degrees of concurrency. 1993 Springer-Verlag.

authors

• Welch, Jennifer

published proceedings

• DISTRIBUTED COMPUTING

author list (cited authors)

• WELCH, J. L., & LYNCH, N. A.

citation count

• 21

complete list of authors

• WELCH, JL||LYNCH, NA

publication date

• July 1993

publisher

• Springer Nature  Publisher

published in

• Distributed Computing  Journal

keywords

• Dining Philosophers
• Distributed Algorithms
• Drinking Philosophers
• Modularity
• Resource Allocation

Digital Object Identifier (DOI)

• 10.1007/BF02242711

start page

• 233

end page

• 244

volume

• 6

issue

• 4

URL

• http%3A%2F%2Fdx.doi.org%2F10.1007%2Fbf02242711