Indeterminacy in concurrent computation: Difference between revisions

Revision as of 15:11, 8 August 2011

Revision as of 13:14, 29 August 2011

Line 4:

'''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 [[Multi-core processor|many-core]] [[computer architectures]]. These computer systems make use of [[Arbiter (electronics)|arbiters]] which give rise to [[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{{fact|date=January 2011}}.

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 [[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]].