In computer science, the Actor model and process calculi are two closely related approaches to the modelling of concurrent digital computation. See Actor model and process calculi history.
There are many similarities between the two approaches, but also several differences (some philosophical, some technical):
The publications on the Actor model and on process calculi have a fair number of cross-references, acknowledgments, and reciprocal citations (see Actor model and process calculi history).
Indirect communication using channels (e.g. Gilles Kahn and David MacQueen [1977]) has been an important issue for communication in parallel and concurrent computation affecting both semantics and performance. Some process calculi differ from the Actor model in their use of channels as opposed to direct communication.
Synchronous channels have the property that a sender putting a message in the channel must wait for a receiver to get the message out of the channel before the sender can proceed.
A synchronous channel can be modeled by an Actor that receives put and get communications. The following is the behavior of an Actor for a simple synchronous channel:
put communication has a message and an address to which an acknowledgment is sent when the message is received by a get communication from the channel in FIFO order.get communication has an address to which the received message is sent.However, simple synchronous channels do not suffice for process calculi such as Communicating Sequential Processes (CSP) [Hoare 1978 and 1985] because use of the guarded choice (after Dijkstra) command (called the alternative command in CSP). In a guarded choice command multiple offers (called guards) can be made concurrently on multiple channels to put and get messages; however at most one of the guards can be chosen for each execution of the guarded choice command. Because only one guard can be chosen, a guarded choice command in general effectively requires a kind of two-phase commit protocol or perhaps even a three-phase commit protocol if time-outs are allowed in guards (as in Occam 3 [1992]).
Consider the following program written in CSP [Hoare 1978]:
[X :: Z!stop() ||
Y :: guard: boolean; guard := true;
*[guard → Z!go(); Z?guard] ||
Z :: n: integer; n:= 0;
*[X?stop() → Y!false; print!n;
[] Y?go() → n := n+1; Y!true]
]
According to Clinger [1981], this program illustrates global nondeterminism, since the nondeterminism arises from incomplete specification of the timing of signals between the three processes X, Y, and Z. The repetitive guarded command in the definition of Z has two alternatives:
stop message is accepted from X, in which case Y is sent the value false and print is sent the value ngo message is accepted from Y, in which case n is incremented and Y is sent the value true.If Z ever accepts the stop message from X, then X terminates. Accepting the stop causes Y to be sent false which when input as the value of its guard will cause Y to terminate. When both X and Y have terminated, Z terminates because it no longer has live processes providing input.
In the above program, there are synchronous channels from X to Z, Y to Z, and Z to Y.
According to Knabe [1992], Chandy and Misra [1988] characterized this as analogous to the committee coordination problem:
This section presents a simple distributed protocol for channels in synchronous process calculi. The protocol has some problems that are addressed in the sections below.
The behavior of a guarded choice command is as follows:
prepare.prepare to commit and sends messages to all of the other guards to abort.
prepared to commit, then it sends the guard a commit message. However, if the guard throws an exception that it cannot prepare to commit, then guarded choice command starts the whole process all over again.prepare, then the guarded command does nothing.The behavior of a guard is as follows:
prepare is received, then the guard sends a prepare message to each of the channels with which it is offering to communicate. If the guard has booleans such that it cannot prepare or if any of the channels respond that they cannot prepare, then it sends abort messages to the other channels and then responds that it cannot prepare.
prepare to commit is received, then the guard sends a prepare to commit message to each of the channels. If any of the channels respond that they cannot prepare to commit, then it sends abort messages to the other channels and then throws an exception that it cannot prepare to commit.commit is received, then the guard sends a commit message to each of the channels.abort is received, then the guard sends an abort message to each of the channels.The behavior of a channel is as follows:
prepare to put communication is received, then respond that it is prepared if there is a prepare to get communication pending unless a terminate communication has been received, in which case throw an exception that it cannot prepare to put.prepare to get communication is received, then respond that it is prepared if there is a prepare to put communication pending unless a terminate communication has been received, in which case throw an exception that it cannot prepare to get.
prepare to commit to put communication is received, then respond that it is prepared if there is a prepare to commit to get communication pending unless a terminate communication has been received, in which case throw an exception that it cannot prepare to commit to put.prepare to commit to get communication is received, then respond that it is prepared if there is a prepare to commit to put communication pending unless a terminate communication has been received, in which case throw an exception that it cannot prepare to commit to get.
commit put communication is received, then depending on which of the following is received:
commit get communication is received, then if not already done perform the put and get and clean up the preparations.abort get communication is received, then cancel the preparationscommit get communication is received, then depending on which of the following is received:
commit put communication is received, then if not already done perform the get and put and clean up the preparations.abort put communication is received, then cancel the preparations.abort put communication is received, then cancel the preparations.abort get communication is received, then cancel the preparations.Again consider the program written in CSP (discussed in Synchronous channels in process calculi above):
[X :: Z!stop() ||
Y :: guard: boolean; guard := true;
*[guard → Z!go(); Z?guard] ||
Z :: n: integer; n:= 0;
*[X?stop() → Y!false; print!n;
[] Y?go() → n := n+1; Y!true]
]
As pointed out in Knabe [1992], a problem with the above protocol (A simple distributed protocol) is that the process Z might never accept the stop message from X (a phenomenon called starvation) and consequently the above program might never print anything.
In contrast consider, a simple Actor system that consists of Actors X, Y, Z, and print where
"start" is received, then send Z the message "stop""start" is received, then send Z the message "go""go"n that is initially 0:
"start" is received, then do nothing."stop" is received, then send Y the message false and send print the message the count n."go" is received, then send Y the message true and process the next message received with count n being n+1.By the laws of Actor semantics, the above Actor system will always halt when the Actors X, Y, are Z are each sent a "start" message resulting in sending print a number that can be unbounded large.
The difference between the CSP program and the Actor system is that the Actor Z does not get messages using a guarded choice command from multiple channels. Instead it processes messages in arrival ordering, and by the laws for Actor systems, the stop message is guaranteed to arrive.
Consider the following program written in CSP [Hoare 1978]:
[Bidder1 :: b: bid;
*[Bids1?b → process1!b;
[] Bids2?b → process1!b;] ||
Bidder2 :: b: bid;
*[Bids1?b → process2!b;
[] Bids2?b → process2!b;]
]
As pointed out in Knabe [1992], an issue with the above protocol (A simple distributed protocol) is that the process Bidder2 might never accept a bid from Bid1 or Bid2 (a phenomenon called livelock) and consequently process2 might never be sent anything. In each attempt to accept a message, Bidder2 is thwarted because the bid that was offered by Bids1 or Bids2 is snatched away by Bidder1 because it turns out that Bidder1 has much faster access than Bidder2 to Bids1 and Bids2. Consequently, Bidder1 can accept a bid, process it and accept another bid before Bidder2 can commit to accepting a bid.
As pointed out in Knabe [1992], an issue with the above protocol (A simple distributed protocol) is the large number of communications that must be sent in order to perform the handshaking in order to send a message through a synchronous channel. Indeed, as shown in the previous section (Livelock), the number of communications can be unbounded.
The subsections above have articulated the following three issues concerned with the use of synchronous channels for process calculi:
It is notable that in all of the above, issues arise from the use of a guarded choice command to get messages from multiple channels.
Asynchronous channels have the property that a sender putting a message in the channel need not wait for a receiver to get the message out of the channel.
An asynchronous channel can be modeled by an Actor that receives put and get communications. The following is the behavior of an Actor for a simple asynchronous channel:
put communication has a message and an address to which an acknowledgment is sent immediately (without waiting for the message to be gotten by a get communication).get communication has an address to which the gotten message is sent.The Join-calculus programming language (published in 1996) implemented local and distributed concurrent computations. It incorporated asynchronous channels as well as a kind of synchronous channel that is used for procedure calls. Agha's Aπ Actor calculus (Agha and Thati 2004) is based on a typed version of the asynchronous π-calculus.
The use of algebraic techniques was pioneered in the process calculi. Subsequently, several different process calculi intended to provide algebraic reasoning about Actor systems have been developed in (Gaspari and Zavattaro 1997), (Gaspari and Zavattaro 1999), (Agha and Thati 2004).
Will Clinger (building on the work of Irene Greif [1975], Gordon Plotkin [1976], Henry Baker [1978], Michael Smyth [1978], and Francez, Hoare, Lehmann, and de Roever [1979]) published the first satisfactory mathematical denotational theory of the Actor model using domain theory in his dissertation in 1981. His semantics contrasted the unbounded nondeterminism of the Actor model with the bounded nondeterminism of CSP [Hoare 1978] and Concurrent Processes [Milne and Milner 1979] (see denotational semantics). Roscoe [2005] has developed a denotational semantics with unbounded nondeterminism for a subsequent version of Communicating Sequential Processes Hoare [1985]. More recently Carl Hewitt [2006b] developed a denotational semantics for Actors based on timed diagrams.
Ugo Montanari and Carolyn Talcott [1998] have contributed to attempting to reconcile Actors with process calculi.