Takeaways from Hewitt, Meijer and Szyperski’s talk on the Actor model

This is a list of my takeaways from the excellent talk between Erik Meijer (of the LINQ and Rx fame), Carl Hewitt (creator of the Actor model) and Clemens Szyperski, on the Actor model.

 

Disclaimer : this conversation revolves around the conceptual model of an actor, as opposed to specific implementations of the Actor model.

 

What is an actor?

An actor is the fundamental unit of computation which embodies the 3 things – processing, storage and communications – that are essential to computation.

One actor is no actor, they come in systems, and they have to have addresses so that one actor can send messages to another actor.

 

Beyond the high-level abstraction, an actor has a number of properties:

  • Everything is an actor
  • An actor has a mailbox

 

Since a mailbox is also an actor, it too will have a mailbox, and so the recursion begins! This recursion ends with axioms.

 

Axiom

When an actor receives a message it can:

  • Create new actors
  • Send messages to actors it has addresses before
  • Designate how to handle the next message it receives (e.g. state)

and that’s it!

“Conceptually, messages are processed one at a time, but the implementation can allow for concurrent processing of messages.” – Carl Hewitt

 

This is not the same as a continuation, which is the lambda expression that you execute after doing the current one and is a concept for single threaded processing.

 

Whilst conceptually messages are processed one at a time, the implementation can allow for concurrent processing of messages. For instance, a factorial actor which has no state and will process each message the same way can process an arbitrary number of messages at the same time.

 

An actor can also send messages to itself (i.e. recursion), and to avoid deadlocks we have the notion of a future.

The idea of a future is that you can create an actor with any result whilst it’s still being computed. For instance, you can create a future for factorial 100m, which will take a long time to compute, but you can have the future straight away and pass it around.

 

Addresses

The address of an actor is not the same as its identity because:

  • One actor can have one address for many actors if you’re replicating behind the scenes
  • One actor can have many addresses that forward to one another (via proxy actors)

hence there’s a many-to-many relationship between actors and addresses.

 

With actors, all you have are addresses, which doesn’t tell you whether you have one or many actors behind those addresses. The same notion of addresses also applies to the web, e.g. whilst searching on google.com it’s not the same actor that are processing your requests every time.

 

Addresses are similar to capabilities, but is a much clearer name for a capability because it tells you exactly what you are allowed to do – sending messages to it, which is its only capability.

“If you can maintain the integrity of addresses, you get capabilities for free” – Carl Hewitt

 

Messages

Messages are like ‘packets’ in the internet, they obey the same rule as packets for efficiency reasons – messages are received in any order because it’s more expensive on the system to enforce the ordering constraint.

 

Messages are also delivered on a best-efforts basis, which when crossing machines this means they are persisted on some storage and can be resent if receipt acknowledgement is not received. But if the source machine is terminated before the resent happens then the message is lost.

 

Messages sent between actors are delivered at most once, and may take a long time to arrive depending on distance and network latency between the actors (e.g. message in a bottle..).

 

Channels

“There are no channels” – Carl Hewitt

Instead, the actors talk directly to one another.

 

The problem with a channel is that if you’re trying to send a message to two recipients only one of them will receive the message, unless you go through with the overhead of a two-phase commit.

 

As an implementation detail, you can implement a channel (which will be another actor in the system) if you want, but it’s not part of the conceptual model.

 

Nondeterminism vs Indeterminism

A quick recap on turing machines, which is theoretical machine that defines computability. It can be thought of as a simple computer that reads and writes symbols one at a time on an infinitely long tape by following a set of rules. It determines what to do next according to an internal state and what symbol it currently sees on the tape.

In a deterministic turing machine, given the current state and symbol it specifies only one action to be performed. For example, “if you are in state 2 and you see an ‘A’, write a ‘B’ and move left”.

In a nondeterministic turing machine (NTM), given the current state and symbol it may specify more than one action to be performed. For example, “if you are in state 2 and you see an ‘A’, write a ‘B’, move right and switch to state 5”.

 

