Indeterminacy in concurrent computation - Revision history

Sirfurboy: Unsourced 17 years

2024-08-18T19:27:59Z

Unsourced 17 years

← Previous revision		Revision as of 19:27, 18 August 2024
Line 29:		Line 29:

	==Prolog-like concurrent systems were claimed to be based on mathematical logic==		==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)]].		[[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. 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.		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.

Jarble: adding Template:Concurrent computing

2024-03-22T20:26:46Z

adding Template:Concurrent computing

← Previous revision		Revision as of 20:26, 22 March 2024
Line 67:		Line 67:
	==External links==		==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.		*[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)]]		[[Category:Actor model (computer science)]]

Cewbot: Normalize {{Multiple issues}}: Remove {{Multiple}} for only 1 maintenance template: Citation style

2024-02-23T06:41:41Z

Normalize {{Multiple issues}}: Remove {{Multiple}} for only 1 maintenance template: Citation style

← Previous revision		Revision as of 06:41, 23 February 2024
Line 1:		Line 1:
	{{multiple\|
	{{Essay\|date=November 2010}}		{{Essay\|date=November 2010}}
	{{Citation style\|date=March 2014}}		{{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]].		'''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]].

Maxeto0910: added multiple issues hatnote

2024-02-21T04:08:04Z

added multiple issues hatnote

← Previous revision		Revision as of 04:08, 21 February 2024
Line 1:		Line 1:
			{{multiple\|
	{{Essay\|date=November 2010}}		{{Essay\|date=November 2010}}
	{{Citation style\|date=March 2014}}		{{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]].		'''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]].

Cewbot: Normalize {{Multiple issues}}: Remove {{Multiple issues}} for only 1 maintenance template: Citation style

2024-02-03T00:26:56Z

Normalize {{Multiple issues}}: Remove {{Multiple issues}} for only 1 maintenance template: Citation style

← Previous revision		Revision as of 00:26, 3 February 2024
Line 1:		Line 1:
	{{Multiple issues\|
	{{Essay\|date=November 2010}}		{{Essay\|date=November 2010}}
	{{Citation style\|date=March 2014}}		{{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]].		'''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]].

JCW-CleanerBot: /* References */task, replaced: IEEE Transactions on Systems, Man and Cybernetics → IEEE Transactions on Systems, Man, and Cybernetics

2023-07-23T13:37:48Z

References: task, replaced: IEEE Transactions on Systems, Man and Cybernetics → IEEE Transactions on Systems, Man, and Cybernetics

← Previous revision		Revision as of 13:37, 23 July 2023
Line 56:		Line 56:
	*Carl Hewitt. '''Viewing Control Structures as Patterns of Passing Messages''' [[Journal of Artificial Intelligence]]. June 1977.		*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.		*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.		*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.		*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.		*Carl Hewitt. '''The Challenge of Open Systems''' Byte Magazine. April 1985. Reprinted in ''The foundation of artificial intelligence–a sourcebook'' Cambridge University Press. 1990.

Правдивыетриумпы: /* Arrival order indeterminacy */

2023-04-02T02:24:34Z

Arrival order indeterminacy

← Previous revision		Revision as of 02:24, 2 April 2023
Line 39:		Line 39:

	==Indeterminacy in other models of computation==		==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]].		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==		==See also==

Правдивыетриумпы: /* Arrival order indeterminacy */

2023-04-02T02:23:48Z

Arrival order indeterminacy

← Previous revision		Revision as of 02:23, 2 April 2023
Line 28:		Line 28:

	==A limitation of logic due to lack of information==		==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 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.		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==		==Prolog-like concurrent systems were claimed to be based on mathematical logic==

Правдивыетриумпы: /* Arrival order indeterminacy */

2023-04-02T02:23:21Z

Arrival order indeterminacy

← Previous revision		Revision as of 02:23, 2 April 2023
Line 16:		Line 16:
	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., see [[metastability in electronics]] and [[arbiter (electronics)\|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.		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., see [[metastability in electronics]] and [[arbiter (electronics)\|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).		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:		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:

Правдивыетриумпы at 02:23, 2 April 2023

2023-04-02T02:23:06Z

← Previous revision		Revision as of 02:23, 2 April 2023
Line 9:		Line 9:
	[[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{{citation needed\|date=January 2011}}.		[[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{{citation 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 cannot implement concurrent computation in open systems.		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 who 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 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 of [[parallel computing]] including the [[lambda calculus]].		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 of [[parallel computing]] including the [[lambda calculus]].

← Previous revision		Revision as of 06:41, 23 February 2024
Line 1:		Line 1:
	{{multiple\|
	{{Essay\|date=November 2010}}		{{Essay\|date=November 2010}}
	{{Citation style\|date=March 2014}}		{{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]].		'''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]].

← Previous revision		Revision as of 04:08, 21 February 2024
Line 1:		Line 1:
			{{multiple\|
	{{Essay\|date=November 2010}}		{{Essay\|date=November 2010}}
	{{Citation style\|date=March 2014}}		{{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]].		'''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]].

← Previous revision		Revision as of 00:26, 3 February 2024
Line 1:		Line 1:
	{{Multiple issues\|
	{{Essay\|date=November 2010}}		{{Essay\|date=November 2010}}
	{{Citation style\|date=March 2014}}		{{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]].		'''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]].