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,[1] is a mathematical model of concurrent computation. The Actor model 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 determine how to respond to the next message received.

As opposed to the previous approach based on composing sequential processes, the Actor model was developed as an inherently concurrent model. In the Actor model sequentiality was a special case that derived from concurrent computation as explained in Actor model theory.

Robin Milner's initial published work on concurrency from the same year[2] was also notable in that it positions mathematical semantics of communicating processes as a framework to understand a variety of interaction agents including the computer's interaction with memory. The framework of modelling was based on Scott's model of domains and as such was not based on sequential processes. His work differed from the Actor model in the following ways:

  • There are a fixed number of processes as opposed to the Actor model which allows the number of Actors to vary dynamically
  • The only quantities that can be passed in messages are integers and strings as opposed to the Actor model which allows the addresses of Actors to be passed in messages
  • The processes have a fixed topology as opposed to the Actor model which allows varying topology
  • Communication is synchronous as opposed to the Actor model in which an unbounded time can elapse between sending and receiving a message.
  • The semantics provided bounded nondeterminism unlike the Actor model with unbounded nondeterminism. However, with bounded nondeterminism is impossible for a server to guarantee service to its clients, i.e., a client might starve.

Milner later removed some of these restrictions in his work on the Pi calculus (see section Milner, et al. below).

The publication by Tony Hoare in 1978 of the original Communicating Sequential Processes was different from the Actor model which states:[3]

This paper suggests that input and output are basic primitives of programming and that parallel composition of communicating sequential processes is a fundamental program structuring method. When combined with a development of Dijkstra's guarded command, these concepts are surprisingly versatile. Their use is illustrated by sample solutions of a variety of familiar programming exercises.
...
The programs expressed in the proposed language are intended to be implementable both by a conventional machine with a single main store, and by a fixed network of processors connected by input/output channels (although very different optimizations are appropriate in the different cases). It is consequently a rather static language: The text of a program determines a fixed upper bound on the number of processes operating concurrently; there is no recursion and no facility for process-valued variables. In other respects also, the language has been stripped to the barest minimum necessary for explanation of its more novel features.
...
This paper has suggested that input, output, and concurrency should be regarded as primitives of programming, which underlie many familiar and less familiar programming concepts. However, it would be unjustified to conclude that these primitives can wholly replace the other concepts in a programming language. Where a more elaborate construction (such as a procedure or a monitor) is frequently useful, has properties which are more simply provable, and can also be implemented more efficiently than the general case, there is a strong reason for including in a programming language a special notation for that construction. The fact that the construction can be defined in terms of simpler underlying primitives is a useful guarantee that its inclusion is logically consistent with the remainder of the language.

The 1978 version of CSP differed from the Actor model in the following respects [Clinger 1981]:

  • The concurrency primitives of CSP were input, output, guarded commands, and parallel composition whereas the Actor model is based on asynchronous one-way messaging.
  • The fundamental unit of execution was a sequential process in contrast to the Actor model in which execution was fundamentally concurrent. Sequential execution is problematical because multi-processor computers are inherently concurrent.
  • The processes had a fixed topology of communication whereas Actors had a dynamically changing topology of communications. Having a fixed topology is problematical because it precludes the ability to dynamically adjust to changing conditions.
  • The processes were hierarchically structured using parallel composition whereas Actors allowed the creation of non-hierarchical execution using futures [Baker and Hewitt 1977]. Hierarchical parallel composition is problematical because it precludes the ability to create a process that outlives its creator. Also message passing is the fundamental mechanism for generating parallelism in the Actor model; sending more messages generates the possibility of more parallelism.
  • Communication was synchronous whereas Actor communication was asynchronous. Synchronous communication is problematical because the interacting processes might be far apart.
  • Communication was between processes whereas in the Actor model communications are one-way to Actors. Synchronous communication between processes is problematical by requiring a process to wait on multiple processes.
  • Data structures consisted of numbers, strings, and arrays whereas in the Actor model data structures were Actors. Restricting data structures to numbers, strings, and arrays is problematical because it prohibits programmable data structures.
  • Messages contain numbers and strings whereas in the Actor model messages could include the addresses of Actors. Not allowing addresses in messages is problematical because it precludes flexibility in communication because there is no way to supply another process with the ability to communicate with an already known process.
  • The model of CSP deliberately had bounded nondeterminism [Francez, Hoare, Lehmann, and de Roever 1979] whereas the Actor model had unbounded nondeterminism. Dijkstra [1976] had convinced Hoare that a programming language with unbounded nondeterminism could not be implemented. Consequently it was not possible to guarantee that servers implemented using CSP would provide service to multiple clients.

