 | This article has multiple issues. Please helpimprove it or discuss these issues on thetalk page.(Learn how and when to remove these messages) (Learn how and when to remove this message)
|
Indeterminacy in concurrent computation is concerned with the effects ofindeterminacy inconcurrent 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 ofmany-core computer architectures. These computer systems make use ofarbiters which gives rise toindeterminacy.
Patrick Hayes [1973] argued that the "usual sharp distinction that is made between the processes of computation and deduction, is misleading".Robert Kowalski developed the thesis thatcomputation could be subsumed by deduction and quoted with approval "Computation is controlled deduction." which he attributed to Hayes in his 1988 paper on the early history of Prolog. Contrary to Kowalski and Hayes,Carl Hewitt claimed that logical deduction was incapable of carrying out concurrent computation in open systems[citation needed].
Hewitt [1985] 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 notionalarbiters) for determining which message is next in thearrival ordering of an Actor who is sent multiple messages concurrently. This introducesindeterminacy in the arrival order. Since the arrival orderings are indeterminate, they cannot be deduced from prior information by mathematical logic alone. Therefore, mathematical logic cannot implement concurrent computation in open systems.
The authors claim 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 ofparallel computing including thelambda calculus.
According to Hewitt, in concrete terms for Actor systems, typically we cannot observe the details by which the arrival order of messages for an Actor is determined. Attempting to do so affects the results and can even push the indeterminacy elsewhere. e.g., seemetastability in electronics andarbiters. Instead of observing the internals of arbitration processes of Actor computations, we await outcomes. Indeterminacy in arbiters produces indeterminacy in Actors. The reason that we await outcomes is that we have no alternative because of indeterminacy.
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 extendProlog (which had some basis inlogic programming) to concurrent computation using message passing. (See the section below).
What does the mathematical theory of Actors have to say about this? Aclosed 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 using the Representation Theorem [Hewitt 2007] as follows:
- The mathematical denotation denoted by a closed systemS is found by constructing increasingly better approximations from an initial behavior called⊥S using a behavior approximating functionprogressionS to construct a denotation (meaning ) forS as follows:
In this way, the behavior ofS can be mathematically characterized in terms of all its possible behaviors (including those involving unbounded nondeterminism).
So mathematical logic can characterize (as opposed to implement) all the possible computations of a closed Actor system.
An open Actor systemS is one in which the addresses of outside Actors can be passed intoS in the middle of computations so thatS can communicate with these outside Actors. These outside Actors can then in turn communicate with Actors internal toS using addresses supplied to them byS. Due to the limitation of the inability to deduce arrival orderings, knowledge of what messages are sent from outside would not enable the response ofS to be deduced. When other models of concurrent systems (e.g.,process calculi) are used to implement open systems, these systems also can have behavior that depends on arrival time orderings and so cannot be implemented by logical deduction.
Keith Clark, Hervé Gallaire, Steve Gregory, Vijay Saraswat, Udi Shapiro, Kazunori Ueda, etc. developed a family ofProlog-like concurrent message passing systems using unification of shared variables and data structure streams for messages. This kind of system was used as the basis of theJapanese Fifth Generation Project (ICOT).
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.
Hewitt maintained that a basic lesson can be learned from Prolog and the Prolog-like concurrent systems: a universal model of concurrent computation is limited by having any mandatory overhead in the basic communication mechanisms. This is an argument against including pattern-directed invocation using unification and extraction of messages from data structure streams as fundamental primitives. But compare Shapiro's survey of Prolog-like concurrent programming languages for arguments for inclusion.
Arbitration is the basis of the indeterminacy in theActor model of concurrent computation (seeHistory of the Actor model andActor model theory). It may also play a role in other models of concurrent systems, such asprocess calculi.
| General | |
|---|---|
| Process calculi | |
| Classic problems | |
