Indeterminacy in concurrent computation: Difference between revisions

Revision as of 20:33, 2 March 2014

Revision as of 09:28, 3 December 2014

Line 2:

{{citation-style|date=March 2014}}

'''Indeterminacy in concurrent computation''' is concerned with the effects of [[Indeterminacy in computation|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 [[Multi-core processor|many-core]] computer architectures. These computer systems make use of [[Arbiter (electronics)|arbiters]] which give rise to [[Nondeterministic algorithm|indeterminacy]].

==A limitation of logic programming==

[[Patrick J. Hayes|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 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{{factcitation needed|date=January 2011}}.

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 notional [[Arbiter (electronics)|Arbiters]]) for determining which message is next in the [[Actor model theory#Arrival orderings|arrival ordering]] of an Actor that is sent multiple messages concurrently. This introduces [[Arbiter (electronics)#Arbiters give rise to indeterminacy|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 programming|parallel]] computation including the [[lambda calculus]].

Line 20:

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:

:The mathematical denotation denoted by a closed system <tt>{{mono|S</tt>}} is found by constructing increasingly better approximations from an initial behavior called <tt>{{mono|⊥_S</tt>}} using a behavior approximating function <tt>{{mono|'''progression'''_S</tt>}} to construct a denotation (meaning ) for <tt>{{mono|S</tt>}} as follows :

::<tt>{{mono|'''Denote'''_S ≡ <math> \lim_{i \to \infty}</math> '''progression'''_Sⁱ(⊥_S)</tt>}}

In this way, the behavior of <tt>{{mono|S</tt>}} 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 <tt>{{mono|S</tt>}} is one in which the addresses of outside Actors can be passed into <tt>{{mono|S</tt>}} in the middle of computations so that <tt>{{mono|S<tt> }}can communicate with these outside Actors. These outside Actors can then in turn communicate with Actors internal to <tt>{{mono|S</tt>}} using addresses supplied to them by <tt>{{mono|S</tt>}}. Due to limitation of the inability to deduce arrival orderings, knowledge of what messages are sent from outside would not enable the response of <tt>{{mono|S</tt>}} 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 Clark]], 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.{{FactCitation needed|date=March 2007}} This kind of system was used as the basis of the [[Fifth generation computer|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.

Line 53:

*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-83–8, 1973.

*Carl Hewitt and [[Henry Baker (computer scientist)|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.