Process calculi and Actor model

Milner, et al.

In his Turing lecture,[4] Milner remarked as follows:

Now, the pure lambda-calculus is built with just two kinds of thing: terms and variables. Can we achieve the same economy for a process calculus? Carl Hewitt, with his Actors model, responded to this challenge long ago; he declared that a value, an operator on values, and a process should all be the same kind of thing: an Actor. This goal impressed me, because it implies the homogeneity and completeness of expression ... But it was long before I could see how to attain the goal in terms of an algebraic calculus...So, in the spirit of Hewitt, our first step is to demand that all things denoted by terms or accessed by names--values, registers, operators, processes, objects--are all of the same kind of thing; they should all be processes. Thereafter we regard access-by-name as the raw material of computation...

In 2003, Ken Kahn recalled in a message about the Pi calculus:

Pi calculus is based upon synchronous (hand-shake) communication. About 25 years ago I went to dinner with Carl Hewitt and Robin Milner (of CCS and pi calculus fame) and they were arguing about synchronous vs. asynchronous communication primitives. Carl used the post office metaphor while Robin used the telephone. Both quickly admitted that one can implement one in the other.

Hoare, et al.

Tony Hoare, Stephen Brookes, and A. W. Roscoe developed and refined the theory of CSP into its modern form.[5] The approach taken in developing the theoretical version of CSP was heavily influenced by Robin Milner's work on the Calculus of Communicating Systems (CCS), and vice versa. Over the years there have been many fruitful exchanges of ideas between the researchers working on both CSP and CCS.

Hewitt, et al.

Will Clinger [1981] developed the first denotational Actor model for concurrent computation that embodied unbounded nondeterminism. Bill Kornfeld and Carl Hewitt [1981] showed that the Actor model could encompass large-scale concurrency. Agha developed Actors as a fundamental model for concurrent computation. His work on representing Actor abstraction and composition, and on developing an operational semantics for Actors based on asynchronous communications trees was explicitly influenced by Milner's work on the Calculus of Communicating Systems (CCS).[6] as well the work of Clinger.

Further co-evolution

The π-calculus, partially inspired by the Actor model as described by Milner above, introduced dynamic topology into the process calculi by allowing dynamic creation of processes and for the names to be passed among different processes. However, the goal of Milner and Hoare to attain an algebraic calculus led to a critical divergence from the Actor model: communication in the process calculi is not direct as in the Actor model but rather indirectly through channels (see Actor model and process calculi). In contrast, recent work on the Actor model [Hewitt 2006, 2007a] has emphasized denotational models and the Representation Theorem.

Nevertheless there are interesting co-evolutions between the Actor Model and Process Calculi. Montanari and Talcott[7] discussed whether the Actor Model and π-calculus were compatible with each other. Sangiorgi and Walker showed how Actor work on treating control structures as patterns of passing messages[8] could be modeled using the π-calculus.

Although algebraic laws have been developed for the Actor model, they do not capture the crucial property of guaranteed delivery of messages sent to Serializers. For example see the following:

See also

