Actor model and process calculi
Encyclopedia
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
).
(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:
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.
The behavior of a guarded choice command is as follows:
The behavior of a guard is as follows:
The behavior of a channel is as follows:
[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
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.
[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.
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.
.
[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.
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...
and process calculi are two closely related approaches to the modelling of concurrent digital computation
Concurrency (computer science)
In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other...
. See Actor model and process calculi history
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...
.
There are many similarities between the two approaches, but also several differences (some philosophical, some technical):
- There is only one Actor modelActor modelIn 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...
(although it has numerous formal systems for design, analysis, verification, modeling, etc.); there are numerous process calculi, developed for reasoning about a variety of different kinds of concurrent systems at various levels of detail (including calculi that incorporate time, stochastic transitions, or constructs specific to application areas such as security analysis). - The Actor model was inspired by the laws of physicsPhysicsPhysics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...
and depends on them for its fundamental axioms, i.e. physical lawPhysical lawA physical law or scientific law is "a theoretical principle deduced from particular facts, applicable to a defined group or class of phenomena, and expressible by the statement that a particular phenomenon always occurs if certain conditions be present." Physical laws are typically conclusions...
s (see Actor model theoryActor model theoryIn theoretical computer science, Actor model theory concerns theoretical issues for the Actor model.Actors are the primitives that form the basis of the Actor model of concurrent digital computation. In response to a message that it receives, an Actor can make local decisions, create more Actors,...
); the process calculi were originally inspired by algebraAlgebraAlgebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from them, including terms, polynomials, equations and algebraic structures...
. - Processes in the process calculi are anonymous, and communicate by sending messages either through named channelsChannel (communications)In telecommunications and computer networking, a communication channel, or channel, refers either to a physical transmission medium such as a wire, or to a logical connection over a multiplexed medium such as a radio channel...
(synchronous or asynchronous), or via ambientsAmbient calculusIn computer science, the ambient calculus is a process calculus devised by Luca Cardelli and Andrew D. Gordon in 1998, and used to describe and theorise about concurrent systems that include mobility...
(which can also be used to model channel-like communications ). In contrast, actors in the Actor model possess an identity, and communicate by sending messages to the mailing addresses of other actors (this style of communication can also be used to model channel-like communications — see below).
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
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...
).
How do channels work?
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.Issues with synchronous channels
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.Simple synchronous channels
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:- Each 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 FIFOFIFOFIFO is an acronym for First In, First Out, an abstraction related to ways of organizing and manipulation of data relative to time and prioritization...
order. - Each get communication has an address to which the received message is sent.
Synchronous channels in process calculi
However, simple synchronous channels do not suffice for process calculi such as Communicating Sequential ProcessesCommunicating sequential processes
In computer science, Communicating Sequential Processes is a formal language for describing patterns of interaction in concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras, or process calculi...
(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
Two-phase commit protocol
In transaction processing, databases, and computer networking, the two-phase commit protocol is a type of atomic commitment protocol . It is a distributed algorithm that coordinates all the processes that participate in a distributed atomic transaction on whether to commit or abort the transaction...
or perhaps even a three-phase commit protocol
Three-phase commit protocol
In computer networking and databases, the three-phase commit protocol is a distributed algorithm which lets all nodes in a distributed system agree to commit a transaction. Unlike the two-phase commit protocol however, 3PC is non-blocking. Specifically, 3PC places an upper bound on the amount...
if time-outs
Timeout (telecommunication)
In telecommunication and related engineering , the term timeout or time-out has several meanings, including...
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:
- the stop message is accepted from X, in which case Y is sent the value false and print is sent the value n
- a go 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.
Analogy with the committee coordination problem
According to Knabe [1992], Chandy and Misra [1988] characterized this as analogous to the committee coordination problem:- Professors in a university are assigned to various committees. Occasionally a professor will decide to attend a meeting of any of her committees, and will wait until that is possible. Meetings may begin only if there is full attendance. The task is to ensure that if all the members of a committee are waiting, then at least one of them will attend some meeting.
- The crux of this problem is that two or more committees might share a professor. When that professor becomes available, she can only choose one of the meetings, while the others continue to wait.
A simple distributed protocol
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:
- The command sends a message to each of its guards to prepare.
- When it receives the first response from one of its guards that it is prepared, then it sends a message to that guard to prepare to commit and sends messages to all of the other guards to abort.
- When it receives a message from the guard that it is 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.
- If all of its guards respond that they cannot prepare, then the guarded command does nothing.
The behavior of a guard is as follows:
- When a message to 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.
- When a message to 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.
- When a message to commit is received, then the guard sends an commit message to each of the channels.
- When a message to abort is received, then the guard sends an abort message to each of the channels.
The behavior of a channel is as follows:
- When a 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.
- When a 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.
- When a 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.
- When a 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.
-
-
- When a commit put communication is received, then depending on which of the following is received:
- When a commit get communication is received, then if not already done perform the put and get and clean up the preparations.
- When an abort get communication is received, then cancel the preparations
- When a commit get communication is received, then depending on which of the following is received:
- When a commit put communication is received, then if not already done perform the get and put and clean up the preparations.
- When an abort put communication is received, then cancel the preparations.
- When an abort put communication is received, then cancel the preparations.
- When an abort get communication is received, then cancel the preparations.
- When a commit put communication is received, then depending on which of the following is received:
-
Starvation on getting from multiple channels
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
Resource starvation
In computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. Without those resources, the program can never finish its task....
) 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
- the Actor X is created with the following behavior:
- If the message "start" is received, then send Z the message "stop"
- the Actor Y is created with the following behavior:
- If the message "start" is received, then send Z the message "go"
- If the message true is received, then send Z the message "go"
- If the message false is received, then do nothing
- the Actor Z is created with the following behavior that has a count n that is initially 0:
- If the message "start" is received, then do nothing.
- If the message "stop" is received, then send Y the message false and send print the message the count n.
- If the message "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.
Livelock on getting from multiple channels
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.
Efficiency
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.Summary of Issues
The subsections above have articulated the following three issues concerned with the use of synchronous channels for process calculi:- Starvation. The use of sychronous channels can cause starvation when a process attempts to get messages from multiple channels in a guarded choice command.
- Livelock. The use of synchronous channels can cause a process to be caught in livelock when it attempts to get messages from multiple channels in a guarded choice command.
- Efficiency. The use of synchronous channels can require a large number of communications in order to get messages from multiple channels in a guarded choice command.
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
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.Simple asynchronous channels
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:- Each 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).
- Each get communication has an address to which the gotten message is sent.
Asynchronous channels in process calculi
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 is based on a typed version of the asynchronous π-calculusPi-calculus
In theoretical computer science, the π-calculus is a process calculus originally developed by Robin Milner, and David Walker as a continuation of work on the process calculus CCS...
.
Algebras
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 , ,Denotational Semantics
Will Clinger (building on the work of Irene Greif [1975], Gordon Plotkin [1976], Henry BakerHenry Baker (computer scientist)
Henry Givens Baker Jr. is a computer scientist who has made contributions in garbage collection, functional programming languages, and linear logic. He was also one of the founders of Symbolics...
[1978], Michael Smyth [1978], and Francez, Hoare
Hoare
Hoare may refer to:Individual people* C. A. R. Hoare , British computer scientist* Des Hoare , Australian cricketer* Desmond Hoare , British sailor & educator...
, Lehmann, and de Roever [1979]) published the first satisfactory mathematical denotational
Denotational semantics
In computer science, denotational semantics is an approach to formalizing the meanings of programming languages by constructing mathematical objects which describe the meanings of expressions from the languages...
theory of 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...
using domain theory
Domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer science, where it is used to specify denotational...
in his dissertation in 1981. His semantics contrasted the 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...
of 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...
with the bounded nondeterminism of CSP
Communicating sequential processes
In computer science, Communicating Sequential Processes is a formal language for describing patterns of interaction in concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras, or process calculi...
[Hoare 1978] and Concurrent Processes [Milne and Milner 1979] (see denotational semantics
Denotational semantics
In computer science, denotational semantics is an approach to formalizing the meanings of programming languages by constructing mathematical objects which describe the meanings of expressions from the languages...
). Roscoe [2005] has developed a denotational semantics with unbounded nondeterminism for a subsequent version of Communicating Sequential Processes Hoare [1985]. More recently Carl Hewitt
Carl 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....
[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.