In a NTM, the state of the computation is fixed, and can be proved that a state machine model of computation has to have a bounded nondeterminism (i.e. it halts after a bounded number of steps, hence has a bounded number of possible configurations).

With the Actor model, you have a configuration-based model of computation (based on messages that are received, which are dynamic as opposed to fixed), which is more powerful because it incorporates communication. This configuration-based model gives you indeterminism, which is what happens when things work themselves out.

 

Contrary to popular believes, turing machine is not the only thing that defines computability, and interactions with an open environment certainly changes what computation means and is the difference between nondeterminism and indeterminism.

 

Synchronization

Synchronization is built into the Actor model because messages can be received one at a time by an actor.

In a check-in account example where many parties can cash-in or withdraw from the account, suppose the current balance is £2, and one person tries to withdraw £7 whilst another tries to cash-in £8, the outcome is indeterminant based on the order in which the messages are received by the actor.

This is where the arbiters come in.

 

Arbiter

“The arbiter decides, and there’s nothing before the arbiter decides” – Carl Hewitt

Given an arbiter, you can have multiple inputs (e.g. I0 and I1) into the arbiter at the same time, but only one of the possible outcomes (e.g. O0 or O1) will come out on the other end.

image

The arbiter is what gives us indeterminism, it can take an arbitrary amount of time (with the probability of indecision decreasing exponentially over time) to come to a decision but it must decide.

 

Implementation

There’s an art to the implementation of the Actor model in programming languages and there are many ways you can make mistakes in the implementation – by violating some of the fundamental principles or by not taking them seriously.

 

The Actor model is not the same as tail recursive calls (because it can change the state for the next message received) or event loops (because of the optimizations).

 

 

I hope I’ve done the talk justice with these short notes I’ve taken and that you find them useful as you no doubt watch the talk over and over as I had, and before we go I’d like to leave you with yet another great quoteSmile

“We don’t know much, and some of it is wrong” – Carl Hewitt

  • Chris

    Did you mean ‘Turing machine’?

  • theburningmonk

    @Chris – yup, typo!

  • http://bitmage.net bitmage

    You said “An axiom can cre­ate new actors”. I think you meant “An actor can create new actors”.

    I’m not sure I understand your use of the word axiom. Actors are a formal system for computations, and formal systems are comprised of rules and axioms. The axioms are the baseline assumptions of such a system. I’m not well versed in the terminology of Actors, but I don’t think there is a concrete component within this system that Karl Hewitt actually refers to as an axiom. Instead he’s referring to a set of rules which are all axiomatic. He’s expressing his system in terms of a formal system, and axioms are part of the terminology of that higher category.

  • theburningmonk

    @bitmage – reading through my notes again it looks like I had scribbled down that segment of the conversation incorrectly (around the 3 min mark), thanks for pointing it out!

    I’ll update the section, please let me know if you find any other mistakes! (there were so much to take in from the conversation I’m sure I’ve made a few mistakes trying to note everything down!)

  • Pingback: Introduce raven_dart, a Dart client for Sentry | theburningmonk.com()

  • Tahir Hassan

    A non-deterministic Turing machine is equivalent in power to a deterministic Turing machine. Its a bit like how a Non-deterministic finite automaton can be converted into a deterministic finite automaton.

    Turing machines do not communicate with the outside world (other than its initial set of conditions), whereas real-world computers do, therefore I don’t think that Turing machines are the right formalism to discuss communication.

    Also, formalism’s like Milner’s “calculus of communicating systems” cannot capture the kind of indeterminism we find in the real world, it can only model it.

  • Pingback: A look at Microsoft Orleans through Erlang-tinted glasses | theburningmonk.com()

  • Pingback: Being visually honest with F# | theburningmonk.com()

  • Pingback: Exercises in Programming Style–Actors | theburningmonk.com()