The actor model is about the semantics of
message passing.
Unbounded nondeterminism controversy Arguably, the first concurrent programs were
interrupt handlers. During the course of its normal operation a computer needed to be able to receive information from outside (characters from a keyboard, packets from a network,
etc). So when the information arrived the execution of the computer was
interrupted and special code (called an interrupt handler) was called to put the information in a
data buffer where it could be subsequently retrieved. In the early 1960s, interrupts began to be used to simulate the concurrent execution of several programs on one processor. Having concurrency with
shared memory gave rise to the problem of
concurrency control. Originally, this problem was conceived as being one of
mutual exclusion on a single computer.
Edsger Dijkstra developed
semaphores and later, between 1971 and 1973,
Tony Hoare and
Per Brinch Hansen developed
monitors to solve the mutual exclusion problem. However, neither of these solutions provided a programming language construct that encapsulated access to shared resources. This encapsulation was later accomplished by the serializer construct ([Hewitt and Atkinson 1977, 1979] and [Atkinson 1980]). The first models of computation (
e.g.,
Turing machines, Post productions, the
lambda calculus,
etc.) were based on mathematics and made use of a global state to represent a computational
step (later generalized in [McCarthy and Hayes 1969] and [Dijkstra 1976] see
Event orderings versus global state). Each computational step was from one global state of the computation to the next global state. The global state approach was continued in
automata theory for
finite-state machines and push down
stack machines, including their
nondeterministic versions. Such nondeterministic automata have the property of
bounded nondeterminism; that is, if a machine always halts when started in its initial state, then there is a bound on the number of states in which it halts.
Edsger Dijkstra further developed the nondeterministic global state approach. Dijkstra's model gave rise to a controversy concerning
unbounded nondeterminism (also called
unbounded indeterminacy), 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 serviced. Hewitt argued that the actor model should provide the guarantee of service. In Dijkstra's model, although there could be an unbounded amount of time between the execution of sequential instructions on a computer, a (parallel) program that started out in a well defined state could terminate in only a bounded number of states [Dijkstra 1976]. Consequently, his model could not provide the guarantee of service. Dijkstra argued that it was impossible to implement unbounded nondeterminism. Hewitt argued otherwise: there is no bound that can be placed on how long it takes a computational circuit called an
arbiter to settle (see
metastability (electronics)). Arbiters are used in computers to deal with the circumstance that computer clocks operate asynchronously with respect to input from outside,
e.g., keyboard input, disk access, network input,
etc. So it could take an unbounded time for a message sent to a computer to be received and in the meantime the computer could traverse an unbounded number of states. The actor model features unbounded nondeterminism which was captured in a mathematical model by
Will Clinger using
domain theory.
Computational Representation Theorem There is a
Computational Representation Theorem in the actor model for systems which are closed in the sense that they do not receive communications from outside. The mathematical denotation denoted by a closed system \mathtt{S} is constructed from an initial behavior \bot_\mathtt{S} and a behavior-approximating function \mathbf{progression}_\mathtt{S}. These obtain increasingly better approximations and construct a denotation (meaning) for \mathtt{S} as follows [Hewitt 2008; Clinger 1981]: :\mathbf{Denote}_{\mathtt{S}} \equiv \lim_{i \to \infty} \mathbf{progression}_{\mathtt{S}^i}(\bot_\mathtt{S}) In this way, \mathtt{S} can be mathematically characterized in terms of all its possible behaviors (including those involving unbounded nondeterminism). Although \mathbf{Denote}_{\mathtt{S}} is not an implementation of \mathtt{S}, it can be used to prove a generalization of the Church-Turing-Rosser-Kleene thesis [Kleene 1943]: A consequence of the above theorem is that a finite actor can nondeterministically respond with an number of different outputs.
Relationship to logic programming One of the key motivations for the development of the actor model was to understand and deal with the control structure issues that arose in development of the
Planner programming language. Once the actor model was initially defined, an important challenge was to understand the power of the model relative to
Robert Kowalski's thesis that "computation can be subsumed by deduction". Hewitt argued that Kowalski's thesis turned out to be false for the concurrent computation in the actor model (see
Indeterminacy in concurrent computation). Nevertheless, attempts were made to extend
logic programming to concurrent computation. However, Hewitt and Agha [1991] claimed that the resulting systems were not deductive in the following sense: computational steps of the concurrent logic programming systems do not follow deductively from previous steps (see
Indeterminacy in concurrent computation). Recently, logic programming has been integrated into the actor model in a way that maintains logical semantics. was also notable in that it was not based on composing sequential processes. His work differed from the actor model because it was based on a fixed number of processes of fixed topology communicating numbers and strings using synchronous communication. The original
communicating sequential processes (CSP) model published by
Tony Hoare differed from the actor model because it was based on the parallel composition of a fixed number of sequential processes connected in a fixed topology, and communicating using synchronous message-passing based on process names (see
Actor model and process calculi history). Later versions of CSP abandoned communication based on process names in favor of anonymous communication via channels, an approach also used in Milner's work on the
calculus of communicating systems (CCS) and the
π-calculus. These early models by Milner and Hoare both had the property of bounded nondeterminism. Modern, theoretical CSP ([Hoare 1985] and [Roscoe 2005]) explicitly provides unbounded nondeterminism.
Petri nets and their extensions (e.g., coloured Petri nets) are like actors in that they are based on asynchronous message passing and unbounded nondeterminism, while they are like early CSP in that they define fixed topologies of elementary processing steps (transitions) and message repositories (places). ==Influence==