A general model of concurrent computation developed by CarlHewitt
(also "actor model"). Several ActorLanguages
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.
The actors model is closely related to the ObjectCapabilityModel
- 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 SeymourPapert'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 http://cliki.tunes.org/Actor
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 ActorsModel
- 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
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 FlowBasedProgramming
(FBP) and Actors. The discussion that led to the summary below is at ActorsAndFlowBasedProgrammingDiscussion
[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 LexicalScoping
- Communication between processes is by way of InformationPackets/messages, travelling across buffered connections. (In FBP use of BoundedBuffers 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 InformationPacket/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 GlobalVariablesAreBad!]
- 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 FirstClass; FBP (process, input port name) pairs are also FirstClass. [Port names (originally numbers) are FirstClass; 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 FirstClass 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.
- 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 http://www.jpaulmorrison.com/fbp/compos.htm ).
- 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 LawsOfLocality?, 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 ObjectCapabilityModel, "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 ActorsModel 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 ActorsModel, 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 http://www.jpaulmorrison.com/fbp/simpapp2.htm ) 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 ActorsModel requires automatic memory management; FBP does not. There are restrictions on "ownership" of FBP InformationPackets, apparently intended to allow reference counting (see http://www.jpaulmorrison.com/fbp/tree.htm ). An implementation of FBP on a garbage-collected platform could presumably relax these restrictions. See also http://www.jpaulmorrison.com/cgi-bin/wiki.pl?TreeIP .
- ActorsModel messages can reference arbitrary graphs of actors; FBP InformationPackets can only be trees.
- There is no equivalent to "bracketed" IPs (see the end of http://www.jpaulmorrison.com/fbp/compos.htm ) 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 InformationPacket
s always a "push" (i.e. packets are sent as soon as they are available, up to the capacity of the BoundedBuffer
), 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 BoundedBuffer, 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 VplLanguage
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?
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 ActorLanguages
) 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 ConfigurableModularity, 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 http://www.jpaulmorrison.com/fbp/minilang.htm. 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 BoundedBuffer 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 ActorsModel
are actor configurations, not individual actors (see http://www.cypherpunks.to/erights/history/actors/96jfp.pdf
for a formal treatment). I've changed the summary above to reflect this.
Because the ActorsModel
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 TuringComplete
; the model becomes TuringComplete
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 ActorsModel
would be like writing it directly in the LambdaCalculus
; 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 TuringComplete languges, but is it so? CeePlusPlusTemplates? are TuringComplete (or so I heard, if not replace with SchemeMacros), 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 TuringComplete or LambdaCalculusEquivalent? gives it some kind of aura.
- [C++ templates are Turing complete. The expansion to infinite source is its "infinite loop".]
, 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 GeeLanguage
, for example) or direct interaction to connect processes.
Because FBP BoundedBuffer
s 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.
"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 http://www.ipsj.or.jp/members/JInfP/Eng/0903/article005.html .
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 ActorsModel.
It is possible they are making a distinction between "streams" and "channels". Here is part of a paragraph from http://www.jpaulmorrison.com/fbp/cognates.htm
: "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 ActorsModel, 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 BoundedBuffer 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.
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).
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 ActorsModel
have been software-based. In terms of sequential computation, the performance cost of the "EverythingIsa
n actor" approach is similar to the cost of "EverythingIsa
n object" in languages like Smalltalk. In terms of concurrency, ErlangLanguage
, 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 BridgingTheGap 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 "EverythingIsan object" either!
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. -- DavidSarahHopwood
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 EwDijkstra 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. -- DavidSarahHopwood
I have felt for a while that this architecture probably has considerable relevance for the security world - anyone want to run with this?
The ActorsModel is the basis of some ObjectCapabilityLanguages including EeLanguage. 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. -- DavidSarahHopwood
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. --SteveWitham
Comparison of the ActorsModel
with the JoinCalculus
This is based on the tutorial at http://pauillac.inria.fr/join/manual/manual002.html
, and the paper "The Reflexive CHAM and the join-calculus", which is at http://research.microsoft.com/~fournet/biblio.htm
(you may need to use MicrosoftInternetExplorer
and/or switch off pop-up blocking to access the latter.)
- Channels in the JoinCalculus are equivalent to actor names; both are FirstClass.
- Both are message-passing models, with arrival order nondeterminism. It is not clear whether the JoinCalculus requires finite delay.
- Both are fundamentally based on ContinuationPassingStyle, 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 ActorsModel has only "behaviours" -- after CPS conversion the JoinCalculus 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 ContinuationPassingStyle).
- Join patterns are primitive in the JoinCalculus, 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 JoinCalculus as well.
So, for all intents and purposes, the JoinCalculus
and the ActorsModel
are almost identical. "The Reflexive CHAM and the join-calculus" describes the JoinCalculus
as a modification of the PiCalculus
and the ChemicalAbstractMachine?
, but these modifications are essentially equivalent to enforcing the actor LawsOfLocality?
, and changing the semantics of channels to follow that of actor message passing.
This would be all very well if the JoinCalculus
had been developed in the late 1970s or 1980s. Given that it was developed in 1995, you have to wonder why CedricFournet?
didn't simply publish a paper relating the PiCalculus
to the ActorsModel
, rather than reinventing the wheel with an entirely new terminology. The only new construct in the JoinCalculus
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 http://cliki.tunes.org/Actor
Oh well -- at least they are
promoting the right concurrency model, even if they had to reinvent it 20 years after the fact. -- DavidSarahHopwood
does allow a very intuitive view of the universe in which processes run. Something like ProcessesInTheEther
s 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 DesignatedBehaviour
of another process - invoking a process is an assertion that that process will follow its DesignatedBehaviour
. I think ActorsModel
are complementary - each Actor implemented using FBP. -- PeterLynch
Some ActorsModel Skepticism
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: ActorsModel 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 ActorsModel 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' ActorsModel 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 ContinuationPassingStyle, and yet more actors to operate as serializers. As noted above, "Practical ActorLanguages, 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 ActorsModel is not simple... because now you need to use these abstractions. As mentioned regarding FlowBasedProgramming 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 SendReceiveReply, break ActorsModel - the properties that hold in ActorsModel 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 ContinuationPassingStyle. 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 CrossCuttingConcerns that, like other forms of coordination, interferes with 'domain' actors. I've developed TransactionalActorModel 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 also: ActorLanguages