Mailbox Semantics and Ordering Guarantees in the Actor Model

An actor holds three things: private state, a set of behaviours, and a mailbox. Only the mailbox is reachable from outside, and it is not shared memory but an address. A message sent to an actor is placed into a queue that only that actor drains. No other actor can read the state behind it, and it cannot read anyone else’s. The concurrency discipline follows from that arrangement rather than from a runtime check: there is no lock because there is no shared mutable cell, and there is no data race because no two threads ever touch the same bytes of actor state at the same time.

What the mailbox actually guarantees is narrower than most descriptions suggest, and the narrowness is deliberate.

The only ordering promise a mailbox can keep

Delivery order is preserved between any single sending actor and any single receiving actor. If process A sends m1 then m2 to B, and no other message from A intervenes, B observes m1 before m2. Messages from different senders have no defined relative order. Two actors sending concurrently to a third can have their messages dequeued in either order, and that order can differ from run to run and from node to node.

This is the strongest promise compatible with concurrency. A global arrival order would require every send to synchronise with every other send in the system, which means a shared clock or a global lock, which is exactly the shared state the model exists to remove. Per-pair ordering costs nothing extra because the messages already travel along the same path; the sender’s sequence number, in effect, is implicit in the channel. The Erlang documentation states the guarantee in this form: signals sent between a pair of processes arrive in the order they were sent, and no ordering is promised across different senders.

The practical consequence is that an actor protocol which requires two independent parties to agree on a sequence must establish that agreement explicitly, usually by routing both through a single coordinator or by attaching a sequence number and buffering out-of-order arrivals. A protocol that silently assumes cross-sender order will pass every test with two participants and fail under three.

Selective receive and its linear scan

Some actor languages let a receive match on message shape rather than take the head of the queue. Erlang’s receive does exactly this: it scans the mailbox from the front and dequeues the first message matching any clause, leaving earlier non-matching messages in place.

loop(State) ->
    receive
        {get, From} ->
            From ! {value, State},
            loop(State);
        {set, New} ->
            loop(New);
        stop ->
            ok
    after 5000 ->
        loop(State)
    end.

The scan is the cost. A selective receive over a queue of depth n is O(n) in the worst case, and the skipped messages stay queued, so a pattern that rarely matches pushes the cost of every subsequent receive upward. Mailboxes with long-lived unmatched traffic degrade into a linear scan over dead weight. The usual mitigation is to keep matching patterns near the front by convention (control messages before data messages, replies before requests), or to split one deep mailbox into several shallow ones.

Selective receive also breaks the neat picture of a mailbox as a FIFO queue. It is a priority queue whose priority function is “matches the current clause”, and the priority changes as the actor’s code moves between receive statements. This is a real expressiveness gain: an actor can wait for a reply while leaving unrelated notifications untouched. It is also why an actor blocked in a selective receive cannot be reasoned about as “not processing anything”, since the mailbox continues to fill.

Where the queue lives, and why unbounded is a bug

The mailbox has a capacity policy, and the policy is a load-shedding decision even when nobody chose it.

An unbounded mailbox never blocks a sender. That makes the send path non-blocking, keeps latency low under burst, and defers all the pain: a consumer slower than its producers accumulates messages until memory is exhausted. The failure is not graceful. In a runtime where all actors share one heap, the growth of one mailbox can raise the cost of garbage collection for every actor in the system, so a single slow consumer can degrade unrelated work before it fails. This is the characteristic failure mode of the model, and it is a direct consequence of choosing a queue with no upper bound.

A bounded mailbox converts the pressure into backpressure at the sender: the send blocks, or returns an error, or drops according to policy. Blocking the sender is the honest option, because it propagates the slowdown to whoever is generating work. Dropping is cheaper but must be matched by a protocol that can tolerate loss, and most request-response protocols cannot. A third option gives the mailbox a limit and treats overflow as an explicit signal to the actor itself, which can then decide to shed, coalesce, or refuse.

The choice also determines whether deadlock is possible. A cycle of actors each blocked on a full mailbox is a deadlock that no lock detector will find, because no lock is held; the wait-for graph is in the queues. Systems that block on send therefore need either an acyclic topology or a timeout on the send path.

Addresses outlive behaviour

An actor’s address is independent of the code currently running behind it. In a runtime with automatic restart, the identity persists across failures, so a message sent to a restarted actor is handled by the new incarnation with whatever state it was rebuilt from. That is the mechanism that makes supervision work, and it is covered in Supervision Trees and the Shape of a Failure Domain.

Sending to an address that no longer has a live actor is usually not an error. Erlang’s send operator to a pid whose process has already exited succeeds; the message is discarded. The guarantee is therefore at-most-once, not at-least-once, and delivery is not confirmed by the send. Any protocol needing confirmation must add an explicit acknowledgement and an identifier, plus a retry policy, at which point the mailbox is no longer providing reliability; the protocol above it is.

This asymmetry is worth stating plainly because it is often blurred: the mailbox provides ordered, asynchronous, at-most-once delivery between a pair of addresses. Reliability, exactly-once semantics, and request timeouts are all application-level constructions on top.

The boundary with channel-based models

An actor mailbox is owned by its receiver and has no notion of a rendezvous. A sender never learns whether the receiver was ready; it appends and continues. Channel-based models in the CSP tradition invert this, making the handoff itself the synchronisation point, and that single difference accounts for most of the behavioural gap between the two families; see Rendezvous and Buffering in CSP-Style Channels.

The cost of the mailbox design is that a sender cannot be slowed by a receiver it has not met, so flow control must be built from bounded queues, acknowledgements, or a separate credit protocol. The benefit is that the send path is short, does not require the receiver to be scheduled, and works unchanged across a network boundary where the receiver may be on another machine. That last property is why the actor model survives as a distributed-systems discipline and not only a shared-memory one.

What the model does not remove

Serialising access to state per actor removes data races on that state. It does not remove races in the protocol. Two messages can still arrive in an order that leaves the actor’s state inconsistent with what either sender believed, and the mailbox will not report this. The invariant “a transfer is either fully applied or not at all” is a property of the message handlers, not of the queue.

Nor does the model bound the number of actors. Each actor typically costs a small heap object plus a queue; the figure varies by runtime and by whether the queue is embedded in the process header or separately allocated. At large actor counts, per-actor overhead and the cost of scheduling a runnable queue dominate, which pushes the design toward the multiplexed schedulers described in Multiplexing Green Threads onto Kernel Threads.

The mailbox is a small mechanism with three parameters: ordering scope, capacity policy, and liveness of the address. Nearly every dispute about actor systems reduces to a disagreement about one of them.