Actor Model

Origin. Carl Hewitt, Peter Bishop and Richard Steiger, "A Universal Modular ACTOR Formalism for Artificial Intelligence" (IJCAI 1973), growing out of Planner and the message-passing discipline of Smalltalk. Baker and Hewitt (1977) stated the laws for communicating parallel processes. Greif (1975) gave the first operational semantics, Clinger (1981) the first denotational one, and Agha (1986) the configuration-based operational theory that later work builds on; Agha, Mason, Smith and Talcott (1997) supplied a full equational theory.

Models. Concurrency without shared state. An actor is an independent entity with a mail address, a mailbox and a behavior; it processes one message at a time and may only send messages, create actors and replace its own behavior. There is no memory two actors both touch, so there are no data races by construction, and every interaction is an asynchronous message. Delivery is guaranteed but unordered, and computation is location-transparent: an address says nothing about where its actor runs.

Formalism.

Actor: Independent computational entity. Has: address, behavior, mailbox. Responds to messages one at a time.

Primitive operations: send(a, m): send message m to actor a create(b): create new actor with behavior b become(b): change own behavior to b

Message delivery: Asynchronous: send doesn't wait. Guaranteed delivery (in model). Order not guaranteed between actors.

Behavior: Function from message to actions. b(m) = {send(...), create(...), become(...)}

Operational semantics: Configuration ⟨α | μ⟩: actor map α (address ↦ behavior) and multiset μ of messages in transit. Step: some actor with a pending message consumes it and performs its actions. Receptionists: addresses known outside; external actors: addresses known inside. The interface (receptionists, externals) is what an observer can use.

Event ordering: Happens-before: causal ordering. a sends to b happens-before b receives. Local ordering within actor.

Properties: No shared state; no locks needed, because nothing is shared. Location transparency: an address carries no place. Encapsulation: state changes only via become. Fairness: every message in transit is eventually delivered.

Equivalences: May-equivalence: same possible observations. Must-equivalence (convergence): sensitive to fairness. Both are defined over the receptionist interface, not over internal structure.

Symbols.

Symbol	Unicode	Name	Meaning
a, b	—	Actors	Entity addresses
m	—	Message	Communication
→	U+2192	Send	Message passing
⟨⟩	—	Configuration	Actor map paired with messages in transit
↦	U+21A6	Maps to	Address to behavior in the actor map
α	U+03B1	Alpha	The actor map of a configuration
μ	U+03BC	Mu	The multiset of messages in transit
send	—	Send	Asynchronous message to a known address
create	—	Create	Allocate a new actor with a given behavior
become	—	Become	Replace the acting behavior for the next message

Metatheory. The model is Turing complete; the λ-calculus embeds by representing each abstraction as an actor and each application as a message. Clinger's Foundations of Actor Semantics (1981) gave the first denotational account, over a power domain of augmented actor computation paths, and established the model's characteristic property: guaranteed delivery under fairness yields unbounded nondeterminism, so a computation can be certain to terminate while no bound exists on its result. Unbounded nondeterminism is not representable by ω-continuous functions, so the Kleene least-fixed-point account of iteration does not apply and the semantics is forced past continuity — this is precisely where the actor model departs from the bounded nondeterminism of the original CSP. Agha, Mason, Smith and Talcott, "A Foundation for Actor Computation" (JFP 1997), gave an operational theory for a λ-based actor language with may- and must-testing equivalences over the receptionist interface, and proved the resulting observational equivalence a congruence, so actor programs can be replaced by equivalent ones inside any configuration.

Applies to. Erlang/OTP. Akka. Distributed systems. Cloud computing. Fault tolerance.

Limitations. Unbounded nondeterminism puts the model outside ω-continuous domain theory, so the standard fixed-point machinery for reasoning about iteration is unavailable and must-equivalence, which depends on the fairness assumption, is correspondingly hard to establish. The guarantee of eventual delivery is itself not implementable over a lossy network without unbounded retransmission and unbounded buffers, so real systems satisfy a weaker model than the one the theory analyses, and results proved under fairness do not transfer to them. Messages between two actors are unordered, so any ordering an application needs must be reconstructed by protocol; the model supplies no sequencing primitive. Removing shared state removes data races but not liveness failures: actors waiting on each other's replies deadlock exactly as locks do, and there is no primitive for an atomic action spanning two actors, so transactions and consensus have to be programmed rather than assumed.