Daniel Lehmann
Michael O. Rabin
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.
- Brinch Hansen, P. Operating Systems Principles. Prentice-Hall 1973. Google Scholar
Digital Library
- Brinch Hansen, P. Distributed processes, a concurrent programming concept. CACM 21, 11 (November 1978). Google ScholarDigital Library
- Dijkstra, E. W. Hierarchical ordering of sequential processes, Operating Systems Techniques, Academic Press 1972.Google Scholar
- 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).Google Scholar
- Hoare, C. A. R. Towards a theory of parallel programming, Operating Systems Techniques, quoted above.Google Scholar
- Hoare, C. A. R. Communicating sequential processes. CACM 21, 8 (August 1978). Google ScholarDigital Library
- Holt, R. C., Graham, G. S., Lazowska, E. D., and Scott, M. A. Structured concurrent programming with operating systems applications, Addison-Wesley 1978.Google Scholar
- Kaubisch, W. H., Perrot, R. H., and Hoare, C. A. R. Quasiparallel programming. Software and Experience, Vol. 6 1976, pp. 341-356.Google ScholarCross Ref
- Lamport, L. Private communication, 1978.Google Scholar
- Rabin, M. O. Theoretical impediments to artificial intelligence, Information Processing 74 (Jack L. Rosenfeld ed.), pp. 615-619.Google Scholar
- 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).Google Scholar
- Rabin, M. O. The choice coordination problem Memorandum No. UCB/ERL M80/38, Univ. of Calif. Berkeley, August 1980.Google Scholar
Recommendations
Free will and moral responsibility in video games
Can a player be held morally responsible for the choices that she makes within a videogame? Do the moral choices that the player makes reflect in any way on the player's actual moral sensibilities? Many videogames offer players the options to make ...
(Dis)Advantages of Lock-free Synchronization Mechanisms for Multicore Embedded Systems
ICPP Workshops '19: Workshop Proceedings of the 48th International Conference on Parallel ProcessingEmbedded systems show a tendency of migrating to multicore processors. However, to fully use the potential of multicore processors, it is necessary to partition software into threads that execute concurrently and communicate using shared memory. In order ...
Comments