Actor model and process calculi

In computer science the Actor model is related to subsequent process calculi models of concurrent digital computation. The Actor model differs from the process calculi in several ways:

• There is only one Actor model whereas there are numerous process calculi.
• The Actor model was inspired by the laws of physics (physical laws) whereas the process calculi were inspired by algebra (see Actor model early history).
• There is no global state in modeling computational steps in the Actor model (see fairness and Actor model early history).
• The Actor model is closely related to the engineering concurency requirements of many-core (Platform 2015 Unveiled at IDF Spring 2005) computer architectures and Web Services.
• The Actor model has a denotational semantics with the property of unbounded nondeterminism [Clinger 1981] which does not require solving any recursive domain equations.
• The process calculi differ from the Actor model in their use of channels as opposed to direct communication. (See below.)

Channels

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. The process calculi differ from the Actor model in their use of channels as opposed to direct communication.

Synchronous

First to be developed were the synchronous process calculi as in Communicating Sequential Processes (the model) (Tony Hoare [1985])and pi-calculus (Robin Milner, Joachim Parrow, and David Walker [1989]). In synchronous process calculi, computing agencies (called "processes") communicate using channels (called "names") in which messages are stored and retrieved, Although a channel can be shared among processes, communication is binary, point-to-point interaction along a channel between a sender and a receiver in which the sender blocks until the message is received. In contrast, a message can be sent directly to any Actor address. A synchronous channel can be modeled by an Actor that receives put and get communications. The following is a simplified version of the behavior of an Actor for a synchronous channel:

• Each put communication has a message and an address to which an acknowledgment is sent when the message is gotten by a get communication from the channel in FIFO order.
• Each get communication has an address to which the gotten message is sent.

Asynchronous

Next asynchronous process calculi were developed.

• The Pict programming language (published in 1993) implemented concurrent computations that run in an operating system process on a single computer using asynchronous channels for communication rather than direct communication as in the Actor model. Pict dropped most of the aspects that complicate Actor modeling of the previous synchronous process calculi including the following:

• synchronous communication
• the choice operator
• full replication of processes

• 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.

An asynchronous channel can be modeled by an Actor that receives put and get communications. The following is a simplified version of the behavior of an Actor for an 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.

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.

Some recent process calculi have migration capabilities, e.g., mobile ambients and the calculus of mobile agents.

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.

Reconciling Process Calculi with the Actor model

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 semenatics 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).

Ugo Montanari and Carolyn Talcott [1998] have contributed to attempting to reconcile Actors with process calculi.

References

