A general model of concurrent computation developed by Carl Hewitt, Henry Baker and Gul Agha (also "actor model"). Several Actor Languages are based on this model.
Actors are autonomous and concurrent objects which execute asynchronously. The actors model provides flexible mechanisms for building parallel and distributed software systems.
"Laws for Communicating Parallel Processes", C. Hewitt et al, IFIP 77, pp. 987-992, N-H 1977
"Actors And Continuous Functionals", C. Hewitt, and H. Baker, MIT-LCS-TR-194, 1978 www.lcs.mit.edu 
The actors model is closely related to the Object Capability Model - the locality laws defined in, e.g. "Actors and Continuous Functionals", correspond directly to some of the requirements for object capabilities. (This does not necessarily mean that all actor languages are capability secure, but pure actor languages necessarily are.) This may help to revive interest in the actors model in the security community. The connection was recognised in the acknowledgements at the end of "Actors and Continuous Functionals":
The design of Smalltalk built on the class instance distinction of Simula, the separation of goal language from method language in Planner, the control ideas in David Fisher's thesis, and Seymour Papert's "little person" model of computation. We [i.e. Baker and Hewitt] have worked to construct a theoretical model that encompasses these ideas in addition to similar abstractions which have been developed in lambda calculus languages and for operating systems such as domains of protection and capabilities.
There are lists of on-line papers about the actors model and languages at:
The corresponding page on the TUNES Wiki is cliki.tunes.org .
Strictly speaking, an "actor" refers to a particular "behaviour" or state. When the actor with a given name specifies its successor behaviour, the name is bound to a new actor with that behaviour (just like processes in CSP). However, it is common to use the term "actor" loosely as if it referred to a single entity with behaviour that changes over time. The discussion below does this.
The main differences between the Actors Model and Communicating Sequential Processes are:
Actors can receive messages from any sender; CSP processes must explicitly name the sending process.
Not strictly true. CSP processes must explicitly name the channel over which they are sending (or receiving) a message. That channel may be used by more than sending process. Modern implementations of CSP-based languages, such as occam-pi and JCSP, support the passing of channel ends from process to process as well.
The actor model requires fairness - no message can be delayed indefinitely. This simplifies reasoning about systems of composed actors (although it complicates the definition of actor semantics - but that is arguably a good trade-off).
In CSP the sender is delayed until it synchronizes with the receiver. An actor, OTOH, can proceed immediately to its next behaviour/state after sending one or more messages (although it often waits for a reply).
Ok, this is strictly true. But not really relevant. It is fairly easy to set up (overwriting) buffers between CSP processes in order to prevent blocking on a message. Again, implementations such as JCSP support this directly with language constructs that provide such buffering.
Yes, it is possible to simulate asynchronous message send on top of synchronous send, and vice versa. However, the different primitive operations are not equally easy to implement:
a CSP unbuffered synchronous send is very simple on an SMP, but only an Actor buffered asynchronous send is a sensible distributed system primitive.
There is a more in-depth comparison with CSP in "Foundations of Actor Semantics" (available from
www.erights.org ).
Note that the comparison in "Foundations of Actor Semantics" deasl with Hoare's original (1978) presentation of CSP, which was then simply a pseudo-programming language. As a result, the comparison doesn't touch on any of the last ~30 years worth of theoretical work on CSP and its associated semantic models. The comparison is of historical interest, but not really relevant to modern CSP.
There are close parallels between Flow Based Programming (FBP) and Actors. The discussion that led to the summary below is at Actors And Flow Based Programming Discussion.
[We'll use "process" to refer to either an FBP process, or a "actor configuration". The latter is a collection of actors, some of which may have names that are made visible outside the configuration. Actors within a configuration typically share part of their state via Lexical Scoping.]
Similarities:
Communication between processes is by way of Information Packets/messages, travelling across buffered connections. (In FBP use of Bounded Buffers is a primitive part of the model; in actors buffering is implemented by serializers.)
A process cannot be affected except by way of an incoming Information Packet/message. [In the [FBP] implementation with which we have most experience, we did provide a "named global" facility, but because of the asynchronism of the system, this could only safely be used for read-only data. In practice it was mostly used for shared reference tables. Besides we told our programmers that Global Variables Are Bad!]
A process can only receive IPs/messages from a limited set of other processes. (The nature of the limitation is different; see below.)
Actor names are First Class; FBP (process, input port name) pairs are also First Class. [Port names (originally numbers) are First Class; I am not sure if process names are. In the static definition case, processes need not even know their own names (the only use that I can think of might be for tracing for debugging). In the dynamic definition case, it might be useful to have process names be First Class also.]
Both models introduce nondeterminism as the result of nondeterministic arrival ordering of messages/IPs.
In both models, a collection of connected processes can be viewed as a larger process. I.e. the notions of FBP process or actor configuration are compositional.
FBP processes can have multiple named input ports. An actor configuration can contain multiple actors whose names are made visible outside the configuration; these serve the same function as input ports.
Use of shared state is discouraged -- although neither model prevents it.
Use of pure functional objects is encouraged -- although neither model requires it.
Differences:
FBP communication networks are specified by a network description that is given in advance, and is usually static (but see the description of dynamic subnets in www.jpaulmorrison.com ).
FBP does not model the internals of processes, only the communication between them. Actors models both (the internal computation of any particular actor configuration can of course be ignored). This reflects the origins of FBP as a programming paradigm, and actors as a foundational model of computation.
An actor can only send messages to its acquaintances, and there are Laws Of Locality, given in "Actors and Continuous Functionals", that describe how the graph of acquaintances can evolve (these laws can be interpreted as applying either between actors or between actor configurations). Just as in the Object Capability Model, "only connectivity begets connectivity". The FBP model does not require any equivalent to these laws, and most FBP systems have been built on top of languages that did not enforce them. In FBP, the main limitations on communication come from the fact that connections must be specified in the network description.
FBP processes also have multiple named output ports. In the Actors Model there are no output ports as such; each actor can send a message to any of its acquaintances at any time. (However, a system might use the convention that the actor names corresponding to outputs are passed in a standardized way on creating an actor configuration, and a network visualizer could recognize this convention.)
In the Actors Model, messages sent to the same actor name by different senders are guaranteed to be merged fairly. In FBP, the corresponding situation where more than one output port is connected to an input port (see figure 8.12 of www.jpaulmorrison.com ) does not require a fair merge, although it might be fair in a particular implementation. In this respect FBP is more similar to CSP.
Each connection in FBP is one-way. In actors most messages include a continuation that allows a reply to be sent; in FBP this would require a separate return channel, and there would be no direct link (except for sequencing) between requests and replies.
The Actors Model requires automatic memory management; FBP does not. There are restrictions on "ownership" of FBP Information Packets, apparently intended to allow reference counting (see www.jpaulmorrison.com ). An implementation of FBP on a garbage-collected platform could presumably relax these restrictions. See also www.jpaulmorrison.com .
Actors Model messages can reference arbitrary graphs of actors; FBP Information Packets can only be trees.
There is no equivalent to "bracketed" IPs (see the end of www.jpaulmorrison.com ) in actors. There is nothing preventing implementing this as a higher-level protocol, but it would be more natural to use messages that reference a list object/actor instead.
Another question about FBP: is the flow of Information Packets always a "push" (i.e. packets are sent as soon as they are available, up to the capacity of the Bounded Buffer), or can packets be "pulled" (i.e. a consumer can say that it only needs a given number of packets)? It is obviously possible to do the latter by adding a back-channel, but is it possible without?
Yes, it's always "push". However, I suppose the receiver can decide how many IPs to receive by "receiving" a certain number of IPs, and then by refusing to receive any more, which will eventually fill up the Bounded Buffer, which will in turn suspend the sender. Not very nice - similar behaviour is often a cause of deadlocks. OTOH It is the mechanism that lets you process "infinite" data streams with a finite amount of resources. (On rereading my sentence, I had a change of heart!)
Hmm -- it seems like support for demand-driven dataflow would be a useful extension to FBP, then. See Vpl Language for example.
Excellent job of refactoring, David! I have some minor quibbles, which I will add here as I digest what you have written. One area of perplexity is what an actor-based Collate would look like in actual code - wouldn't you have to synchronize the cooperating actors somehow? --Paul Morrison
Yes, you do have to synchronize the cooperating actors. The most straightforward way to do this is to have one controlling actor representing the Collate itself, and one "subactor" per input stream. In most actor languages, messages from the subactors to the controlling actor would be automatically serialized by default.
Alternatively, some hybrid Actor Languages (e.g. Ee Language) have the concept of a "vat", which is basically a thread shared by several actors. In that case putting the actors that make up the Collate in the same vat would automatically synchronize them.
Ports are key to the concept of Configurable Modularity, which offers the very real prospect in the future of being able to build quite interesting applications without writing a line of code - just specify the network and parameters, where "parameters" can be expanded to include "mini-languages" - see the discussion in www.jpaulmorrison.com . Ports are the way the inside of a process communicates with the network definition. Suppose you have multiple instances of a Reader process: each instance will usually have its OUT port feeding a different Bounded Buffer connection. Using the concept of Port, the code for a basic Collate is so stunningly simple that I really fail to see what advantage one would gain by coding it using multiple actors, especially if actors don't support ports. And anyway, the FBP orientation towards black-box modules surely makes it even less important what language a module is written in. Maybe you can set me straight, David!
The black-box modules in the Actors Model are actor configurations, not individual actors (see www.cypherpunks.to for a formal treatment). I've changed the summary above to reflect this.
Because the Actors Model is intended as a foundational model of computation, its most basic concept -- an actor -- is deliberately as simple as possible. In a pure actor language, the sublanguage used to specify an actor behaviour is not even Turing Complete; the model becomes Turing Complete only when the behaviours change over time and multiple actors (or an actor sending messages to itself) are considered. Writing a program directly in terms of the pure Actors Model would be like writing it directly in the Lambda Calculus using Continuation Passing Style; it's important to know that it can be done, that high level programs have a well-defined translation to this form, and that's about all.
As a humble programmer, I keep puzzling over the last sentence: *why* is it important to know it can be done? I know it is important to know that matter is made of quarks and leptons (or whatever), but how does this apply to the world of computing? Could someone try to articulate this, or point us at a page that does?
I guess it's important as a proof you can solve anything with it you could with other Turing Complete languges, but is it so? Cee Plus Plus Templates are Turing Complete (or so I heard, if not replace with Scheme Macros), but wouldn't they have to expand to an infinite source to model an infinite loop? Then they would never actually run. Maybe stating something is Turing Complete or Lambda Calculus Equivalent gives it some kind of aura.
[C++ templates are Turing complete. The expansion to infinite source is its "infinite loop".]
Practical Actor Languages, OTOH, always include various abstractions above the basic model -- serializers, synchronous calls, vats, message queues, promises, sponsors, etc. The fact that you're creating multiple actors in a situation where an FBP network would have multiple ports is a detail that may be exposed in some actor languages, and hidden in others. The model actually says very little about how to design a high-level actor language; basically it only says that all communication must be by a message passing mechanism that satisfies certain laws. So the code in a particular actor language might look identical to how it would look in an FBP system, including the possibility of using graphical network diagrams (something like Gee Language, for example) or direct interaction to connect processes.
Because FBP Bounded Buffers have finite capacity, [the property that "no message can be delayed indefinitely"] above is probably true in FBP. I have seen a paper stating that this prevents livelock.
www.jpaulmorrison.com says: "Kuse et al. (1986) proved that, although a network with fixed capacity connections (like the ones in FBP) can suffer from deadlock, it can never suffer from livelock." The reference is to K. Kuse, M. Sassa, I. Nakata (1986), "Modelling and Analysis of Concurrent Processes Connected by Streams", Journal of Information Processing, Vol. 9, No. 3, abstract at www.ipsj.or.jp .
The abstract of this paper says that "A network in this class has some restrictions, for example, a stream must have only one producer and one consumer." This is not usually the case for the Actors Model.
It is possible they are making a distinction between "streams" and "channels". Here is part of a paragraph from www.jpaulmorrison.com : "In A'UM [K. Yoshida and T. Chikayama (1988)] and some of the other systems related to it, a distinction is made between "streams" and "channels". ... in A'UM, a "stream" runs from one source to one destination, whereas a "channel" may contain more than one stream, coming from different sources: the items in each stream must stay in sequence relative to each other, but the streams in a channel are not constrained relative to each other. In A'UM only one reader is allowed for a channel, while in Tribble's paper on channels (Tribble et al. 1987), he allows multiple readers for a channel. The authors of A'UM feel that not allowing multiple readers makes their semantics sounder and the implementation simpler." FBP also does not allow multiple readers. --pm
In actors you could easily construct a stream that had multiple readers, by reifying the stream as an actor. For normal messages, though, an actor receives some interleaving (fair merge) of all the messages sent to it.
In FBP it looks as though you could also construct a stream with multiple readers, using something similar to the Collate construct but in reverse, with one input port per reader to request the next item, and one output port per reader to receive the item. It would be more complicated than in actors because FBP has no built-in convention for reply messages.
About the fairness property:
The fairness guarantee applies to directly sent messages. Because messages are first-class in the Actors Model, it is possible for an actor to be wrapped by a "serializer" or "guardian", which can filter, delay or reorder individual messages (this is how an actor would avoid receiving a message when it is in an inconsistent state). A serializer may not pass on a particular message, but this does not contradict fairness, because it received the message with only finite delay. Serializers were a feature of the first actor languages (see "Issues in the Design and Implementation of Act2").
A Bounded Buffer in FBP corresponds directly to a serializer with a bounded message queue. Suppose, for example, that we have two actors A and B where A is sending messages to B's serializer, and is expecting a reply to each message. Each message from A to B's serializer includes a unique continuation. After each send, A will go into a state where it is waiting to be sent the reply via that continuation. (A would have its own serializer which delays messages directed to A while it is waiting.) The fact that A waits for a response ensures that it will not try to send so many messages that B cannot keep up.
The fact that it is serializers that store any "delayed" messages means that the actor system itself can be implemented with only finite memory for pending messages. However, this ducks the issue of how a serializer should deal with "message overruns", where other actors try to send an unbounded number of messages to it without waiting for anything. This potential problem is inherent to one-way buffered messaging, and it can be solved by using higher-level abstractions that provide flow control or backpressure (to attempt to prevent the problem), and that account for memory usage (to deal with the effects if prevention fails). The nice thing about this approach is that you're not limited to any fixed set of abstractions.
From www.jpaulmorrison.com :
Hewitt's Actors take processes down to the finest possible granularity: "Hewitt declared", to quote Robin Milner (1993), "that a value, an operator on values, and a process should all be the same kind of thing: an actor." This approach has considerable theoretical attractiveness, but in my view, to be practical, it basically has to be implemented as hardware, rather than software. There are also of course a number of projects growing out of Hewitt's Actors, which also seem to be on a converging path with all the other work (albeit at the more granular end of the scale), e.g. Agha's COOP (1990).
The Actors Model doesn't have to be implemented in hardware to be practical. Although there was a project to build an actor-oriented machine called the "Apiary", AFAIK this was never completed, and so all working implementations of the Actors Model have been software-based. In terms of sequential computation, the performance cost of the "Everything Isan actor" approach is similar to the cost of "Everything Isan object" in languages like Smalltalk. In terms of concurrency, Erlang Language, Oz Language, Stackless Python, etc. demonstrate that user-level threading implementations can easily scale to large numbers (100s of 1000s?) of active threads. Since actors only perform work in response to messages, the number of actors can be much greater again than the number of threads.
You touch on a key concern of mine: how would these systems perform processing millions of transactions a day? I relate to the goal of Bridging The Gap between the designer's thought and the implementation, but if a program is going to be used for productive work in a large company, it also has to be able to handle (very) large volumes. This was the thought underlying my comment on hardware. BTW I'm not too excited about the overhead of "Everything Isan object" either! --Paul Morrison
1 million transactions per day is ~12 transactions per second on average. Suppose it is 100 transactions per second peak. On a 1 GHz processor, that is 10 million cycles to play with for each transaction. Assuming adequate bandwidth and that each transaction is not unreasonably computationally intensive, it would actually be quite difficult to implement a system inefficiently enough that it cannot keep up with this load -- unless the underlying operating system gets in the way.
Reliability is likely to be much more of an issue for this kind of system than raw performance. After all, we now have supercomputers on our desks. It is only the inefficiency of certain operating system platforms that obscures that fact. -- David Sarah Hopwood
That makes sense to me. And it means that we can actually spend quite a lot of CPU time to make systems more reliable, and, I would add, more maintainable. I have often been struck by how so much of our research goes into better ways to create new code, rather than ways to make code that is more reusable. I think it was Ew Dijkstra who said code should be a cost item, not a measure of productivity.
I couldn't agree more -- see my home page when it's finished. -- David Sarah Hopwood
Still waiting.... --Paul Morrison
I have felt for a while that this architecture probably has considerable relevance for the security world - anyone want to run with this?
The Actors Model is the basis of some Object Capability Languages including Ee Language. This is a very active area of research. I'm currently working on an actor-based multi-language operating system -- I'll add references here when the design is closer to being cooked. -- David Sarah Hopwood
In case that's not explicit enough, capability systems are a ... fundamental or foundational model of security. The "acquaintance" that one actor has with another is just like a capability. A capability is a one-way channel that one actor (or process or user) has to another, and in these systems, sending requests through capabilities is the only way of doing things. A capability can't be "forged"--that is, you can't create one by casting from a number or guessing an address, you can only acquire one at your creation time or passed to you in a message. Security is achieved by controlling who and what processes are given capabilities to access what resources, other processes, etc. Authorities for different operations or views on the same thing, e.g. read vs. write, can be set up as separate capabilities. --Steve Witham
Comparison of the Actors Model with the Join Calculus:
This is based on the tutorial at pauillac.inria.fr , and the paper "The Reflexive CHAM and the join-calculus", which is at research.microsoft.com
(you may need to use Microsoft Internet Explorer and/or switch off pop-up blocking to access the latter.)
Channels in the Join Calculus are equivalent to actor names; both are First Class.
Both are message-passing models, with arrival order nondeterminism. It is not clear whether the Join Calculus requires finite delay.
Both are fundamentally based on Continuation Passing Style, with most practical languages that follow each model providing sequential constructs via CPS conversion. (This accounts for the fact that the tutorial distinguishes between "expressions" and "processes", whereas the Actors Model has only "behaviours" -- after CPS conversion the Join Calculus also only has one kind of behaviour.)
In both models, a process can send a message to another process if-and-only-if it "knows" the latter's channel/name. A new process' channel/name is only initially known by its creator.
Ordinary (non-join) patterns correspond straightforwardly to actor definitions (with the obvious translation of the 'reply' construct to Continuation Passing Style).
Join patterns are primitive in the Join Calculus, but not primitive in actors. It would be easy to support join patterns in an actor language, by representing each subpattern as an actor and having each wait until all subpatterns are triggered.
The approach to modelling objects described in the tutorial (using lexical scoping to hide internal state) is similar to what would be used in actors. In actors you would normally pattern match on the method name rather than returning a tuple of functions, but you could do that in the Join Calculus as well.
So, for all intents and purposes, the Join Calculus and the Actors Model are almost identical. "The Reflexive CHAM and the join-calculus" describes the Join Calculus as a modification of the Pi Calculus and the Chemical Abstract Machine, but these modifications are essentially equivalent to enforcing the actor Laws Of Locality, and changing the semantics of channels to follow that of actor message passing.
This would be all very well if the Join Calculus had been developed in the late 1970s or 1980s. Given that it was developed in 1995, you have to wonder why Cedric Fournet and Georges Gonthier didn't simply publish a paper relating the Pi Calculus to the Actors Model, rather than reinventing the wheel with an entirely new terminology. The only new construct in the Join Calculus is join patterns, and those are trivially simulatable by actors. "The Reflexive CHAM and the join-calculus" does reference two papers on actors, but little or no research seems to have been put into any comparison. Also see cliki.tunes.org .
Oh well -- at least they are promoting the right concurrency model, even if they had to reinvent it 20 years after the fact. -- David Sarah Hopwood
This Actors Model does allow a very intuitive view of the universe in which processes run. Something like Processes In The Ether or Programmable Logic Controllers on a factory backbone, it even makes the factory floor model easily conceivable as a model for a robot's software. I think its view of inter-process communication offers a clear and simple single practical view to the designer. All processes are the result of the Designated Behaviour of another process - invoking a process is an assertion that that process will follow its Designated Behaviour. I think Actors Model and Flow Based Programming are complementary - each Actor implemented using FBP. -- Peter Lynch
Some Actors Model Skepticism
Actors Model in its base form has some nice, simple properties that make it easy to reason about and implement. But, after having pursued it for a while based on its being inherently distributed and concurrent, I've grown quite skeptical about its application in practice. Among the problems:
message delivery: Actors Model makes an assumption that messages will eventually reach their destination. In any open distributed system, this can't be guaranteed. In part, we must deal with the fact that distributed garbage collection in an open system is undecidable, and so actors will need to be deleted heuristically or explicitly when it seems unlikely they will see further use. That said, the Actors Model is still one of the better models out there for handling dropped messages, since they simply become messages that aren't delivered yet.
coordination: 'Pure' Actors Model coordination is not simple. To the contrary, it is very invasive of actors, often requiring a complex dance of creating new actors to receive messages and process them in a sort of Continuation Passing Style, and yet more actors to operate as serializers. As noted above, "Practical Actor Languages, OTOH, always include various abstractions above the basic model -- serializers, synchronous calls, vats, message queues, promises, sponsors, etc.". And, even with these abstractions, coordination with the Actors Model is not simple... because now you need to use these abstractions. As mentioned regarding Flow Based Programming above, some sort of external coordination (both when creating new services and when integrating with pre-existing services) seems far more promising.
synchronous communications, such as Send Receive Reply, break Actors Model - the properties that hold in Actors Model cannot be claimed to hold in a system with synchronous communications. For example, one gets deadlock for free! Something 'sort of like' synchronous communications is to send messages with an actor identifier to which to send the reply message, which will be further processed in a Continuation Passing Style. However, the similarities break down if the actor requesting the reply intends to update its own behavior for processing other messages. This behavior can be handled by ever more state and vocabulary within actors (actors keep state regarding which messages have been sent, which are being waited upon, which are waiting for processing until after receiving a message, etc.) but this makes for heavyweight actors and more Cross Cutting Concerns that, like other forms of coordination, interferes with 'domain' actors. I've developed Transactional Actor Model to aide with certain forms of synchronization, but have yet to explore how much it helps in enough use-cases to deem it a solution.
See original on c2.com