|
 ABSTRACT
It is shown that distributed systems of probabilistic processors are essentially more powerful than distributed systems of deterministic processors, i.e., there are certain useful behaviors that can be realized only by the former. This is demonstrated on the dining philosophers problem. It is shown that, under certain natural hypotheses, there is no way the philosophers can be programmed (in a deterministic fashion) so as to guarantee the absence of deadlock (general starvation). On the other hand, if the philosophers are given some freedom of choice one may program them to guarantee that every hungry philosopher will eat (with probability one) under any circumstances (even an adversary scheduling). The solution proposed here is fully distributed and does not involve any central memory or any process with which every philosopher can communicate.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
 |
2
|
|
| |
3
|
Dijkstra, E. W. Hierarchical ordering of sequential processes, Operating Systems Techniques, Academic Press 1972.
|
| |
4
|
Francez, N. and Rodeh, M. A distributed abstract data type implemented by a probabilistic communication scheme. I.B.M. Israel Scientific Center TR-080, April 1980 (to be presented at 21st Annual Symposium on F.O.C.S., Syracuse Oct. 1980).
|
| |
5
|
Hoare, C. A. R. Towards a theory of parallel programming, Operating Systems Techniques, quoted above.
|
| |
6
|
|
| |
7
|
Holt, R. C., Graham, G. S., Lazowska, E. D., and Scott, M. A. Structured concurrent programming with operating systems applications, Addison-Wesley 1978.
|
| |
8
|
Kaubisch, W. H., Perrot, R. H., and Hoare, C. A. R. Quasiparallel programming. Software and Experience, Vol. 6 1976, pp. 341-356.
|
| |
9
|
Lamport, L. Private communication, 1978.
|
| |
10
|
Rabin, M. O. Theoretical impediments to artificial intelligence, Information Processing 74 (Jack L. Rosenfeld ed.), pp. 615-619.
|
| |
11
|
Rabin, M. O. N-process synchronization by 4.logN-valued shared variable, Technical Report Forschungsinstitut fuer mathematik, ETH Zuerich, March 1980, 21st Annual F.O.C.S. Symposium (1980).
|
| |
12
|
Rabin, M. O. The choice coordination problem Memorandum No. UCB/ERL M80/38, Univ. of Calif. Berkeley, August 1980.
|
CITED BY 46
|
|
Eyal Kushilevitz , Yishay Mansour , Michael O. Rabin , David Zuckerman, Lower bounds for randomized mutual exclusion, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.154-163, May 16-18, 1993, San Diego, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Nancy Lynch , Isaac Saias , Roberto Segala, Proving time bounds for randomized distributed algorithms, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.314-323, August 14-17, 1994, Los Angeles, California, United States
|
|
|
|
|
|
Alain Mayer , Yoram Ofek , Rafail Ostrovsky , Moti Yung, Self-stabilizing symmetry breaking in constant-space (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.667-678, May 04-06, 1992, Victoria, British Columbia, Canada
|
|
|
|
|
|
|
|
|
Baruch Awerbuch , Lenore J. Cowen , Mark A. Smith, Efficient asynchronous distributed symmetry breaking, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.214-223, May 23-25, 1994, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sandy Irani , Vitus Leung, Scheduling with conflicts, and applications to traffic signal control, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.85-94, January 28-30, 1996, Atlanta, Georgia, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Rajeev Motwani , Steven Phillips , Eric Torng, Non-clairvoyant scheduling, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.422-431, January 25-27, 1993, Austin, Texas, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Benny Chor , Amos Israeli , Ming Li, On processor coordination using asynchronous hardware, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.86-97, August 10-12, 1987, Vancouver, British Columbia, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf