Actor Mdel

Actor model

From Wikipedia, the free encyclopedia

Jump to: navigation, search

This article may require cleanup to meet Wikipedia's quality standards. No cleanup reason has been specified. Please help improve this article if you can. (June 2010)

The actor model in computer science is a mathematical model of concurrent computation that 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. The actor model originated in 1973.^[1] It has been used both as a framework for a theoretical understanding of computation, and as the theoretical basis for several practical implementations of concurrent systems. The relationship of the model to other work is discussed in Indeterminacy in concurrent computation and Actor model and process calculi.

Contents

• 1 History
• 2 Fundamental concepts
• 3 Formal systems
• 4 Applications
• 5 Message-passing semantics
  • 5.1 Unbounded nondeterminism controversy
  • 5.2 Direct communication and asynchrony
  • 5.3 Actor creation plus addresses in messages means variable topology
  • 5.4 Inherently concurrent
  • 5.5 No requirement on order of message arrival
  • 5.6 Locality
  • 5.7 Composing Actor Systems
  • 5.8 Behaviors
  • 5.9 Modeling other concurrency systems
  • 5.10 Computational Representation Theorem
  • 5.11 Relationship to logic programming
  • 5.12 Migration
  • 5.13 Security
  • 5.14 Synthesizing addresses of actors
  • 5.15 Contrast with other models of message-passing concurrency
• 6 Influence
  • 6.1 Theory
  • 6.2 Practice
• 7 Current issues
• 8 Early Actor researchers
• 9 Programming with Actors
  • 9.1 Early Actor programming languages
  • 9.2 Later Actor programming languages
  • 9.3 Actor libraries and frameworks
• 10 See also
• 11 References
• 12 Further reading
• 13 External links
  • 13.1 Videos
  • 13.2 Articles
  • 13.3 Procedural Libraries

History

Main article: History of the Actor model

According to Carl Hewitt, unlike previous models of computation, the Actor model was inspired by physics including general relativity and quantum mechanics. It was also influenced by the programming languages Lisp, Simula and early versions of Smalltalk, as well as capability-based systems and packet switching. Its development was "motivated by the prospect of highly parallel computing machines consisting of dozens, hundreds or even thousands of independent microprocessors, each with its own local memory and communications processor, communicating via a high-performance communications network."^[2] Since that time, the advent of massive concurrency through multi-core computer architectures has revived interest in the Actor model.
Following Hewitt, Bishop, and Steiger's 1973 publication, Irene Greif developed an operational semantics for the Actors model as part of her doctoral research.^[3] Two years later, Henry Baker and Hewitt published a set of axiomatic laws for Actor systems.^[4] Other major milestones include William Clinger's 1981 dissertation introducing a denotational semantics based on power domains ^[2] and Gul Agha's 1985 dissertation which further developed a transition-based semantic model complementary to Clinger's.^[5] This resulted in the full development of actor model theory.
Major software implementation work was done by Russ Atkinson, Giuseppe Attardi, Henry Baker, Gerry Barber, Peter Bishop, Peter de Jong, Ken Kahn, Henry Lieberman, Carl Manning, Tom Reinhardt, Richard Steiger and Dan Theriault in the Message Passing Semantics Group at Massachusetts Institute of Technology (MIT). Research groups led by Chuck Seitz at California Institute of Technology (Caltech) and Bill Dally at MIT constructed computer architectures that further developed the message passing in the model. See Actor model implementation.
Research on the Actor model has been carried out at Caltech Computer Science, Kyoto University Tokoro Laboratory, MCC, MIT Artificial Intelligence Laboratory, SRI, Stanford University, University of Illinois at Urbana-Champaign,^[6] Pierre and Marie Curie University (University of Paris 6), University of Pisa, University of Tokyo Yonezawa Laboratory and elsewhere.

Fundamental concepts

The Actor model adopts the philosophy that everything is an actor. This is similar to the everything is an object philosophy used by some object-oriented programming languages, but differs in that object-oriented software is typically executed sequentially, while the Actor model is inherently concurrent.
An actor is a computational entity that, in response to a message it receives, can concurrently:

• send a finite number of messages to other actors;
• create a finite number of new actors;
• designate the behavior to be used for the next message it receives.

There is no assumed sequence to the above actions and they could be carried out in parallel.
Decoupling the sender from communications sent was a fundamental advance of the Actor model enabling asynchronous communication and control structures as patterns of passing messages.^[7]
Recipients of messages are identified by address, sometimes called "mailing address". Thus an actor can only communicate with actors whose addresses it has. It can obtain those from a message it receives, or if the address is for an actor it has itself created.
The Actor model is characterized by inherent concurrency of computation within and among actors, dynamic creation of actors, inclusion of actor addresses in messages, and interaction only through direct asynchronous message passing with no restriction on message arrival order.

Formal systems

Over the years, several different formal systems have been developed which permit reasoning about systems in the Actor model. These include:

• Operational semantics^[3][8]
• Laws for Actor systems^[4]
• Denotational semantics^[2][9]
• Transition semantics^[5]

There are also formalisms that are not fully faithful to the Actor model in that they do not formalize the guaranteed delivery of messages including the following (See Attempts to relate Actor semantics to algebra and linear logic):

• Several different Actor algebras^[10][11][12]
• Linear logic^[13]