A simple actor definition
TODO
Introduction
In 1986, Gul Agha wrote: It is generally believed that the next generation of computers will involve massively parallel architectures(Agha 1986). Today, in 2026, 40 years later, it is the case. The central abstraction to deal with this fact is the idea of an Actor. We go through available published work and attempt to provide a simple definition to this idea, then a few examples and finally use cases.
Objective
- Define what an actor is.
- Provide an illustrative example.
- Provide a use case.
Gul A. Agha 1986
Actors: A Model of Concurrent Computation in Distributed Systems(Agha 1986), seems to be the main book about actors. Unfortunately, I find it hard to understand.
Hewitt 2010
Time may have sorted out a clearer exposition in Actor Model of Computation: Scalable Robust Information Systems(Hewitt 2010).
Message passing using types is the foundation of system communication:
- Messages are the unit of communication1
- Types enable secure communication with any Actor
What is the definition of a Message? What is the definition of an Actor?
When an Actor receives a message, it can concurrently:
- send messages to (unforgeable) addresses of Actors that it has;
- create new Actors;
- designate how to handle the next message it receives.
What is an address?
It is a consequence of the Actor Model that there are some computations that cannot be implemented in the lambda calculus.
Proof?
The Actor Model is a mathematical theory of computation that treats “Actors” as the universal primitives of concurrent digital computation [Hewitt, Bishop, and Steiger 1973; Hewitt 1977]
So, this is where we should look for the definition of an Actor.
The advent of massive concurrency through client-cloud computing and many-core computer architectures has galvanized interest in the Actor Model [Hewitt 2009b].
It took a few decades, but time seems to favor the actor model. Hewitt 2009b should explain why.
An Actor can only communicate with another Actor to which it has an address. Addresses can be implemented in a variety of ways:
- direct physical attachment
- memory or disk addresses
- network addresses
- email addresses
But why not just give definitions like mathematicians do? Just a sequence of consistent definitions and propositions, maybe with proofs.
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 reception order.
direct asynchronous message passing?
The Actor Model differs from its predecessors and most current models of computation in that the Actor Model assumes the following:
- Concurrent execution in processing a message.
- The following are not required by an Actor: a thread, a mailbox, a
message queue, its own operating system process, etc.
- Message passing has the same overhead as looping and procedure
calling.
- Primitive Actors can be implemented in hardware.
Ok.
The Actor Model is based on one-way asynchronous communication. Once a message has been sent, it is the responsibility of the receiver. Messages in the Actor Model are decoupled from the sender and are delivered by the system on a best efforts basis. […] message passing is taken as fundamental in the Actor Model. […] laws for Actors [Baker and Hewitt 1977]
Fine.
The Actor Model supports indeterminacy because the reception order of messages can affect future behavior. Operations are said to be quasi-commutative to the extent that it doesn’t matter in which order they occur. To the extent possible, quasi-commutativity is used to reduce indeterminacy.
Does this have any relationship with eventual consistency?
Locality and security mean that in processing a message: an Actor can send messages only to addresses for which it has information by the following means:
- that it receives in the message
- that it already had before it received the message
- that it creates while processing the message.
One of the things that every sorcerer will tell you is that if you have the name of the spirit, you have power over it.(Abelson and Sussman 1986).
In the Actor Model, there is no hypothesis of simultaneous change in multiple locations. In this way it differs from some other models of concurrency.
non-local effects are rejected. I cannot seriously believe in it [quantum mechanics] because the theory is incompatible with the principle that physics should represent a reality in time and space, free from spooky actions at a distance.(Einstein 1971).
The security of Actors can be protected in the following ways:
- hardwiring in which Actors are physically connected
- every-word-tagged memory.
- virtual machines as in Java virtual machine, Common Language
Runtime, etc.
- signing and/or encryption of Actors and their addresses
A delicate point in the Actor Model is the ability to synthesize the address of an Actor. In some cases security can be used to prevent the synthesis of addresses in practice using the following:
- every-word-tagged memory
- signing and encryption of messages
Interesting.
Runtime failures are always a possibility in Actor systems and are dealt with by runtime infrastructures. Message acknowledgement, reception, and response cannot be guaranteed although best efforts are made. Consequences are cleaned up on a best-effort basis. Robustness is based on the following principle: If an Actor is sent a request, then the continuation will be one of the following two mutually exclusive possibilities:
- to respond with the response received from the Actor sent the request
- to throw a Messaging exception
A response is either a returned value or a thrown exception. A Messaging exception can have information concerning the lack of response. even though the Actor may have received the request and sent a response that has not yet been received. Requestors need to be able to interact with infrastructures concerning policies to be applied concerning when to generate Unresponsive exceptions.
Ok, so we know what to expect when "speaking" with an actor.
The Computational Representation Theorem [Clinger 1981; Hewitt 2006]11 characterizes computation for systems which are closed in the sense that they do not receive communications from outside. […] The upshot is that concurrent systems can be axiomatized using mathematical logiciv but in general cannot be implemented. Thus, the following practical problem arose:
"How can practical programming languages be rigorously defined since the proposal by Scott and Strachey [1971] to define them in terms lambda calculus failed because the lambda calculus cannot implement concurrency?"
Does it have any implication in practice? See Plotkin "or" and the fact that lambda calculous it can simulate some parallelism (via Church-Rosser allowing independent reductions), but not true non-deterministic or fair concurrency where independent subcomputations can converge independently without full evaluation.(Plotkin 1977)
Programming languages like ActorScript [Hewitt 2010] take the approach of extending behavior in contrast to the approach of specializing behavior:
- Type specialization: If type t1 is a subtype of type t2, then instances of t1 have all of the properties that are provable from the definition of type t2 [Liskov 1987, Liskov and Wing 2001].
- Type extension: A type can be extended to have additional (perhaps incompatible) properties from the type that it extends. An extension type can make use of the implementation of the type that it extends. Type extension is commonly used to extend operating system software as well as applications.
The term “inheritance” in programming has been used (sometimes ambiguously) to mean both specialization and extension.
Interesting distinction: Specializing and Extension.
Reasoning about Actor Systems The principle of Actor induction is:
- Suppose that an Actor x has property P when it is created
- Further suppose that if x has property P when it receives a message,
then it has property P when it receives the next message.
- Then x always has the property P.
In his doctoral dissertation, Aki Yonezawa developed further techniques for proving properties of Actor systems including those that make use of migration. Russ Atkinson developed techniques for proving properties of Actors that are guardians of shared resources. Gerry Barber's 1981 doctoral dissertation concerned reasoning about change in knowledgeable office systems.
So reasoning, i.e. deriving conclusions from premises, is possible.
- Swiss cheese [Hewitt and Atkinson 1977, 1979; Atkinson 1980].
- Futures [Baker and Hewitt 1977].
Time is scarce, let us focus and skip things.
TODO Hewitt & Baker 1977
Bit
bit : Bit signifie que bit peut être remplacé par 0 ou 1.
Bit :≡ 0 | 1
Data
bits : List(Bit) signifie que bits est une liste de Bit. Nous appellons cette structure Data.
Data :≡ List(Bit)
State
State is formally equivalent to Data. It differs in how we plan to use it. While Data is generic, we reserve State in some specific cases.
State :≡ Data
Address
Address#mk() : Address :≡ Data such that it cannot be arbitrarily created, fabricated, guessed, or forged by any actor in the system.
Message
What can be said about State can also be said about Message.
Message :≡ Data
Script
script : Script means that script is some kind of program, i.e. essentially a list of instructions executable mechanically by a machine. The instruction set is restraint in the following sub-sections, but remains abstract as
Script :≡ Given state : State and script : Script, then script(state) is a program starting from state executing what is prescribed by script with the only restriction that its I/O is done by sending and receiving messages.
The precise meanings of sending and receiving are left to interpretation as well as the precise instructions set executed by the program or how they are prescribed by script.
■
■ :≡ Within a script, ■ means that the current script stops equivalent to return in
C.
receive
receive([timeout : Nat]) :≡ whenever a message msg has been received by a program I/O subsystem, then receive([timeout]) is to be replaced by msg. This instruction blocks until then. If timeout is specified, and no message is received before the timeout is exhausted, then receive(timeout) is to be replaced by an instance of Timeout ; a kind of message.
emit
emit(msg) :≡ Within a script, given a message msg, emit(msg) means that any actor observing the current observer will receive msg.
self
self :≡ Within script : Script, then self refers to the current actor actor.
∥
∥ :≡ Given state : State and script : Script, then ∥(state script) means that resources are allocated (e.g. CPU, Memory, energy) so that a program executing script and starting from state is created. program :≡ ∥(state script) means that program references the created program. Does not block.
Actor
- state : State
- script : Script
- Actor#mk(state script) : Actor :≡
- self :≡ Address#mk()
- program :≡ ∥(state script)
- Given msg : Message, then after self#rcv(msg), program has received msg.
- self
observe and ignore
observe(actor) :≡ Given actor : Actor, then after executing observe(actor), any message emitted on the I/O subsystem of the underlying actor is received by the current program. This instruction does not block.
ignore(actor) :≡ Reciprocal of observe(actor).
Clock
Let's attempt to model a clock using Actor. We assume the existance of crystal : Address such that the underlying actor emits instances of Tick — a kind of Message — on its I/O subsystem.
Note that the instructions executing order is not given by the script ; only some
constraints are. For instance, a :≡ A#mk(…); b :≡ f(a) imposes and order, but a :≡
A#mk(…); b :≡ B#mk(…) does not.
Note that the following script must be understood as being executed by an actor.
decode : Message → (String × Address) | String | Nothing
script :≡
<n : Nat, crystal : Crystal> ↦
time :≡ n
observe(crystal)
while msg :≡ receive()
match decode(msg)
<"tick", crystal> ↦ time :≡ time + 1
<"read", to : Address> ↦ to#rcv(<time, self>)
"stop" ↦ ■
state :≡ <0, crystal>
clock :≡ Actor#mk(state script)
clock#rcv(<"read", self>)
while msg :≡ receive()
match msg
<time : Nat, clock> ↦
"The time is: ${time}"
■
_ ↦ continue
Events
Events :≡ Set(Event List=)
Discretness
- E : Events
- < : StrictPartialOrder(E)
- Discretness(E <) :≡ 🞎
concurrent with
- E : Events
- e(i), e(j) ∈ E
- < : StrictPartialOrder(E)
- e1 concurrent with e2 :≡ 🞎
precedes
- E : Events
- e(i), e(j) ∈ E
- < : StrictPartialOrder(E)
- e1 precedes e2 :≡ 🞎
message
message : Event → Message
ActorComputation
- ActorComputation :≡
- E : Events
- < : StrictPartialOrder(E)
- Discretness(E <)
Event
Event :≡ Data
TODO Hewitt 1977
Message definition
A message is an immutable parcel of data sent to an actor’s address. It contains at minimum the recipient address and whatever information the sender chooses to communicate.
Actor definition
An actor is an independent computational entity with three essential properties:
- It has addresses.
- It has private internal state.
- When it receives a message at its address, it may do the following concurrently:
- send messages to addresses it knows,
- create new actors,
- change how it will react to the next message.
Messages are one-way and asynchronous: once sent, the sender cannot wait for or assume delivery.