Actor model and process calculi history

From Wikipedia, the free encyclopedia

You have new messages (last change).

The Actor model and process calculi share an interesting history and coevolution.

Contents

[edit] Early development of the Actor model

The Actor model, first published in [Hewitt et al. 1973], 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.

[edit] No buffering

Messages in the Actor model are not necessarily buffered which was a sharp break with previous approaches to models of concurrent computation. The lack of buffering caused a great deal of misunderstanding at the time of the development of the Actor model and is still a controversial issue. Some researchers argued that the messages are buffered in the "ether" or the "environment". However, the "ether" does not make a very good buffer. Messages put in the ether do not stay until they are gotten! Also messages in the Actor model are simply sent (like packets in IP) there is no requirement for a synchronous handshake with the recipient of the message.

[edit] Dynamic topology

A natural development of the Actor model was to allow addresses in messages. Influenced by packet switched networks [1961 and 1964], Hewitt proposed the development of a new model of concurrent computation in which communications would not have any required fields at all: they could be empty. Of course, if the sender of a communication desired a recipient to have access to addresses which the recipient did not already have, the address would have to be sent in the communication.

A computation might need to send a message to a recipient from which it would later receive a response. The way to do this is to send a communication which has the message along with the address of another Actor called the customer (sometimes also called continuation or stack frame) along with the message. The recipient could then cause a response message to be sent to the customer.

Actor creation plus the inclusion of the addresses of Actors in messages means that Actors have a potentially variable topology in their relationship to one another much as the objects in Simula also had a variable topology in their relationship to one another.

[edit] Arrival ordering not necessarily same as sending order

Hewitt argued against making the requirement messages must arrive in the order that they are sent a requirement of the Actor model. If output message ordering is desired then it can be modeled by a queue Actor that provides this functionality. Such a queue Actor would queue the messages that arrived so that they could be retrieved in FIFO order. So if an Actor X sent a message M1 to an Actor Y and in response to a subsequent message that X received, it sent another message M2 to Y, there is no requirement that M1 arrives at Y before M2.

In this respect the Actor model mirrors packet switching systems which do not guarantee that packets must be received in the order sent. Not providing the order of delivery guarantee allows packet switching to buffer packets, use multiple paths to send packets, resend damaged packets, and to provide other optimizations.

For example, Actors are allowed to pipeline the processing of messages. What this means is that in the course of processing a message M1, an Actor can designate the behavior to be used to process the next message, and then in fact begin processing another message M2 before it has finished processing M1. Just because an Actor is allowed to pipeline the processing of messages does not mean that it must pipeline the processing. Whether a message is pipelined is an engineering tradeoff. How would an external observer know whether the processing of a message by an Actor has been pipelined? There is no ambiguity in the definition of an Actor created by the possibility of pipelining. Of course, it is possible to perform the pipeline optimization incorrectly in some implementations, in which case unexpected behavior may occur.

[edit] Milner's early publications

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 [1973] initial published work on concurrency was also notable in that it was not based on composing sequential processes. His work differed from the Actor model because it was based on a fixed number of processes of fixed topology communicating using synchronous buffered communication.

[edit] Hoare's early publications

The original Communicating Sequential Processes model published by Tony Hoare [1978] differed from the Actor model because it was based on the parallel composition of a fixed number of sequential processes of fixed topology communicating using synchronous buffered communication.

These early models by Milner and Hoare both had the property of bounded nondeterminism as opposed to the unbounded nondeterminism in the Actor model.

[edit] Process calculi and Actor model

[edit] Milner, et al.

In his Turing lecture (Milner 1993), Milner remarked as follows:

Now, the pure lambda-calclus 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 expession ... 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...

[edit] Hoare, et al.

Tony Hoare, Stephen Brookes, and A. W. Roscoe [1984] developed and refined the theory of CSP into its modern form. 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.

[edit] Further coevolution

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

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

[edit] 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.
  • 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 Processes 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.
  • 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.
  • Eike Best. Concurrent Behaviour: Sequences, Processes and Axioms Lecture Notes in Computer Science Vol.197 1984.
  • S.D. Brookes, C.A.R. Hoare and W. Roscoe. A theory of communicating sequential processes JACM 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.
  • Eike Best and R.Devillers. Sequential and Concurrent Behaviour in Petri Net Theory Theoretical Computer Science Vol.55/1. 1987.
  • 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. Some directions in concurrency theory International Conference on Fifth Generation Computer Systems. 1988.
  • Carl Hewitt. Knowledge processing International Conference on Fifth Generation Computer Systems. 1988.
  • 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.
  • Frederick Knabe. A Distributed Protocol for Channel-Based Communication with Choice PARLE 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.
  • -  Robin Milner: Elements of interaction: Turing award lecture, Communications of the ACM, vol. 36, no. 1, pp. 78-89, January 1993. (DOI).
  • 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.
  • Q. Zhang, W. Li and S. Chen. Technology of Object-Oriented Languages and Systems Tools. 1998.
  • Mauro Gaspari and Gianluigi Zavattaro. An Algebra of Actors Formal Methods for Open Object Based Systems. 1999.
  • Robin Milner. Communicating and Mobile Systems: the Pi-Calculus Cambridge University Press. 1999.
  • Gul Agha. The relation between problems in large-scale concurrent systems and distributed databases International Symposium on Databases for Parallel and Distributed Systems. Austin, Texas. 2000.
  • Pawel Wojciechowski. Nomadic Pict: Language and Infrastructure Design for Mobile Computation Cambridge University Ph.D. thesis. Technical Report 492. June 2000.
  • Davide Sangiorgi and David Walker. The Pi-Calculus : A Theory of Mobile Processes Cambridge University Press. 2001.
  • Asis Unyapoth. Nomadic Pi Calculi: Expressing and Verifying Infrastructure for Mobile Computation University of Cambridge Ph.D. thesis. Technical Report 514. June 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.
  • 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.
  • Bill Roscoe. The Theory and Practice of Concurrency Prentice-Hall. 2005.
Retrieved from "http://en.wikipedia.org../../../a/c/t/Actor_model_and_process_calculi_history.html"