Citizendia

In computer science, the Actor model 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. Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their Parallel computing is a form of computation in which many instructions are carried out simultaneously operating on the principle that large problems can often The Actor model originates in a 1973 paper by Carl Hewitt, Peter Bishop, and Richard Steiger. Carl E Hewitt is Associate Professor Emeritus in the Electrical Engineering and Computer Science department at the Massachusetts Institute of Technology [1] It has been used both as a framework for a theoretical understanding of concurrency, and as the theoretical basis for several practical implementations of concurrent systems. In Theoretical computer science, Actor model theory concerns theoretical issues for the Actor model. In Computer science, concurrency is a properties of system in which several Computational processes are executing at the same time and potentially interacting In Computer science, Actor model implementation concerns implementation issues for the Actor model. In Computer science, concurrency is a properties of system in which several Computational processes are executing at the same time and potentially interacting The relationship of the model to other work is discussed in Indeterminacy in concurrent computation and Actor model and process calculi. Indeterminacy in concurrent computation is concerned with the effects of Indeterminacy in Concurrent computation. In Computer science, the '''Actor model''' and '''process calculi''' are two closely related approaches to the modelling of concurrent digital computation

Contents

History

Main article: History of the Actor model

Unlike previous models of computation, the Actor model was inspired by physical laws. In Computer science, the Actor model, first published in 1973, is a mathematical model of Concurrent computation. A physical law or scientific law is a Scientific generalization based on empirical Observations of physical behavior (i It was also influenced by the programming languages Lisp, Simula and early versions of Smalltalk, as well as capability-based systems and packet switching. Lisp (or LISP) is a family of Computer Programming languages with a long history and a distinctive fully parenthesized syntax Simula is a name for two programming languages Simula I and Simula 67 developed in the 1960s at the Norwegian Computing Center in Oslo, by Ole-Johan Dahl Smalltalk is an object-oriented, dynamically typed, reflective programming language. Capability-based security is a concept in the design of Secure computing systems Packet switching is a network communications method that splits data traffic (digital representations of text sound or video data into chunks called packets, that are then 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 rekindled interest in the Actor model. A multi-core processor (or chip-level multiprocessor, CMP) combines two or more independent cores into a single package composed of a single Integrated

Following Hewitt, Bishop, and Steiger's 1973 publication, Irene Greif developed an operational semantics for the Actors model as part of her doctoral research. In Computer science, operational semantics is a way to give meaning to Computer programs in a mathematically rigorous way [3] Two years later, Henry Baker and Hewitt published a set of axiomatic laws for Actor systems. Henry G Baker (fl late 20th century is a computer scientist who has made contributions in garbage collection, Functional programming languages and Linear logic [4] Other major milestones include William Clinger's dissertation, in 1981, 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. The Denotational semantics of the Actor model is the subject of denotational Domain theory for Actors. Gul Agha is a Professor in the Department of Computer Science at the University of Illinois at Urbana-Champaign, and Director of the Open Systems Laboratory [5] This resulted in the full development of actor model theory. In Theoretical computer science, Actor model theory concerns theoretical issues for the Actor model.

Major software implementation work was done 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 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. The California Institute of Technology (commonly referred to as Caltech) is a private, Coeducational research university located in Pasadena See Actor model implementation. In Computer science, Actor model implementation concerns implementation issues for the Actor model.

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 Open Systems Laboratory, University of Paris 6, University of Pisa, University of Tokyo Yonezawa Laboratory and elsewhere. or is a major national university in Kyoto, Japan. It is the second oldest university in Japan and formerly one of the Imperial Universities of SRI International, based in the United States is one of the world's largest contract Research institutes. Leland Stanford Junior University, commonly known as Stanford University or simply Stanford, is a private Research university located in This article is about the flagship campus For other uses and locations of University of Illinois, see University of Illinois (disambiguation The University of The historic University of Paris (Université de Paris first appeared in the second half of the 13th century The University of Pisa ( Italian Università di Pisa) is one of the most renowned Italian universities The, abbreviated as, is a major Research university located in Tokyo, Japan.

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. Object-oriented programming (OOP is a Programming paradigm that uses " objects " and their interactions to design applications and computer programs

An actor is a computational entity that, in response to a message it receives, can concurrently:

There is no assumed sequence to the above actions and they could be carried out in parallel.

Communications among actors occur asynchronously: that is, the sending actor does not wait until the message is received before proceeding with computation.

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 just 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. In Computer science, message passing is a form of communication used in Parallel computing, Object-oriented programming, and Interprocess communication

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. In Computer science, operational semantics is a way to give meaning to Computer programs in a mathematically rigorous way In Computer science, denotational semantics is an approach to formalizing the meanings of Programming languages by constructing mathematical objects (called In Computer science, concurrency is a properties of system in which several Computational processes are executing at the same time and potentially interacting For example:

Models prior to the Actor model

The Actor model builds on previous models of computation.

Lambda calculus

The lambda calculus of Alonzo Church can be viewed as the earliest message passing programming language. In Mathematical logic and Computer science, lambda calculus, also written as λ-calculus, is a Formal system designed to investigate function Alonzo Church ( June 14, 1903 – August 11, 1995) was an American Mathematician and logician In Computer science, message passing is a form of communication used in Parallel computing, Object-oriented programming, and Interprocess communication A programming language is an Artificial language that can be used to write programs which control the behavior of a machine particularly a Computer. 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. Mathematical logic is a subfield of Logic and Mathematics with close connections to Computer science and Philosophical logic. The substitution model is unsuitable for concurrency because it does not allow the capability of sharing of changing resources. Sharing is the joint use of a resource or space In its narrow sense it refers to joint or alternating use of an inherently finite good such as a common pasture or a Timeshared 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. In Computer science, an interpreter normally means a Computer program that executes, i Lisp (or LISP) is a family of Computer Programming languages with a long history and a distinctive fully parenthesized syntax This allowed for sharing of the effects of updating shared data structures but did not provide for concurrency. In Computer science, a function or expression is said to produce a side effect if it modifies some state in addition to returning a value

Simula

Simula 67 pioneered using message passing for computation, motivated by discrete event simulation applications. Simula is a name for two programming languages Simula I and Simula 67 developed in the 1960s at the Norwegian Computing Center in Oslo, by Ole-Johan Dahl 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. Kristen Nygaard ( August 27, 1926 – August 10, 2002) was a Norwegian Mathematician, Computer programming Ole-Johan Dahl ( October 12, 1931 &ndash June 29 2002) was a Norwegian Computer scientist and is considered to be one of In Object-oriented programming, the term method refers to a Subroutine that is exclusively associated either with a class (called class methods In its simplest embodiment an object is an allocated region of storage In addition they introduced a class structure for objects with inheritance. In Object-oriented programming, a class is a Programming language construct that is used as a blueprint to create objects This blueprint includes attributes In Object-oriented programming, inheritance is a way to form new classes (instances of which are called objects using classes that have already been defined Their innovations considerably improved the modularity of programs.

However, Simula used coroutine control structure instead of true concurrency. In Computer science, coroutines are program components that generalize Subroutines to allow multiple entry points and suspending and resuming of execution at certain

Smalltalk

Alan Kay was influenced by message passing in the pattern-directed invocation of Planner in developing Smalltalk-71. Alan Curtis Kay (born May 17, 1940) is an American Computer scientist, known for his early pioneering work on Object-oriented programming Planner (often seen in publications as "PLANNER" although it is not an acronym is a Programming language designed by Carl Hewitt at MIT, and Smalltalk is an object-oriented, dynamically typed, reflective programming language. 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. Logo is a Computer programming language used for Functional programming. Seymour Papert (born February 29, 1928 in Pretoria South Africa) is an MIT Mathematician, computer scientist, and 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. Daniel Henry Holmes Ingalls Jr is a pioneer of object-oriented Computer programming and the principal architect, designer and implementor of 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 concurrent 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. In Object-oriented programming, the term method refers to a Subroutine that is exclusively associated either with a class (called class methods However Smalltalk-72 made primitives such as integers, floating point numbers, etc. into objects. In its simplest embodiment an object is an allocated region of storage 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. C# (pronounced C Sharp is a Multi-paradigm 5) adopted the more elegant solution of using boxing and unboxing, a variant of which had been used earlier in some Lisp implementations. In Computer science, an object type (aka wrapping object is a Datatype which is used in Object-oriented programming to wrap a non-object Lisp (or LISP) is a family of Computer Programming languages with a long history and a distinctive fully parenthesized syntax

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 The Early History of Smalltalk[12]. 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. A Petri net (also known as a place/transition net or P/T net) is one of several Mathematical Modeling languages for the description of discrete 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.

Unbounded nondeterminism controversy

Arguably, the first concurrent programs were interrupt handlers. An interrupt handler, also known as an interrupt service routine ( ISR) is a callback subroutine in an Operating system or Device driver 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 gotten. In Computing, a buffer is a region of memory used to temporarily hold Data while it is being moved from one place to another

In the early 1960s, interrupts began to be used to simulate the concurrent execution of several programs on a single processor. [13] Having concurrency with shared memory gave rise to the problem of concurrency control. In Computing, shared memory is a memory that may be simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies In Computer science, especially in the fields of Computer programming (see also Concurrent programming, Parallel programming) Operating systems Originally, this problem was conceived as being one of mutual exclusion on a single computer. Mutual exclusion (often abbreviated to mutex) Algorithms are used in Concurrent programming to avoid the simultaneous use of a common resource such as a Edsger Dijkstra developed semaphores and later, between 1971 and 1973[14], Tony Hoare[15] and Per Brinch Hansen[16] developed monitors to solve the mutual exclusion problem. Edsger Wybe Dijkstra ( May 11, 1930 &ndash August 6, 2002; ˈɛtsxər ˈwibə ˈdɛɪkstra was a Dutch computer scientist For other uses see Semaphore. A semaphore, in computer science is a protected Variable (an entity storing a value or Abstract Year 1971 ( MCMLXXI) was a Common year starting on Friday (link will display full calendar of the 1971 Gregorian calendar. Year 1973 ( MCMLXXIII) was a Common year starting on Monday (link will display full calendar of the 1973 Gregorian calendar. Sir Charles Antony Richard Hoare ( Tony Hoare or CAR Hoare, born January 11, 1934) is a British computer scientist, probably Per Brinch Hansen (November 13 1938 - July 31 2007 was a Danish-American Computer scientist known for Concurrent programming theory A monitor is an approach to synchronize two or more computer tasks that use a shared resource usually a hardware device or a set of Variables With monitor-based 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 1977, 1979] and [Atkinson 1980]).

The first models of computation (e. g. Turing machines, Post productions, the lambda calculus, etc. Turing machines are basic abstract symbol-manipulating devices which despite their simplicity can be adapted to simulate the logic of any Computer Algorithm In Mathematical logic and Computer science, lambda calculus, also written as λ-calculus, is a Formal system designed to investigate function ) were based on mathematics and made use of a global state to represent a computational step (later generalized in [McCarthy and Hayes 1969] and [Dijkstra 1976] see Event orderings versus global state). In Computer science, the Actor model, first published in 1973, is a mathematical model of Concurrent computation. 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. In Computer science, a stack machine is a Model of computation in which the computer's memory takes the form of one or more stacks The term also refers 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. In Computer science, unbounded nondeterminism or unbounded indeterminacy is a property of concurrency by which the amount of delay in servicing a request

Edsger Dijkstra further developed the nondeterministic global state approach. Edsger Wybe Dijkstra ( May 11, 1930 &ndash August 6, 2002; ˈɛtsxər ˈwibə ˈdɛɪkstra was a Dutch computer scientist Dijkstra's model gave rise to a controversy concerning unbounded nondeterminism. Unbounded nondeterminism (also called unbounded indeterminacy), 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. In Computer science, unbounded nondeterminism or unbounded indeterminacy is a property of concurrency by which the amount of delay in servicing a request In Computer science, concurrency is a properties of system in which several Computational processes are executing at the same time and potentially interacting 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 [Dijkstra 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 electronic devices that allocate access to shared resources Metastability in electronics is the ability of a non-equilibrium electronic state to persist for a long (and theoretically unlimited period of time (see Asynchronous circuit 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. Domain theory is a branch of Mathematics that studies special kinds of Partially ordered sets (posets commonly called domains. [2] There is no global state in the Actor model.

Direct communication and asynchrony

Messages in the Actor model are not necessarily buffered. This 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". Also, messages in the Actor model are simply sent (like packets in IP); there is no requirement for a synchronous handshake with the recipient. In Information technology, a packet is a formatted unit of Data carried by a Packet mode Computer network. The Internet Protocol ( IP) is a protocol used for communicating data across a Packet-switched Internetwork using the Internet Protocol

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 [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. Packet switching is a network communications method that splits data traffic (digital representations of text sound or video data into chunks called packets, that are then 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. In Computing, a continuation represents the rest of the computation given a point in the computation In Computer science, a call stack is a dynamic stack data structure which stores information about the active Subroutines of a Computer program 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. In Theoretical computer science, Actor model theory concerns theoretical issues for the Actor model.

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. FIFO is an Acronym for First In First Out, an abstraction in ways of organizing and manipulation of data relative to time and prioritization 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. Packet switching is a network communications method that splits data traffic (digital representations of text sound or video data into chunks called packets, that are then 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.

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. In Computer science, the Actor model is a mathematical model of Concurrent computation that treats "actors" as the universal primitives of concurrent )

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 placed in other locations. A Petri net (also known as a place/transition net or P/T net) is one of several Mathematical Modeling languages for the description of discrete

Composing actors

The idea of composing Actor systems into larger ones is an important aspect of modularity that was developed in Gul Agha's doctoral dissertation,[5], developed later by Gul Agha, Ian Mason, Scott Smith, and Carolyn Talcott. Modular programming is a software design technique that increases the extent to which software is composed from separate parts called modules [6]

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. In Computer science, Actor model implementation concerns implementation issues for the Actor model.

Representation theorem

There is a representation theorem for concurrent systems in the Actor model by which the mathematical denotation denoted by a system S is found by constructing increasingly better approximations from an initial behavior called ⊥S using a behavior approximating function progressionS to construct a denotation (meaning ) for S as follows [Hewitt 2006b; Clinger 1981]:

DenoteS ≡ ∨i∈ω progressionSi(⊥S).

Since the Actor model is very general, the Representation Theorem applies to the other main stream models as well. For example it applies to petri net and process calculi models via a two-phase commit protocol protocol to handle the synchronization. A Petri net (also known as a place/transition net or P/T net) is one of several Mathematical Modeling languages for the description of discrete In Computer science, the process calculi (or process algebras) are a diverse family of related approaches to formally modelling Concurrent systems Process In Computer networking and Databases the two-phase commit protocol (2PC is a Distributed algorithm that lets all nodes in a Distributed system

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. Planner (often seen in publications as "PLANNER" although it is not an acronym is a Programming language designed by Carl Hewitt at MIT, and 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 concurrent computation). Indeterminacy in concurrent computation is concerned with the effects of Indeterminacy in Concurrent 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 logic programming to concurrent computation. Logic programming is in its broadest sense the use of mathematical logic for computer programming However, Hewitt and Agha [1991] claimed that the resulting systems were not deductive in the following sense: computational steps of the concurrent logic programming systems do not follow deductively from previous steps (see Indeterminacy in concurrent computation). Indeterminacy in concurrent computation is concerned with the effects of Indeterminacy in Concurrent computation.

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 faithfulness 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. An operating system (commonly abbreviated OS and O/S) is the software component of a Computer system that is responsible for the management and coordination Capability-based security is a concept in the design of Secure computing systems A digital signature or digital signature scheme is a type of asymmetric cryptography used to simulate the security properties of a handwritten Signature In some cases security can be used to prevent the synthesis of addresses (see Security). In Computer science, the Actor model is a mathematical model of Concurrent computation that treats "actors" as the universal primitives of concurrent However, if an Actor address is simply a bit string then clearly it can be synthesized although it may be difficult or even infeasible 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. SOAP (see below for name and origins is a protocol for exchanging XML -based messages over Computer networks normally using Uniform Resource Locator is an URI which also specifies where the identified resource is available and the protocol for retrieving it Since a URL is a character string, it can clearly be synthesized although encryption can make it impossible to guess. Uniform Resource Locator is an URI which also specifies where the identified resource is available and the protocol for retrieving it

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. SOAP (see below for name and origins is a protocol for exchanging XML -based messages over Computer networks normally using The Domain Name System (DNS is a hierarchical naming system for computers services or any resource participating in the Internet. Uniform Resource Locator is an URI which also specifies where the identified resource is available and the protocol for retrieving it

Contrast with other models of message-passing concurrency

Robin Milner's initial published work on concurrency[17] was also notable in that it was not based on composing sequential processes. Robin Milner FRS (born 1934 is a prominent British Computer scientist. His work differed from the Actor model because it was based on a fixed number of processes of fixed topology communicating numbers and strings using synchronous communication. The original Communicating Sequential Processes model[18] published by Tony Hoare differed from the Actor model because it was based on the parallel composition of a fixed number of sequential processes connected in a fixed topology, and communicating using synchronous message-passing based on process names (see Actor model and process calculi history). In Computer science, Communicating Sequential Processes ( CSP) is a formal language for describing Patterns of Interaction in Concurrent Sir Charles Antony Richard Hoare ( Tony Hoare or CAR Hoare, born January 11, 1934) is a British computer scientist, probably The Actor model and process calculi share an interesting history and co-evolution Later versions of CSP abandoned communication based on process names in favor of anonymous communication via channels, an approach also used in Milner's work on the Calculus of Communicating Systems and the π-calculus. The Calculus of Communicating Systems (CCS is a Process calculus introduced by Robin Milner in around 1980 In Theoretical computer science, the \pi-calculus is a Process calculus originally developed by Robin Milner, Joachim Parrow and

These early models by Milner and Hoare both had the property of bounded nondeterminism. Modern, theoretical CSP ([Hoare 1985] and [Roscoe 2005]) explicitly provides unbounded nondeterminism. In Computer science, Communicating Sequential Processes ( CSP) is a formal language for describing Patterns of Interaction in Concurrent

Current importance

40 years after the publication of Moore's Law, hardware development is furthering local and nonlocal massive concurrency. Moore's law describes an important trend in the History of computer hardware. Local concurrency is enabled by new hardware for 64-bit multi-core (Platform 2015 Unveiled at IDF Spring 2005) microprocessors, multi-chip modules, and high performance interconnect. '64-bit' CPUs have existed in Supercomputers since the 1960s and in RISC -based workstations and servers since the early 1990s. An electrical connection between discrete points allows the flow of Electrons ( Electric current) Nonlocal concurrency is being enabled by new hardware for wired and wireless broadband packet switched communications (see Wi-Fi and Ultra wideband). Wireless communication is the transfer of information over a distance without the use of electrical conductors or " Wires quot The term broadband can have different meanings in different contexts Packet switching is a network communications method that splits data traffic (digital representations of text sound or video data into chunks called packets, that are then Wi-Fi (ˈwaɪfaɪ is the trade name for the popular wireless technology used Ultra-wideband (aka UWB, ultra-wide band, ultraband, etc is a radio technology that can be used at very low energy levels for short-range high-bandwidth Both local and nonlocal storage capacities are growing exponentially.

According to Hewitt [2006], the Actor model faces issues in computer and communications architecture, concurrent programming languages, and Web Services including the following:

Many of the ideas introduced in the Actor model are now also finding application in multi-agent systems for these same reasons [Hewitt 2006b 2007b]. A multi-agent system ( MAS) is a system composed of multiple interacting Intelligent agents Multi-agent systems can be used to solve problems which are difficult or The key difference is that agent systems (in most definitions) impose extra constraints upon the Actors, typically requiring that they make use of commitments and goals.

Actor researchers

Important contributions to the semantics of Actors have been made by: 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.

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

Languages

Languages employing the actor model:

References

  1. ^ Carl Hewitt; Peter Bishop and Richard Steiger (1973). Dataflow is a term used in Computing, and may have various shades of meaning Special relativity (SR (also known as the special theory of relativity or STR) is the Physical theory of Measurement in Inertial The relativity of simultaneity is the concept that simultaneity is not absolute but dependent on the observer Quantum mechanics is the study of mechanical systems whose dimensions are close to the Atomic scale such as Molecules Atoms Electrons In Theoretical computer science, Actor model theory concerns theoretical issues for the Actor model. A multi-agent system ( MAS) is a system composed of multiple interacting Intelligent agents Multi-agent systems can be used to solve problems which are difficult or Traditionally the term neural network had been used to refer to a network or circuit of biological neurons. In Computer science, the Scientific Community Metaphor is one way of understanding scientific communities. E is an Object-oriented programming language for secure Distributed computing, created by Mark S Erlang is a general-purpose concurrent Programming language and Runtime system Gambit, also called Gambit-C is a Free software Scheme Implementation, consisting of a Scheme interpreter, and a Compiler which Io is a pure object-oriented programming language inspired by Smalltalk, Self, Lua, Lisp, Act1 Other 'Ptolemy Projects' exist including a medical one named for Ptolemy I Soter. Rebeca ( Re active O b j ec ts L a nguage is an actor-based language with a formal foundation designed in an effort to The SALSA programming language ( S imple A ctor L anguage S ystem and A rchitecture is an actor-oriented programming language Scala ( Scalable Language) is a multi-paradigm Programming language designed to integrate features of Object-oriented programming and "A Universal Modular Actor Formalism for Artificial Intelligence". . IJCAI
  2. ^ a b c d William Clinger (June 1981). William Floyd "Bill" Clinger Jr (born April 4, 1929) was a Republican member of the U "Foundations of Actor Semantics". Mathematics Doctoral Dissertation. . MIT
  3. ^ a b Irene Greif (August 1975). "Semantics of Communicating Parallel Processes". EECS Doctoral Dissertation. . MIT
  4. ^ a b Henry Baker; Carl Hewitt (August 1977). Henry Baker may refer to Henry Baker (naturalist (1698–1774 English Henry Baker (computer scientist (fl Carl E Hewitt is Associate Professor Emeritus in the Electrical Engineering and Computer Science department at the Massachusetts Institute of Technology "Laws for Communicating Parallel Processes". . IFIP
  5. ^ a b c Gul Agha (1986). "Actors: A Model of Concurrent Computation in Distributed Systems". Doctoral Dissertation. . MIT Press
  6. ^ a b Gul Agha; Ian Mason, Scott Smith, and Carolyn Talcott (January 1993). "A Foundation for Actor Computation". Journal of Functional Programming.  
  7. ^ Carl Hewitt (April 27, 2006). Carl E Hewitt is Associate Professor Emeritus in the Electrical Engineering and Computer Science department at the Massachusetts Institute of Technology "What is Commitment? Physical, Organizational, and Social". . COIN@AAMAS
  8. ^ Mauro Gaspari; Gianluigi Zavattaro (May 1997). "An Algebra of Actors". Technical Report UBLCS-97-4. . University of Bologna
  9. ^ M. Gaspari; G. Zavattaro (1999). "An Algebra of Actors". . Formal Methods for Open Object Based Systems
  10. ^ Gul Agha; Prasanna Thati (2004). Gul Agha may refer to Gul Agha Sherzai, Governor of Nangarhar province in Afghanistan Gul Agha (computer scientist, American computer "An Algebraic Theory of Actors and Its Application to a Simple Object-Based Language". . From OO to FM (Dahl Festschrift) LNCS 2635
  11. ^ John Darlington; Y. K. Guo (1994). "Formalizing Actors in Linear Logic". . International Conference on Object-Oriented Information Systems
  12. ^ Kay, Alan (March 1993). Alan Curtis Kay (born May 17, 1940) is an American Computer scientist, known for his early pioneering work on Object-oriented programming "The Early History of Smalltalk". ACM SIGPLAN 28 (3): 69-75. doi:10.1145/155360.155364. A digital object identifier ( DOI) is a permanent identifier given to an Electronic document.  
  13. ^ Brinch-Hansen, Per (2002). The Origins of Concurrent Programming: From Semaphores to Remote Procedure Calls. Springer. ISBN 978-0387954011.  
  14. ^ Monitors and Concurrent Pascal: A Personal History, Per Brinch Hansen, Comm. ACM 1996, pp 121-172
  15. ^ Monitors: An Operating System Structuring Concept, Comm. ACM Vol. 17, No. 10. October 1974, pp. 549-557
  16. ^ Operating System Principles, Brinch Hansen, P. , Prentice-Hall, July 1973.
  17. ^ Robin Milner. Processes: A Mathematical Model of Computing Agents in Logic Colloquium 1973.
  18. ^ C. A. R. Hoare. Communicating sequential processes CACM. August 1978.
  19. ^ Henry Lieberman. "A Preview of Act 1". . MIT AI memo 625
  20. ^ Henry Lieberman. "Thinking About Lots of Things at Once without Getting Confused: Parallelism in Act 1". . MIT AI memo 626
  21. ^ Philipp Haller and Martin Odersky. "Event-Based Programming without Inversion of Control". . Proc. JMLC 2006
  22. ^ Philipp Haller and Martin Odersky. "Actors that Unify Threads and Events". . Technical report LAMP 2007

Further reading

External links

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic