|
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). 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: Synchronous channels in process calculi 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 comannd 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: | 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: 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 behavior of a guard is as follows:
The behavior of a channel is as follows:
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; *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, an issue 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 the Actor X is created with the following behavior:
the Actor Y is created with the following behavior:
the Actor Z is created with the following behavior that has a count n that is initially 0:
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: | 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: 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 that 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 asynchronouus 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: 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 π-calculus. Migration Migration is the ability of computational agencies to change locations. E.g., in his dissertation, Aki Yonezawa modeled a post office that customer Actors could enter, change locations within while operating, and exit. An Actor that can migrate can be modeled by having a location Actor that changes when the Actor migrates. However the faithfullness of this modeling is controversial and the subject of research. Note that there is a potential confusion in that the original literature on process calculi used the term mobility to mean the ability to change the topology of communication whereas later mobility is sometimes use to mean migration. E.g., process calculi such as the higher-order π-calculus and API-Calculus used mobility to mean change in topology whereas the mobile ambients use mobility to mean migration. In this respect the ambient calculus differs from the π-calculus in that communication is through ambients as opposed to being though channels in the π-calculus. 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 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 denotatinal semantics with unbounded nondeterminism for a subsequent version of Communicating Sequential Processes Hoare 1985. More recently 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. | |||||||
|
| ||||||||
 |
|
| |