Indeterminacy in concurrent computation: Difference between revisions

Revision as of 02:23, 2 April 2023

Latest revision as of 03:17, 21 July 2025

(8 intermediate revisions by 6 users not shown)

Line 1:

{{multiple|

{{Multiple issues|

{{Essay|date=November 2010}}

{{Citation style|date=March 2014}}

}}

'''Indeterminacy in concurrent computation''' is concerned with the effects of [[nondeterministic algorithm|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 gives rise to [[nondeterministic algorithm|indeterminacy]].

Line 28 ⟶ 27:

==A limitation of logic due to lack of information==

An open Actor system {{mono|S}} is one in which the addresses of outside Actors can be passed into {{mono|S}} in the middle of computations so that {{mono|S}} can communicate with these outside Actors. These outside Actors can then in turn communicate with Actors internal to {{mono|S}} using addresses supplied to them by {{mono|S}}. Due to the limitation of the inability to deduce arrival orderings, knowledge of what messages are sent from outside would not enable the response of {{mono|S}} to be deduced. When other models of concurrent systems (e.g., [[process calculus|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 (computer scientist)|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.{{Citation 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 39 ⟶ 38:

==Indeterminacy in other models of computation==

Arbitration is the basis of the indeterminacy in the [[Actor model]] of concurrent computation (see [[History of the Actor model]] and [[Actor model theory]]). It may also play a role in other models of concurrent systems, such as [[process calculus|process calculi]].

==See also==

Line 56 ⟶ 55:

*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.

Line 69 ⟶ 68:

==External links==

*[http://channel9.msdn.com/Shows/Going+Deep/Hewitt-Meijer-and-Szyperski-The-Actor-Model-everything-you-wanted-to-know-but-were-afraid-to-ask Hewitt, Meijer and Szyperski: The Actor Model (everything you wanted to know, but were afraid to ask)] Microsoft Channel 9. April 9, 2012.

{{Concurrent computing}}

[[Category:Actor model (computer science)]]