Actor model and process calculi history
The Actor model and process calculi share an interesting history and co-evolution.
Early work
The Actor model, first published in 1973, is a mathematical model of concurrent computation. The Actor model 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 determine how to respond to the next message received.As opposed to the previous approach based on composing sequential processes, the Actor model was developed as an inherently concurrent model. In the Actor model sequentiality was a special case that derived from concurrent computation as explained in Actor model theory.
Robin Milner's initial published work on concurrency from the same year was also notable in that it positions mathematical semantics of communicating processes as a framework to understand a variety of interaction agents including the computer's interaction with memory. The framework of modelling was based on Scott's model of domains and as such was not based on sequential processes. His work differed from the Actor model in the following ways:
- There are a fixed number of processes as opposed to the Actor model which allows the number of Actors to vary dynamically
- The only quantities that can be passed in messages are integers and strings as opposed to the Actor model which allows the addresses of Actors to be passed in messages
- The processes have a fixed topology as opposed to the Actor model which allows varying topology
- Communication is synchronous as opposed to the Actor model in which an unbounded time can elapse between sending and receiving a message.
- The semantics provided bounded nondeterminism unlike the Actor model with unbounded nondeterminism. However, with bounded nondeterminism is impossible for a server to guarantee service to its clients, i.e., a client might starve.
The publication by Tony Hoare in 1978 of the original Communicating Sequential Processes was different from the Actor model which states:
The 1978 version of CSP differed from the Actor model in the following respects :
- The concurrency primitives of CSP were input, output, guarded commands, and parallel composition whereas the Actor model is based on asynchronous one-way messaging.
- The fundamental unit of execution was a sequential process in contrast to the Actor model in which execution was fundamentally concurrent. Sequential execution is problematical because multi-processor computers are inherently concurrent.
- The processes had a fixed topology of communication whereas Actors had a dynamically changing topology of communications. Having a fixed topology is problematical because it precludes the ability to dynamically adjust to changing conditions.
- The processes were hierarchically structured using parallel composition whereas Actors allowed the creation of non-hierarchical execution using futures . Hierarchical parallel composition is problematical because it precludes the ability to create a process that outlives its creator. Also message passing is the fundamental mechanism for generating parallelism in the Actor model; sending more messages generates the possibility of more parallelism.
- Communication was synchronous whereas Actor communication was asynchronous. Synchronous communication is problematical because the interacting processes might be far apart.
- Communication was between processes whereas in the Actor model communications are one-way to Actors. Synchronous communication between processes is problematical by requiring a process to wait on multiple processes.
- Data structures consisted of numbers, strings, and arrays whereas in the Actor model data structures were Actors. Restricting data structures to numbers, strings, and arrays is problematical because it prohibits programmable data structures.
- Messages contain numbers and strings whereas in the Actor model messages could include the addresses of Actors. Not allowing addresses in messages is problematical because it precludes flexibility in communication because there is no way to supply another process with the ability to communicate with an already known process.
- The model of CSP deliberately had bounded nondeterminism whereas the Actor model had unbounded nondeterminism. Dijkstra had convinced Hoare that a programming language with unbounded nondeterminism could not be implemented. Consequently it was not possible to guarantee that servers implemented using CSP would provide service to multiple clients.
Process calculi and Actor model
Milner, ''et al.''
In his Turing lecture, Milner remarked as follows:In 2003, Ken Kahn recalled in a message about the :
Hoare, ''et al.''
, Stephen Brookes, and A. W. Roscoe developed and refined the theory of CSP into its modern form. The approach taken in developing the theoretical version of CSP was heavily influenced by Robin Milner's work on the Calculus of Communicating Systems, and vice versa. Over the years there have been many fruitful exchanges of ideas between the researchers working on both CSP and CCS.Hewitt, ''et al.''
Will Clinger developed the first denotational Actor model for concurrent computation that embodied unbounded nondeterminism. Bill Kornfeld and Carl Hewitt showed that the Actor model could encompass large-scale concurrency. Agha developed Actors as a fundamental model for concurrent computation. His work on representing Actor abstraction and composition, and on developing an operational semantics for Actors based on asynchronous communications trees was explicitly influenced by Milner's work on the Calculus of Communicating Systems. as well the work of Clinger.Further co-evolution
The π-calculus, partially inspired by the Actor model as described by Milner above, introduced dynamic topology into the process calculi by allowing dynamic creation of processes and for the names to be passed among different processes. However, the goal of Milner and Hoare to attain an algebraic calculus led to a critical divergence from the Actor model: communication in the process calculi is not direct as in the Actor model but rather indirectly through channels. In contrast, recent work on the Actor model has emphasized denotational models and the Representation Theorem.Nevertheless there are interesting co-evolutions between the Actor Model and Process Calculi. Montanari and Talcott discussed whether the Actor Model and π-calculus were compatible with each other. Sangiorgi and Walker showed how Actor work on treating control structures as patterns of passing messages could be modeled using the π-calculus.
Although algebraic laws have been developed for the Actor model, they do not capture the crucial property of guaranteed delivery of messages sent to Serializers. For example see the following:
- Gaspari and Zavattaro
- Agha and Thati