Synthesis of Efficient Drinking Philosophers Algorithms

Abstract

A variant of the drinking philosophers algorithm of Chandy and Misra is described and proved correct in a modular way, using the I/O automation model of Lynch and Tuttle. 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 true 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). Formal definitions are given to distinguish the drinking and dining philosophers problems and to specify precise varying degrees of concurrency.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1989
Accession Number
ADA216390

Entities

People

  • Jennifer A. Welch
  • Nancy Lynch

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • C4I
  • Cyber
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Classification
  • Computer Science
  • Computers
  • Contracts
  • Digestive System Processes
  • Information Processing
  • Information Systems
  • Military Research
  • Multithreading
  • Numbers
  • Procedures (Computers)
  • Real Numbers
  • Sequences
  • Theoretical Computer Science

Readers

  • Educational Psychology
  • Industrial Economics
  • Parallel and Distributed Computing.