Information AboutActor Model |
| CATEGORIES ABOUT ACTOR MODEL | |
| actor modelactor model | |
| concurrency | |
| concurrent computing | |
| computational models | |
|
HISTORY See Also: Actor model early history The Actor model differs from previous models of computation in that the Actor model was inspired by the laws of Physics ( Physical Law s). It was also influenced by Lisp , Simula , Capability-based Systems , Packet Switching and early versions of Smalltalk . Development of the Actor model was "''motivated by the prospect of highly parallel computing machines consisting of dozens, hundreds or even thousands of independent microprocesors, each with its own local memory and communications processor, communicating via a high-performance communications network.''" . Since that time the motivation has broadened to include the prospect of massive concurrency due to the advent of Web Services and Many-core computer architecture. Following Hewitt's 1973 publication, Irene Greif developed an operational semantics for the Actors model as part of her doctoral research . Two years later, Henry Baker and Hewitt published a set of axiomatic laws for Actor systems . Other major milestones include William Clinger's dissertation, in 1981, introducing an Actor model Denotational Semantics based on power domains , and Gul Agha's 1985 dissertation which further developed a transition-based semantic model that was complementary to Clinger's semantics . This resulted in the full development of Actor Model Theory . Major software implementation work on the Actor model was performed by Russ Atkinson, Beppe 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 MIT. Research groups under the leadership of Chuck Seitz at Caltech and Bill Dally at MIT constructed computer architectures that further developed the message passing in the Actor model. For further discussion 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 Open Systems Laboratory, 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 with a behavior such that in response to each message received it can concurrently:
Note that there is no assumed sequence to above actions and that they could in fact be carried out in parallel. Communications with other Actors occur asynchronously (''i.e.'' the sending Actor does not wait until the message has been received before proceeding with computation). Messages are sent to specific Actors, identified by address (sometimes referred to as the Actor's “mailing address”). As a result, an Actor can only communicate with Actors for which it has an address which it might obtain in the following ways: #The address is in the message received #The address is one that the Actor already had; ''i.e.'' it was already an "acquaintance" #The address is for a just created Actor 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:
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:
APPLICATIONS The Actors model can be used as a framework for modelling, understanding, and reasoning about, a wide range of Concurrent Systems . For example:
MODELS PRIOR TO THE ACTOR MODEL The Actor model built on previous models of computation. Lambda calculus The Lambda Calculus of Alonzo Church can be viewed as the earliest Message Passing Programming Language . For example the lambda expression below implements a tree data structure when supplied with parameters for a leftSubTree and rightSubTree. When such a tree is given a parameter message "getLeft", it returns leftSubTree and likewise when given the message "getRight" it returns rightSubTree. λ(leftSubTree,rightSubTree) λ(message) ''if'' (message == "getLeft") ''then'' leftSubTree ''else if'' (message == "getRight") ''then'' rightSubTree However, the semantics of the lambda calculus were expressed using Variable Substitution in which the values of parameters were substituted into the body of an invoked lambda expression. The substitution model is unsuitable for concurrency because it does not allow the capability of Sharing of changing resources. Inspired by the lambda calculus, the Interpreter for the programming language Lisp made use of a data structure called an environment so that the values of parameters did not have to be substituted into the body of an invoked lambda expression. This allowed for sharing of the Effects of updating shared data structures but did not provide for concurrency. Simula Simula 67 pioneered using message passing for computation, motivated by discrete event simulation applications. These applications had become large and unmodular in previous simulation languages. At each time step, a large central program would have to go through and update the state of each simulation object that changed depending on the state of which ever simulation objects that it interacted with on that step. Kristen Nygaard and Ole-Johan Dahl developed the idea (first described in an IFIP workshop in 1967) of having Methods on each Object that would update its own local state based on messages from other objects. In addition they introduced a Class Structure for objects with Inheritance . Their innovations considerably improved the modularity of programs. However, Simula used coroutine control structure instead of true concurrency. Smalltalk Alan Kay was influenced by message passing in the pattern-directed invocation of Planner in developing Smalltalk-71. Hewitt was intrigued by Smalltalk-71 but was put off by the complexity of communication that included invocations with many fields including ''global'', ''sender'', ''receiver'', ''reply-style'', ''status'', ''reply'', ''operator selector'', ''etc.'' In 1972 Kay visited MIT and discussed some of his ideas for Smalltalk-72 building on the Logo work of Seymour Papert and the "little person" model of computation used for teaching children to program. However, the message passing of Smalltalk-72 was quite complex. Code in the language was viewed by the interpreter as simply a stream of tokens. As Dan Ingalls later described it: The first (token) encountered (in a program) was looked up in the dynamic context, to determine the receiver of the subsequent message. The name lookup began with the class dictionary of the current activation. Failing there, it moved to the sender of that activation and so on up the sender chain. When a binding was finally found for the token, its value became the receiver of a new message, and the interpreter activated the code for that object's class. This led some to believe that a new mathematical model of concurent computation based on message passing should be simpler than Smalltalk-72. Subsequent versions of the Smalltalk language largely followed the path of using the virtual Methods of Simula in the message passing structure of programs. However Smalltalk-72 made primitives such as integers, floating point numbers, ''etc.'' into Objects . The authors of Simula had considered making such primitives into objects but refrained largely for efficiency reasons. Java at first used the expedient of having both primitive and object versions of integers, floating point numbers, ''etc.'' The C# programming language (and later versions of Java, starting with Java 1.5) adopted the more elegant solution of using ''boxing'' and ''unboxing'', a variant of which had been used earlier in some Lisp implementations. The Smalltalk system went on to become very influential, innovating in bitmap displays, personal computing, the class browser interface, and many other ways. For details see Kay's early history of Smalltalk. Meanwhile the Actor efforts at MIT remained focused on developing the science and engineering of higher level concurrency. (See the paper by Jean-Pierre Briot for ideas that were developed later on how to incorporate some kinds of Actor concurrency into later versions of Smalltalk.) Petri nets Prior to the development of the Actor model, Petri Nets were widely used to model concurrent computation. However, they were widely acknowledged to have an important limitation: they modeled control flow but not data flow. Consequently they were not readily composable thereby limiting their modularity. Hewitt pointed out another difficulty with Petri nets: simultaneous action. ''I.e.'', the atomic step of computation in Petri nets is a transition in which tokens ''simultaneously'' disappear from the input places of a transition and appear in the output places. The physical basis of using a primitive with this kind of simultaneity seemed questionable to him. Despite these apparent difficulties, Petri nets continue to be a popular approach to modelling concurrency, and are still the subject of active research. MESSAGE PASSING SEMANTICS The Actor model is about the semantics of message passing. The unbounded nondeterminism controversy Arguably, the first concurrent programs were Interrupt Handlers . During the course of its normal operation, a computer needed to be able to receive information from outside (characters from a keyboard, packets from a network, ''etc''.). So when the information arrived execution of the computer was "interrupted" and special code called an interrupt handler was called to ''put'' the information in a Buffer where it could be subsequently later ''gotten''. This was the beginning of development of the "communicating sequential processes" paradigm in which concurrent programs were the parallel composition of sequential programs that communicated synchronously using buffers. Having parallelism with shared memory gave rise to the problem of Concurrency Control . Originally this problem was conceived as being one of Mutual Exclusion on a single computer. First Edsger Dijkstra developed Semaphores and then Tony Hoare and Per Brinch Hansen developed Monitors to solve the mutual exclusion problem. However, neither of these solutions provided a programming language construct that encapsulated access to shared resources. This encapsulation was later accomplished by the serializer construct ([Hewitt and Atkinson 1979 and 1980 ). The first models of computation (''e.g.'' Turing Machines , Post productions, the Lambda Calculus , ''etc.'') were based on mathematics and made use of a global state to represent a computational ''step''. Each computational step was from one global state of the computation to the next global state. The global state approach was continued in Automata Theory for Finite State machines and Push Down Stack machines, including their Nondeterministic versions. Such nondeterministic automata have the property of Bounded Nondeterminism ; that is, if a machine always halts when started in its initial state, then there is a bound on the number of states in which it halts. Edsger Dijkstra further developed the nondeterministic global state approach. Dijkstra's model gave rise to a controversy concerning ''unbounded nondeterminism.'' Unbounded Nondeterminism (also called ''unbounded Indeterminacy '', a title preferred by Hewitt following Niels Bohr ), is a property of Concurrency by which the amount of delay in servicing a request can become unbounded as a result of arbitration of contention for shared resources ''while still guaranteeing that the request will eventually be serviced''. Hewitt argued that the Actor model should provide the guarantee of service. In Dijkstra's model, although there could be an unbounded amount of time between the execution of sequential instructions on a computer, a (parallel) program that started out in a well defined state could terminate in only a bounded number of states 1976 . Consequently, his model could not provide the guarantee of service. Dijkstra argued that it was impossible to implement unbounded nondeterminism. Hewitt argued otherwise: there is no bound that can be placed on how long it takes a computational circuit called an ''arbiter'' to settle (see Metastability In Electronics ). Arbiters are used in computers to deal with the circumstance that computer clocks operate asynchronously with input from outside, ''e.g.'' keyboard input, disk access, network input, ''etc.'' So it could take an unbounded time for a message sent to a computer to be received and in the meantime the computer could traverse an unbounded number of states. The Actor Model features unbounded nondeterminism which was captured in a mathematical model by Will Clinger using Domain Theory . There is no global state in the Actor model. Direct communication and asynchrony 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" doesn't make a very good buffer. Messages ''put'' in the Ether don't 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. Actor creation plus addresses in messages means variable topology A natural development of the Actor model was to allow addresses in messages. Influenced by Packet Switched Networks 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 ''resumption'' (sometimes also called Continuation or Stack Frame ) along with the message. The recipient could then cause a response message to be sent to the resumption. 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. Inherently concurrent 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 . No requirement on order of message arrival Hewitt argued against adding the requirement that messages must arrive in the order in which they are sent to 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. Not sequentiality, not buffering, not synchrony and not fixed topology Robin Milner 's 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. 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. Modern, theoretical CSP ( 1985 and 2005 ) explicitly provides unbounded nondeterminism. Locality Another important characteristic of the Actor model is locality. Locality means that in processing a message: an Actor can send messages only to addresses that it receives in the message, addresses that it already had before it received the message and addresses for Actors that it creates while processing the message. (But see Synthesizing Addresses Of Actors .) Also locality means that there is no simultaneous change in multiple locations. In this way it differs from some other models of concurrency, ''e.g.'', the Petri Net model in which tokens are simultaneously removed from multiple locations and place in other locations. Compositionality Compositionality , i.e., the ability to compose Actor systems into larger ones, is an important aspect of Modularity that was developed in Gul Agha's doctoral dissertation and later by Gul Agha, Ian Mason, Scott Smith, and Carolyn Talcott. Behaviors A key innovation was the introduction of ''behavior'' specified as a mathematical function to express what an Actor does when it processes a message including specifying a new behavior to process the next message that arrives. Behaviors provided a mechanism to mathematically model the sharing in concurrency. Behaviors also freed the Actor model from implementation details, ''e.g.'', the Smalltalk-72 token stream interpreter. However, it is critical to understand that the efficient implementation of systems described by the Actor model require ''extensive'' optimization. See Actor Model Implementation for details. Relationship to mathematical logic The development of the Actor model has an interesting relationship to mathematical logic. One of the key motivations for its development was to understand and deal with the control structure issues that arose in development of the Planner Programming Language . Once the Actor model was initially defined, an important challenge was to understand the power of the model relative to Kowalski's thesis that "computation can be subsumed by deduction". Kowalski's thesis turned out to be false for the concurrent computation in the Actor model (see Indeterminacy In Computation ). This result is still somewhat controversial and it reversed previous expectations because Kowalski's thesis is true for sequential computation and even some kinds of parallel computation, ''e.g.'' the lambda calculus. Nevertheless attempts were made to extend ). Migration Migration in the Actor model is the ability of Actors 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. Security The security of Actors can be protected in the following ways:
Synthesizing addresses of Actors A delicate point in the Actor model is the ability to synthesize the address of an Actor. In some cases security can be used to prevent the synthesis of addresses (see Security ). However, if an Actor address is simply a bit string then clearly it can be synthesized although it may be difficult or even impossible to guess the address of an Actor if the bit strings are long enough. SOAP uses a URL for the address of an endpoint where an Actor can be reached. Since a URL is a character string, it can clearly be synthesized although encryption can make it impossible to guess. Synthesizing the addresses of Actors is usually modeled using mapping. The idea is to use an Actor system to perform the mapping to the actual Actor addresses. For example, on a computer the memory structure of the computer can be modeled as an Actor system that does the mapping. In the case of SOAP addresses, it's modeling the DNS and rest of the URL mapping. WHY IS THE ACTOR MODEL IMPORTANT NOW? On the 40th anniversary of the publication of . Nonlocal concurrency is being enabled by new hardware for wired and Wireless Broadband Packet Switched communications (see Wi-Fi and Ultra Wideband ). Both local and nonlocal storage capacities are growing exponentially. According to Hewitt {Link without Title} , the Actor model faces issues in computer and communications architecture, Concurrent Programming Languages , and Web Services including the following:
ACTOR RESEARCHERS Gul Agha, Beppe Attardi, Henry Baker, Will Clinger, Irene Grief, Carl Manning, Ian Mason, Ugo Montanari, Maria Simi, Scott Smith, Carolyn Talcott, Prasanna Thati, and Aki Yonezawa have made important contributions to the semantics of Actors. Important contributions to the implementation of Actors have been made by Bill Athas, Russ Atkinson, Beppe Attardi, Henry Baker, Gerry Barber, Peter Bishop, Nanette Boden, Jean-Pierre Briot, Bill Dally, Peter de Jong, Jessie Dedecker, Ken Kahn, Henry Lieberman, Carl Manning, Tom Reinhardt, Chuck Seitz, Richard Steiger, Dan Theriault, Mario Tokoro, Darrell Woelk, and Carlos Varela. SEE ALSO
REFERENCES
|
|
|