Actor model and process calculi

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):
*There is only one Actor model (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 physics and depends on them for its fundamental axioms, ''i.e.'' physical laws (see Actor model theory); the process calculi were originally inspired by algebra .
*Processes in the process calculi are anonymous, and communicate by sending messages either through named channels (synchronous or asynchronous), or via ambients (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).

How channels work

Indirect communication using channels (''e.g.'' Gilles Kahn and David MacQueen 977 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

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 FIFO 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 Processes (CSP) oare 1978 and 1985because 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 992.

Consider the following program written in CSP oare 1978
,
Y :: guard: boolean; guard := true;
* ,
Z :: n: integer; n:= 0;
* ?stop()_ → _Y!false;_print!n;
__________[Y?go()_ → _n_:=_n+1;_Y!true_.html" ;"title="/a>Y?go()  →  n := n+1; Y!true">?stop()  →  Y!false; print!n;
[Y?go()  →  n := n+1; Y!true ">/a>Y?go()  →  n := n+1; Y!true">?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 992 Chandy and Misra 988characterized 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 a 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.

Starvation on getting from multiple channels

Again consider the program written in CSP (discussed in Synchronous channels in process calculi above):
,
Y :: guard: boolean; guard := true;
* ,
Z :: n: integer; n:= 0;
* ?stop()_ → _Y!false;_print!n;
__________[Y?go()_ → _n_:=_n+1;_Y!true_.html"_;"title="/a>Y?go()_ → _n_:=_n+1;_Y!true">?stop()_ → _Y!false;_print!n;
__________[Y?go()_ → _n_:=_n+1;_Y!true_">/a>Y?go()_ → _n_:=_n+1;_Y!true">?stop()_ → _Y!false;_print!n;
__________[Y?go()_ → _n_:=_n+1;_Y!true_
As_pointed_out_in_Knabe_992_

Year_992_(_CMXCII)_was_a_leap_year_starting_on_Friday_(link_will_display_the_full_calendar)_of_the_Julian_calendar.
__Events_

__By_place_
__Worldwide_
*_Winter_–_A_superflare_from_the_sun_causes_an_Aurora_Borealis,_with_visibility_as_fa_...