• Carl Hewitt, Peter Bishop and Richard Steiger. A Universal Modular Actor Formalism for Artificial Intelligence IJCAI 1973.
• Robin Milner. Processes: A Mathematical Model of Computing Agents in Logic Colloquium 1973.
• Carl Hewitt, et. al. Actor Induction and Meta-evaluation Conference Record of ACM Symposium on Principles of Programming Languages, January 1974.
• Carl Hewitt, et. al. Behavioral Semantics of Nonrecursive Control Structure Proceedings of Colloque sur la Programmation, April 1974.
• John Reynolds. On the Relation between Direct and Continuation Semantics Proceedings of Second Colloquium on Automata, Languages, and Programming. 1974.
• Irene Greif and Carl Hewitt. Actor Semantics of PLANNER-73 Conference Record of ACM Symposium on Principles of Programming Languages. January 1975.
• Carl Hewitt. How to Use What You Know IJCAI. September, 1975..
• Irene Greif. Semantics of Communicating Parallel Professes MIT EECS Doctoral Dissertation. August 1975.
• Gordon Plotkin. A powerdomain construction SIAM Journal of Computing September 1976.
• Carl Hewitt and Henry Baker Actors and Continuous Functionals Proceeding of IFIP Working Conference on Formal Description of Programming Concepts. August 1-5, 1977.
• Henry Baker and Carl Hewitt The Incremental Garbage Collection of Processes Proceeding of the Symposium on Artificial Intelligence Programming Languages. SIGPLAN Notices 12, August 1977.
• Gilles Kahn and David MacQueen. Coroutines and networks of parallel processes IFIP. 1977
• Carl Hewitt and Henry Baker Laws for Communicating Parallel Processes IFIP-77, August 1977.
• Aki Yonezawa Specification and Verification Techniques for Parallel Programs Based on Message Passing Semantics MIT EECS Doctoral Dissertation. December 1977.
• Carl Hewitt. Journal of Artificial Intelligence. June 1977.
• Henry Baker. Actor Systems for Real-Time Computation MIT EECS Doctoral Dissertation. January 1978.
• Michael Smyth. Power domains Journal of Computer and System Sciences. 1978.
• George Milne and Robin Milner. Concurrent processes and their syntax JACM. April, 1979.
• CAR Hoare. Communicating Sequential Processes CACM. August, 1978.
• Nissim Francez, C.A.R. Hoare, Daniel Lehmann, and Willem de Roever. Semantics of nondetermiism, concurrency, and communication Journal of Computer and System Sciences. December 1979.
• Nancy Lynch and Michael Fischer. On describing the behavior of distributed systems in Semantics of Concurrent Computation. Springer-Verlag. 1979.
• Jerald Schwartz Denotational semantics of parallelism in Semantics of Concurrent Computation. Springer-Verlag. 1979.
• Ralph-Johan Back. Semantics of Unbounded Nondeterminism ICALP 1980.
• Mathew Hennessy and Robin Milner. On Observing Nondeterminism and Concurrency LNCS 85. 1980.
• Will Clinger. Foundations of Actor Semantics MIT Mathematics Doctoral Dissertation. June 1981.
• Mathew Hennessy. A Term Model for Synchronous Processes Computer Science Dept. Edinburgh University. CSR-77-81. 1981.
• C.A.R. Hoare, S. Brookes and W. Roscoe. Programming Research Group. Oxford University. 1981.
• Robin Milner. Four combinators for concurrency ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. Ottawa, Canada, 1982.
• J.A. Bergstra and J.W. Klop. Process algebra for synchronous communication Information and Control. 1984.
• Luca Cardelli. An implementation model of rendezvous communication Seminar on Concurrency. Lecture Notes in Computer Science 197. Springer-Verlag. 1985
• Gul Agha. Actors: A Model of Concurrent Computation in Distributed Systems Doctoral Dissertation. 1986.
• Robert van Glabbeek. Bounded nondeterminism and the approximation induction principle in process algebra Symposium on Theoretical Aspects of Computer Sciences on STACS 1987.
• Robin Milner, Joachim Parrow and David Walker. A calculus of mobile processes Computer Science Dept. Edinburgh. Reports ECS-LFCS-89-85 and ECS-LFCS-89-86. June 1989. Revised Sept. 1990 and Oct. 1990 respectively.
• Carl Hewitt and Gul Agha. Guarded Horn clause languages: are they deductive and Logical? in Artificial Intelligence at MIT, Vol. 2. MIT Press 1991.
• Robin Milner. The Polyadic pi-Calculus: A Tutorial Edinburgh University. LFCS report ECS-LFCS-91-180. 1991.
• Kohei Honda and Mario Tokoro. An Object Calculus for Asynchronous Communication ECOOP 91.
• José Meseguer. Conditional rewriting logic as a unified model of concurrency in Selected papers of the Second Workshop on Concurrency and compositionality. 1992.
• Benjamin Pierce, Didier Rémy and David Turner. A typed higher-order programming language based on the pi-calculus Workshop on type Theory and its application to computer Systems. Kyoto University. July 1993.
• R. Amadio and S. Prasad. Locations and failures Foundations of Software Technology and Theoretical Computer Science Conference. 1994.
• Cédric Fournet and Georges Gonthier. The reflexive chemical abstract machine and the join-calculus POPL 1996.
• Cédric Fournet, Georges Gonthier, Jean-Jacques Lévy, Luc Maranget, and Didier Rémy. A Calculus of Mobile Agents CONCUR 1996.
• Gérard Boudol. The pi-calculus in direct style POPL 1997
• Tatsurou Sekiguchi and Akinori Yonezawa. A Calculus with Code Mobility FMOODS 1997.
• Luca Cardelli and Andrew Gordon. Mobile Ambients Foundations of Software Science and Computational Structures, Maurice Nivat (Ed.), Lecture Notes in Computer Science, Vol. 1378, Springer, 1998.
• Ugo Montanari and Carolyn Talcott. Can Actors and Pi-Agents Live Together? Electronic Notes in Theoretical Computer Science. 1998.
• Robin Milner. Communicating and Mobile Systems: the Pi-Calculus Cambridge University Press. 1999.
• Davide Sangiorgi and David Walker. The Pi-Calculus : A Theory of Mobile Processes Cambridge University Press. 2001.
• Nick Benton, Luca Cardelli, and Cédric Fournet. Modern Concurrency Abstractions for C# ECOOP 2002.
• Thati, Prasanna, Carolyn Talcott, and Gul Agha. Techniques for Executing and Reasoning About Specification Diagrams International Conference on Algebraic Methodology and Software Technology (AMAST), 2004.
• J. C. M. Baeten. A brief history of process algebra Theoretical Computer Science. 2005.
• J.C.M. Baeten, T. Basten, and M.A. Reniers. Algebra of Communicating Processes Cambridge University Press. 2005.
• Luca Aceto and Andrew D. Gordon (editors). Algebraic Process Calculi: The First Twenty Five Years and Beyond Process Algebra. Bertinoro, Forl`ı, Italy, August 1–5, 2005