Actor model later history
Encyclopedia
In computer science
, the Actor model
, first published in 1973 , is a mathematical model of concurrent computation. This article reports on the later history of the Actor model in which major themes were investigation of the basic power of the model, study of issues of compositionality, development of architectures, and application to Open systems. It is the follow on article to Actor model middle history
which reports on the initial implementations, initial applications, and development of the first proof theory and denotational model.
[1985] argued that because of the use of Arbiters
that the Actor model was more powerful than logic programming
(see indeterminacy in concurrent computation).
A family of Prolog
-like concurrent message passing systems using unification of shared variables and data structure streams for messages were developed by Keith Clark
, Hervé Gallaire, Steve Gregory, Vijay Saraswat, Udi Shapiro, Kazunori Ueda, etc. Some of these authors made claims that these systems were based on mathematical logic. However, like the Actor model, the Prolog-like concurrent systems were based on message passing and consequently were subject to indeterminacy in the ordering of messages in streams that was similar to the indeterminacy in arrival ordering of messages sent to Actors. Consequently Carl Hewitt and Gul Agha [1991] concluded that the Prolog-like concurrent systems were neither deductive nor logical. They were not deductive because computational steps did not follow deductively from their predecessors and they were not logical because no system of mathematical logic was capable of deriving the facts of subsequent computational situations from their predecessors
and Petri nets. E.g., two lambda expressions are not a lambda expression and two Petri nets are not a Petri net and cannot influence each other.
In his doctoral dissertation Gul Agha addressed issues of compositionality in the Actor model. Actor configurations have receptionists that can receive messages from outside and may have the addresses of the receptionists of other Actor configurations. In this way two Actor configurations can be composed into another configuration whose subconfigurations can communicate with each other. Actor configurations have the advantage that they can have multiple Actors (i.e. the receptionists) which receive messages from outside without the disadvantage of having to poll to get messages from multiple sources (see issues with getting messages from multiple channels).
Monotonicity
Pluralism
Unbounded nondeterminism
Inconsistency
Carl Hewitt and Jeff Inman [1991] worked to develop semantics for Open Systems to address issues that had arisen in Distributed Artificial Intelligence. Carl Hewitt and Carl Manning [1994] reported on the development of Participatory Semantics for Open Systems.
However, none of the above formalisms addresses the crucial property of guarantee of service (see unbounded nondeterminism
).
Hardware development is furthering both local and nonlocal massive concurrency. Local concurrency is being enabled by new hardware for 64-bit many-core microprocessors, multi-chip modules, and high performance interconnect. Nonlocal concurrency is being enabled by new hardware for wired and wireless broadband packet switched communications. Both local and nonlocal storage capacities are growing exponentially. These hardware developments pose enormous modelling challenges. Hewitt [Hewitt 2006a, 2006b] is attempting to use the Actor model to address these challenges.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the Actor model
Actor 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...
, first published in 1973 , is a mathematical model of concurrent computation. This article reports on the later history of the Actor model in which major themes were investigation of the basic power of the model, study of issues of compositionality, development of architectures, and application to Open systems. It is the follow on article to Actor model middle history
Actor model middle history
In computer science, the Actor model, first published in 1973 , is a mathematical model of concurrent computation. This article reports on the middle history of the Actor model in which major themes were initial implementations, initial applications, and development of the first proof theory and...
which reports on the initial implementations, initial applications, and development of the first proof theory and denotational model.
Power of the Actor Model
Investigations began into the basic power of the Actor model. Carl HewittCarl 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....
[1985] argued that because of the 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...
that the Actor model was more powerful than 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...
(see indeterminacy in concurrent computation).
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 were developed by Keith Clark
Keith 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. Some of these authors made claims that these systems were based on mathematical logic. However, like the Actor model, the Prolog-like concurrent systems were based on message passing and consequently were subject to indeterminacy in the ordering of messages in streams that was similar to the indeterminacy in arrival ordering of messages sent to Actors. Consequently Carl Hewitt and Gul Agha [1991] concluded that the Prolog-like concurrent systems were neither deductive nor logical. They were not deductive because computational steps did not follow deductively from their predecessors and they were not logical because no system of mathematical logic was capable of deriving the facts of subsequent computational situations from their predecessors
Compositionality
Compositionality concerns composing systems from subsystems. Issues of compositionality had proven to be serious limitations for previous theories of computation including the lambda calculusLambda 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...
and Petri nets. E.g., two lambda expressions are not a lambda expression and two Petri nets are not a Petri net and cannot influence each other.
In his doctoral dissertation Gul Agha addressed issues of compositionality in the Actor model. Actor configurations have receptionists that can receive messages from outside and may have the addresses of the receptionists of other Actor configurations. In this way two Actor configurations can be composed into another configuration whose subconfigurations can communicate with each other. Actor configurations have the advantage that they can have multiple Actors (i.e. the receptionists) which receive messages from outside without the disadvantage of having to poll to get messages from multiple sources (see issues with getting messages from multiple channels).
Open Systems
Carl Hewitt [1985] pointed out that openness was becoming a fundamental challenge in software system development. Open distributed systems are required to meet the following challenges:Monotonicity
- Once something is published in an open distributed system, it cannot be taken back.
Pluralism
- Different subsystems of an open distributed system include heterogeneous, overlapping and possibly conflicting information. There is no central arbiter of truth in open distributed systems.
Unbounded nondeterminism
- Asynchronously, different subsystems can come up and go down and communication links can come in and go out between subsystems of an open distributed system. Therefore the time that it will take to complete an operation cannot be bounded in advance (see unbounded nondeterminismUnbounded nondeterminismIn computer science, unbounded nondeterminism or unbounded indeterminacy is a property of concurrency by which the amount of delay in servicing a request can become unbounded as a result of arbitration of contention for shared resources while still guaranteeing that the request will eventually be...
).
Inconsistency
- Large distributed systems are inevitably inconsistent concerning their information about the information system interactions of their human users
Carl Hewitt and Jeff Inman [1991] worked to develop semantics for Open Systems to address issues that had arisen in Distributed Artificial Intelligence. Carl Hewitt and Carl Manning [1994] reported on the development of Participatory Semantics for Open Systems.
Computer Architectures
Researchers at Caltech under the leadership of Chuck Seitz developed the Cosmic Cube which was one of the first message-passing Actor architectures. Subsequently at MIT researchers under the leadership of Bill Dally developed the J Machine.Attempts to relate Actor semantics to algebra and linear logic
[Kohei Honda and Mario Tokoro 1991], [José Meseguer 1992], [Ugo Montanari and Carolyn Talcott 1998], [M. Gaspari and G. Zavattaro 1999] have attempted to relate Actor semantics to algebra. Also [John Darlington and Y. K. Guo 1994] have attempted to relate linear logic to Actor semantics.However, none of the above formalisms addresses the crucial property of guarantee of service (see unbounded nondeterminism
Unbounded nondeterminism
In computer science, unbounded nondeterminism or unbounded indeterminacy is a property of concurrency by which the amount of delay in servicing a request can become unbounded as a result of arbitration of contention for shared resources while still guaranteeing that the request will eventually be...
).
Recent developments
Recent developments in the Actor model have come from several sources.Hardware development is furthering both local and nonlocal massive concurrency. Local concurrency is being enabled by new hardware for 64-bit many-core microprocessors, multi-chip modules, and high performance interconnect. Nonlocal concurrency is being enabled by new hardware for wired and wireless broadband packet switched communications. Both local and nonlocal storage capacities are growing exponentially. These hardware developments pose enormous modelling challenges. Hewitt [Hewitt 2006a, 2006b] is attempting to use the Actor model to address these challenges.