Added to Favorites

Related Searches

Definitions

Indeterminacy in concurrent computation is concerned with the effects of indeterminacy in concurrent computation.

Computation is an area in which indeterminacy is becoming increasingly important because of the massive increase in concurrency due to networking and the advent of many-core computer architectures. These computer systems make use of arbiters which give rise to indeterminacy.

Hewitt [1985], Hewitt and Agha [1991], and other published work argued that mathematical models of concurrency did not determine particular concurrent computations as follows: The Actor model makes use of arbitration (often in the form of notional Arbiters) for determining which message is next in the arrival ordering of an Actor that is sent multiple messages concurrently. This introduces indeterminacy in the arrival order. Since the arrival orderings are indeterminate, they cannot be deduced from prior information by mathematical logic alone. Therefore mathematical logic can not implement concurrent computation in open systems.

The authors note that although mathematical logic cannot, in their view, implement general concurrency it can implement some special cases of concurrent computation, e.g., sequential computation and some kinds of parallel computation including the lambda calculus.

It is important to be clear about the basis for the published claim about the limitation of mathematical logic. It was not just that Actors could not in general be implemented in mathematical logic. The published claim was that because of the indeterminacy of the physical basis of the Actor model, that no kind of deductive mathematical logic could escape the limitation. This became important later when researchers attempted to extend Prolog (which had some basis in logic programming) to concurrent computation using message passing. (See the section below).

What does the mathematical theory of Actors have to say about this? A closed system is defined to be one which does not communicate with the outside. Actor model theory provides the means to characterize all the possible computations of a closed Actor system. So mathematical logic can characterize (as opposed to implement) all the possible computations of a closed Actor system. Other models of concurrent systems, e.g., process calculi, can sometimes be used to characterize closed concurrent computations.

Carl Hewitt and Gul Agha [1991] argued that these Prolog-like concurrent systems were neither deductive nor logical: like the Actor model, the Prolog-like concurrent systems were based on message passing and consequently were subject to the same indeterminacy.

- Carl Hewitt. PLANNER: A Language for Proving Theorems in Robots IJCAI 1969.
- Carl Hewitt. Procedural Embedding of Knowledge In Planner IJCAI 1971.
- Carl Hewitt, Peter Bishop and Richard Steiger. A Universal Modular Actor Formalism for Artificial Intelligence IJCAI 1973.
- Robert Kowalski Predicate Logic as Programming Language Memo 70, Department of Artificial Intelligence, Edinburgh University. 1973.
- Pat Hayes. Computation and Deduction Mathematical Foundations of Computer Science: Proceedings of Symposium and Summer School, Štrbské Pleso, High Tatras, Czechoslovakia, September 3-8, 1973.
- Carl Hewitt and Henry Baker Laws for Communicating Parallel Processes IFIP-77, August 1977.
- Carl Hewitt. Viewing Control Structures as Patterns of Passing Messages Journal of Artificial Intelligence. June 1977.
- Henry Baker. Actor Systems for Real-Time Computation MIT EECS Doctoral Dissertation. January 1978.
- Bill Kornfeld and Carl Hewitt. The Scientific Community Metaphor IEEE Transactions on Systems, Man, and Cybernetics. January 1981.
- Will Clinger. Foundations of Actor Semantics MIT Mathematics Doctoral Dissertation. June 1981.
- Carl Hewitt. The Challenge of Open Systems Byte Magazine. April 1985. Reprinted in The foundation of artificial intelligence---a sourcebook Cambridge University Press. 1990.
- Gul Agha. Actors: A Model of Concurrent Computation in Distributed Systems Doctoral Dissertation. MIT Press. 1986.
- Robert Kowalski. The limitation of logic Proceedings of the 1986 ACM 14th Annual Conference on Computer science.
- Ehud Shapiro (Editor). Concurrent Prolog MIT Press. 1987.
- Robert Kowalski. The Early Years of Logic Programming Communications of the ACM. January 1988.
- Ehud Shapiro. The family of concurrent logic programming languages ACM Computing Surveys. September 1989.
- Carl Hewitt and Gul Agha. Guarded Horn clause languages: are they deductive and Logical? International Conference on Fifth Generation Computer Systems, Ohmsha 1988. Tokyo. Also in Artificial Intelligence at MIT, Vol. 2. MIT Press 1991.
- Carl Hewitt. The repeated demise of logic programming and why it will be reincarnated What Went Wrong and Why: Lessons from AI Research and Applications. Technical Report SS-06-08. AAAI Press. March 2006.
- Carl Hewitt (2006b) What is Commitment? Physical, Organizational, and Social COIN@AAMAS. April 27, 2006.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Sunday December 09, 2007 at 16:35:42 PST (GMT -0800)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Sunday December 09, 2007 at 16:35:42 PST (GMT -0800)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.