From: rolfe@dsuvax.dsu.edu (Tim Rolfe)
Subject: Summary:  Dining Philosophers origins
Summary: First papers posing the problem referenced
Keywords: deadlock, operating systems, deadly embrace, dining philosophers
Organization: Dakota State University
Date: Thu, 9 Apr 1992 15:05:11 GMT

In article <1992Mar23.163607.23249@dsuvax.dsu.edu> I wrote:
>Has anyone read Dijkstra's original paper posing the Dining
>Philosophers' Problem?  If so, may I please have the reference.  If you
>quote "Co-operating Sequential Process," in Programming Languages,
>Genuys, F. (ed.), please give me exact page number.  I got that
>reference by inter-library loan and cannot find the problem in there.
>That IS the paper in which Dijkstra discusses semaphores, and it does
>have the sleepy barber and the banker's algorithm, but I can't find the
>philosophers anywhere in it.

I would like to thank the following persons for their responses to my
query:

Andy Tanenbaum <ast@cs.vu.nl>
Brian Mark Carlson <bmc@white.toronto.edu>
Jon Allen Boone <jb3o+@andrew.cmu.edu>
chaim@cimco.com (Chaim Frenkel)
dboyce@hemel.bull.co.uk (David Boyce)
edski@phx.mcd.mot.com (Ed Skinner)
hemmendd@athena.union.edu (David Hemmendinger)
jsm@elc1.dina.kvl.dk ("J. Steensgaard")
ouij@triples.Math.McGill.CA (Luigi Perrotta)
szhang@galois.UVic.CA (Shujian  Zhang)

Based on their responses I have been able to prepare the following short
annotated bibliography:

     Earliest references suggest that the problem was published
     first by E. W. Dijkstra in

E. W. Dijkstra, "Hierarchical Ordering of Sequential Processes",
_Acta_Informatica_, 1 (1971), 115-138.  The problem is discussed on
pp. 131 ff.

     Tony Hoare also discusses the problem in a paper
     published in the proceedings of a seminar on 30 August
     1971 to 3 September 1971 at Queen's University,
     Belfast.  (The proceedings also republish Dijkstra's
     paper referenced above as pp. 72-93.)  He explicitly
     acknowledges "It will be obvious to all how much this
     paper owes to the thought and writings of Professor E.
     W. Dijkstra, to whom I owe . . . the examples of the
     bounded buffer and the spaghetti eaters."

C. A. R. Hoare, "Towards a theory of Parallel Programming",
_Operating_Systems_Techniques_, C. A. R. Hoare and R. H. Perrott,
ed. (Academic Press, 1972), pp. 61-71.  The problem is discussed
on pp. 67 ff.

     A paper by Coffman, Elphick and Shoshani from the same
     period (and explicitly referenced by Hoare) discusses
     deadlock without mention of the Dining Philosophers
     problem.

E. G. Coffman, Jr., M. J. Elphick, and A. Shoshani, "System
Deadlocks", _Computing_Surveys_, 3 (June 1971), 67-78.

     Similarly, Coffman and Denning discuss deadlock at
     length without mention of the Dining Philosophers.
     They reference Dijkstra's 1965 paper on "Cooperating
     Sequential Processes" (which does not include the
     Dining Philosophers problem) but do not reference his
     1971 paper given above.

Edward G. Coffman, Jr., and Peter J. Denning, _Operating_Systems_
Theory_ (Prentice-Hall, 1973), pp. 44-67.

     Tony Hoare also discusses the problem in his book
     _Communicating_Sequential_Processes_, but by 1985 the
     problem had so entered the common culture of computing
     that he gives it without reference.

C. A. R. Hoare, _Communicating_Sequential_Processes_ (Prentice/Hall
International, 1985), pp. 75 ff.
-- 
                                              --- Tim Rolfe
                                           rolfe@dsuvax.dsu.edu
                                            ROLFE@SDNET.BITNET