References
  1. Carl Hewitt, Peter Bishop and Richard Steiger. A Universal Modular Actor Formalism for Artificial Intelligence IJCAI 1973.
  2. Robin Milner. Processes: A Mathematical Model of Computing Agents in Logic Colloquium 1973.
  3. C.A.R. Hoare. Communicating Sequential Processes CACM. August, 1978.
  4. Robin Milner: Elements of interaction: Turing award lecture, Communications of the ACM, vol. 36, no. 1, pp. 78-89, January 1993. (DOI).
  5. S.D. Brookes, C.A.R. Hoare and W. Roscoe. A theory of communicating sequential processes JACM 1984.
  6. Gul Agha (1986). "Actors: A Model of Concurrent Computation in Distributed Systems". Doctoral Dissertation. MIT Press. hdl:1721.1/6952. Cite journal requires |journal= (help)
  7. Ugo Montanari and Carolyn Talcott. Can Actors and Pi-Agents Live Together? Electronic Notes in Theoretical Computer Science. 1998.
  8. Carl Hewitt. Viewing Control Structures as Patterns of Passing Messages Journal of Artificial Intelligence. June 1977.
  9. Mauro Gaspari; Gianluigi Zavattaro (May 1997). "An Algebra of Actors". Technical Report UBLCS-97-4. University of Bologna. Cite journal requires |journal= (help)
  10. M. Gaspari; G. Zavattaro (1999). "An Algebra of Actors". Formal Methods for Open Object Based Systems. Cite journal requires |journal= (help)
  11. Gul Agha; Prasanna Thati (2004). "An Algebraic Theory of Actors and Its Application to a Simple Object-Based Language" (PDF). From OO to FM (Dahl Festschrift) LNCS 2635. Archived from the original (PDF) on 2004-04-20. Retrieved 2008-01-15. Cite journal requires |journal= (help)

Further reading
  • Edsger Dijkstra. A Discipline of Programming Prentice Hall. 1976.
  • 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.
  • Irene Greif and Carl Hewitt. Actor Semantics of PLANNER-73 Conference Record of ACM Symposium on Principles of Programming Languages. January 1975.
  • Irene Greif. Semantics of Communicating Parallel Processes MIT EECS Doctoral Dissertation. August 1975.
  • Carl Hewitt and Henry Baker Actors and Continuous Functionals Proceeding of IFIP Working Conference on Formal Description of Programming Concepts. August 1–5, 1977.
  • Carl Hewitt and Henry Baker Laws for Communicating Parallel Processes IFIP-77, August 1977.
  • Henry Baker and Carl Hewitt The Incremental Garbage Collection of Processes Proceedings of the Symposium on Artificial Intelligence Programming Languages. SIGPLAN Notices 12, August 1977.
  • Aki Yonezawa Specification and Verification Techniques for Parallel Programs Based on Message Passing Semantics MIT EECS Doctoral Dissertation. December 1977.
  • Henry Baker. Actor Systems for Real-Time Computation MIT EECS Doctoral Dissertation. January 1978.
  • George Milne and Robin Milner. Concurrent processes and their syntax JACM. April, 1979.
  • 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.
  • Will Clinger. Foundations of Actor Semantics MIT Mathematics Doctoral Dissertation. June 1981.
  • J.A. Bergstra and J.W. Klop. Process algebra for synchronous communication Information and Control. 1984.
  • Eike Best. Concurrent Behaviour: Sequences, Processes and Axioms Lecture Notes in Computer Science Vol.197 1984.
  • Luca Cardelli. An implementation model of rendezvous communication Seminar on Concurrency. Lecture Notes in Computer Science 197. Springer-Verlag. 1985
  • 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.
  • 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.
  • 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.
  • 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 D. Gordon. Mobile Ambients Foundations of Software Science and Computational Structures, Maurice Nivat (Ed.), Lecture Notes in Computer Science, Vol. 1378, Springer, 1998.
  • Robin Milner. Communicating and Mobile Systems: the Pi-Calculus Cambridge University Press. 1999.
  • J. C. M. Baeten. A brief history of process algebra Theoretical Computer Science. 2005. (link valid as of 2015_26_5_0004)
  • J.C.M. Baeten, T. Basten, and M.A. Reniers. Algebra of Communicating Processes Cambridge University Press. 2005.
  • He Jifeng and C.A.R. Hoare. Linking Theories of Concurrency United Nations University International Institute for Software Technology UNU-IIST Report No. 328. July, 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.
  • Carl Hewitt. What is Commitment? Physical, Organizational, and Social COIN@AAMAS. April 27, 2006b.
  • Carl Hewitt (2007a) What is Commitment? Physical, Organizational, and Social (Revised) Pablo Noriega .et al. editors. LNAI 4386. Springer-Verlag. 2007.
  • Carl Hewitt (2007b) Large-scale Organizational Computing requires Unstratified Paraconsistency and Reflection COIN@AAMAS'07.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.