Indeterminacy in computation
Encyclopedia
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
.
[1973] argued that the "usual sharp distinction that is made between the processes of computation and deduction, is misleading". Robert Kowalski
developed the thesis that computation 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.
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
.
and arbiters
. 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 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 using the Representation Theorem [Hewitt 2007] as follows:
In this way, the behavior of S 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.
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.
, Hervé Gallaire, Steve Gregory, Vijay Saraswat, Udi Shapiro, Kazunori Ueda, etc. developed a family of Prolog
-like concurrent message passing systems using unification of shared variables and data structure streams for messages. Claims were made that these systems were based on mathematical logic. This kind of system was used as the basis of the Japanese 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.
of concurrent computation (see Actor model early history
and Actor model theory
). It may also play a role in other models of concurrent systems such as process calculi.
Indeterminacy
Indeterminacy or underdeterminacy may refer to:* Indeterminacy in computation * aleatoric music and indeterminacy in music.* Statically indeterminate*Indeterminacy a literary term...
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
Arbiter (electronics)
-Asynchronous arbiters:An important form of arbiter is used in asynchronous circuits, to select the order of access to a shared resource among asynchronous requests. Its function is to prevent two operations from occurring at once when they should not...
which give rise to indeterminacy
Indeterminacy
Indeterminacy or underdeterminacy may refer to:* Indeterminacy in computation * aleatoric music and indeterminacy in music.* Statically indeterminate*Indeterminacy a literary term...
.
A limitation of logic programming
Patrick HayesPatrick J. Hayes
Patrick John Hayes or Pat Hayes is a British computer scientist who lives and works in the United States. , he is a Senior Research Scientist at the Institute for Human and Machine Cognition in Pensacola, Florida. He received a B.A. in Mathematics from University of Cambridge and a Ph.D...
[1973] argued that the "usual sharp distinction that is made between the processes of computation and deduction, is misleading". Robert Kowalski
Robert Kowalski
Robert "Bob" Anthony Kowalski is a British logician and computer scientist, who has spent most of his career in the United Kingdom....
developed the thesis that computation 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
Carl Hewitt
Carl Hewitt is Board Chair of the International Society for Inconsistency Robustness. He has been a Visiting Professor at Stanford University and the University of Keio. In 2000, he became emeritus in the EECS department at MIT....
claimed that logical deduction was incapable of carrying out concurrent computation in open systems.
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
Arbiter (electronics)
-Asynchronous arbiters:An important form of arbiter is used in asynchronous circuits, to select the order of access to a shared resource among asynchronous requests. Its function is to prevent two operations from occurring at once when they should not...
) 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
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
.
Arrival order indeterminacy
According to Hewitt [2008], 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., see metastability in electronicsMetastability in electronics
Metastability in electronics is the ability of a digital electronic system to persist for an unbounded time in an unstable equilibrium or metastable state....
and arbiters
Arbiter (electronics)
-Asynchronous arbiters:An important form of arbiter is used in asynchronous circuits, to select the order of access to a shared resource among asynchronous requests. Its function is to prevent two operations from occurring at once when they should not...
. 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 extend Prolog
Prolog
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
(which had some basis in logic programming
Logic programming
Logic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy's [1958] advice-taker proposal, logic is used as a purely declarative representation language, and a...
) 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
Actor model theory
In theoretical computer science, Actor model theory concerns theoretical issues for the Actor model.Actors are the primitives that form the basis of the Actor model of concurrent digital computation. In response to a message that it receives, an Actor can make local decisions, create more Actors,...
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 system S is found by constructing increasingly better approximations from an initial behavior called ⊥S using a behavior approximating function progressionS to construct a denotation (meaning ) for S as follows :
- DenoteS ≡ ⊔i∈ω progressionSi(⊥S)
In this way, the behavior of S 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.
A limitation of logic due to lack of information
An open Actor system S is one in which the addresses of outside Actors can be passed into S in the middle of computations so that S can communicate with these outside Actors. These outside Actors can then in turn communicate with Actors internal to S using addresses supplied to them by S. Due to limitation of the inability to deduce arrival orderings, knowledge of what messages are sent from outside would not enable the response of S 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.
Prolog-like concurrent systems were claimed to be based on mathematical logic
Keith ClarkKeith Clark
Keith L. Clark is a Professor of Computer Science at Imperial College London, England. He has lectured in both mathematics and computer science. Since 1979 he has had a tenured position in the Department of Computing, Imperial College London, where he has been Professor of Computational Logic...
, Hervé Gallaire, Steve Gregory, Vijay Saraswat, Udi Shapiro, Kazunori Ueda, etc. developed a family of Prolog
Prolog
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
-like concurrent message passing systems using unification of shared variables and data structure streams for messages. Claims were made that these systems were based on mathematical logic. This kind of system was used as the basis of the Japanese Fifth Generation Project (ICOT)
Fifth generation computer
The Fifth Generation Computer Systems project was an initiative by Japan'sMinistry of International Trade and Industry, begun in 1982, to create a "fifth generation computer" which was supposed to perform much calculation using massive parallel processing...
.
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.
Logical operations and system efficiency
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.Indeterminacy in other models of computation
Arbitration is the basis of the indeterminacy in the Actor modelActor model
In computer science, the Actor model is a mathematical model of concurrent computation that treats "actors" as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and...
of concurrent computation (see Actor model early history
Actor model early history
In computer science, the Actor model, first published in 1973 , is a mathematical model of concurrent computation. This article is about the early history of the Actor model...
and Actor model theory
Actor model theory
In theoretical computer science, Actor model theory concerns theoretical issues for the Actor model.Actors are the primitives that form the basis of the Actor model of concurrent digital computation. In response to a message that it receives, an Actor can make local decisions, create more Actors,...
). It may also play a role in other models of concurrent systems such as process calculi.