Deadlock, TOCTOU, and redo: the trilemma for waiting actors #

2026-09-11. Refers to the runner (effectory), the "servers never wait" mitigation in README.md §"The remaining structural cost", and strawman.md §6. Companion to steelman.md, which concedes the deadlock; this file works out what the mitigations actually are, what each one costs, and why none of them is specific to effect routines.

The one-sentence version #

Any system of concurrent, stateful parties that wait on one another faces the same three-way choice — deadlock, stale reads, or redone work — and the choice is orthogonal to whether each party is a coroutine or a sans-io hand-written state machine; the only mitigation that avoids all three is a static order on the channels between parties, which is a property of the boundary, not of the mechanism.

The problem, stated precisely #

An effect routine has one way to wait: Ask/Call records an effect and returns Pending. Tell never blocks. A wait-for cycle therefore needs two or more routines whose pending replies are owed by each other:

        Call(Lookup) ──▶
  A  (awaiting B's reply)      B  (awaiting A's reply)
        ◀── Call(Count)

Both futures are parked; the host has no effect left to perform; the event loop is idle. This is the gen_server:call cycle, and strawman.md §6 is right that no type in the runner rules it out.

Coffman, Elphick, and Shoshani (1971) give the four conditions that are jointly necessary: mutual exclusion, hold-and-wait, no preemption, and circular wait. Every mitigation below breaks one of them, and which one it breaks determines what it costs.

The trilemma #

The hold-and-wait condition is doing double duty. It is what makes a cycle possible, and it is also what gives a sub-call its atomicity: while A holds its obligation to its caller and waits on B, nothing else touches A's decision. Remove hold-and-wait and you keep liveness but lose that atomicity; keep it and you must break the cycle some other way.

approach	addresses	keeps	cost
blocking call	nothing	atomic sub-calls	deadlock
defer and revalidate ("never wait")	hold-and-wait	liveness	stale reads: TOCTOU or redo on conflict (actually fine in a lot of cases AKA optimistic concurrency)
detection or deadlines	no preemption	atomic sub-calls	a party is killed or errors out
ordered channels (levels)	circular wait	atomic sub-calls and liveness	a static layering discipline

The first three rows are the trilemma: deadlock, TOCTOU-then-redo, or failure. The fourth row is the way out, and it costs architecture rather than correctness.

Mitigation 1: servers never wait; conversations do #

The discipline the README already recommends. A long-lived routine handles each input to completion without an Ask to another routine; anything needing a round trip is spawned as a short-lived child that carries the requester's Reply and runs the sequential protocol. In the wait-for graph:

  requester ──awaits──▶ child ──awaits──▶ host effect (I/O, timer)
                          │
  server ◀── nothing points at it: it answered by delegating

• The requester waits, as it always did; only its own caller waits on it, further up the same chain.
• The child owes exactly one thing — the inherited Reply — and only its requester can wait on it, because nobody else has a handle to a fresh child.
• The server owes nothing at any suspension point: its in-degree is zero.
• The host never waits in this sense at all; every chain bottoms out in an effect the host performs from its loop.

So the wait-for graph is a forest of chains, and chains do not deadlock. Something always waits — that is what a conversation is — but it always waits at a leaf.

Attribution #

This is the E-language / Syndicate discipline, where it is total: a vat runs turns to completion and when (promise) → … registers a continuation rather than blocking. It is not the Erlang default. gen_server:call is a blocking rendezvous with a timeout as the deadlock breaker. What Erlang does have is the server-side half: a handle_call that would need to wait returns {noreply, State}, stashes From, and some later message or helper calls gen_server:reply(From, Result). The folk rule "don't call out of a handle_call" is this discipline applied to servers only, with clients still blocking. Reply<T> is exactly From: a capability to answer later that can be stored, forwarded, or handed to a child.

The cost: hold-and-wait was the atomicity #

The moment the server delegates and keeps taking inputs, the window between "read the state and decided" and "the child's answer arrived and acted" is open. Other inputs ran in it. This is the same hazard as a reentrant Orleans grain or an await in single-threaded JS: the yield point is where invariants are unprotected.

   call arrives        child replies
        │                    │
        ▼                    ▼
 ── read state ── [ other inputs mutate state ] ── act on stale read ──

In the general case, handling this is optimistic concurrency, with optimistic concurrency's cost curve: redo proportional to conflict rate × cost of the work. Three things narrow it:

• What the child does matters more than the pattern. The sub-call was usually deferred because it is I/O — a lookup, a read, a network hop — whose result is not a function of the server's state and is never invalidated. What needs revalidating is the decision, an in-memory check against a slow external call. The redo is a re-decision, not a re-fetch. The bad case is a child whose work is itself derived from the stale state; deferral is the wrong tool there.
• Pessimistic per key is still deadlock-free. An InFlight { waiters } entry is a hold on that key: later requests for it queue rather than race, so no redo. What was given up is holding the whole server. Fine-grained holds can still cycle across servers, which is exactly where levels come in.
• Coalescing dedups the flights. Three requests for the same key attach to one InFlight entry; one result answers all three Replys.

Where the hazard lives #

A routine's locals are private and cannot change while it is suspended — nobody else can run it. The interleaving hazard exists only for state shared across yield points: a server's state when the server keeps looping, or host-owned state several routines reach through effects. If the server is loop { let msg = ctx.ask(Inbox).await; … } and defers by spawning a child, the child cannot touch the parent's locals; its result arrives as a message the parent handles against current state, with no stale snapshot available. The hazard does not vanish, but it is forced into one handler, which must revalidate — the same property Erlang gives when the helper's result arrives as handle_info, versus the trap of stashing From and a snapshot.

Does this expose the state machine again? #

Partly, and it is worth being exact about which part, because it is the line steelman.md draws: sans-io is right when control state is domain state.

An effect routine hides the control state of one conversation — "between the lookup and the sleep" — which has one observer, the conversation itself, so it may live in a suspended stack frame nobody can inspect. An InFlight entry is different in kind: it exists because other requests need to observe it while the first is suspended. A suspended coroutine is by construction unobservable, so state that must be seen concurrently has to be reified as a value.

one observer   → implicit, a suspension point      (effect routine)
many observers → explicit, a value in a table      (data, sans-io style)

The server's Map<Key, Entry> is domain state — a cache is its table. What effect routines still buy is that each in-flight child, doing the lookup and the retry and the backoff across three awaits, is direct-style. This is the README's recommended architecture applied one layer up: explicit state where shared, coroutines for the sequential work hanging off each entry.

The alternative that keeps even the entry implicit is the Erlang answer: make the entity the unit. One child routine per key, held in a registry (Map<Key, Handle>). InFlight is not a variant but the fact that the child exists and is suspended; queuing is its mailbox; coalescing is the child answering every Reply it collected when the one lookup returns. The only explicit state is key → handle, which says nothing about the protocol. Cost: many small routines, Ctx::spawn, a registry, and lifetime management. This is the gen_server-per-entity / Orleans-grain shape, and it reintroduces the risk one level down: entities that Call each other synchronously are both waited-on and waiting, the classic case. Orleans answers with non-reentrant grains, a response timeout, and call-chain reentrancy; the alternative is the rule "entities Tell or spawn a conversation, never Call an entity" — the discipline recursed — or levels.

It converts deadlock into growth #

A → server S → child c₁ → server T → child c₂ → server S … S is never blocked, so it spawns c₃. No cycle in the wait-for graph, but a chain that grows until a deadline fires or memory runs out. Erlang shows this as mailbox growth; here it is child count. Structure removes the cycle; detection is still what bounds the pathology.

Mitigation 2: forward the reply instead of awaiting it #

Promise pipelining in miniature. If A needs B's answer only to hand it to A's own caller, A passes its Reply<T> on as an argument in the Call to B and returns, holding no obligation. Reply<T> is already a first-class value, so this works today with no runner change. It is the From-passing pattern verbatim, and it is what "the child carries the requester's Reply cap" in the README describes. It does not help when A needs B's answer for A's own decision.

Mitigation 3: fire-and-collect #

Perform::start → Oneshot<T> lets a routine issue the Call and keep going: handle further inputs, and only .await or try_recv later. The blocking wait becomes "an outstanding request and an open inbox", the select loop actors use to stay responsive. Two same-level requests issued together are not contingent on each other and cannot form a cycle between themselves — which is why this is also the escape hatch for levels below.

Mitigation 4: the host's wait-for graph #

Threads and mutexes hide their wait-for graph inside the kernel. Here the host sees every Ask/Call and every Reply it hands to another routine, so it can maintain edges: routine → routine-that-owes-it, run a DFS when adding an edge — the graph is tiny and sparse — and break a cycle by not answering one member. That member gets ReplyMissing on its next resume and dies, let-it-crash style; a supervisor restarts it. Cost: one map insert per outstanding request. A Reply::fail or poison would let the killed side receive a typed error rather than ReplyMissing, if recovery is preferable to restart.

Sans-io makes this even cheaper: each machine's state enum already says what it is waiting for, so the graph is readable straight out of the states with no bookkeeping. This is the concrete content of strawman.md §6's "you can print the Greeter".

Two extensions:

• Causal chain ids. Tag every Call with the id of the conversation that started it (Orleans's call-chain id). The host can then see "S is being asked from within a chain S itself started" and cut it — which is what bounds the child-chain growth from Mitigation 1, where there is no cycle to detect.
• Dynamic level check. The same edge map can enforce the level rule of Mitigation 6 at runtime, which is how the static guarantee degrades at the FFI and Wasm boundaries, exactly as typed replies degrade to BAD_INPUT / WrongType there.

Mitigation 5: deadlines #

Erlang's gen_server:call default (5 s) and Orleans's response timeout (30 s). The host owns the clock, so this is a timer per outstanding request, failing with ReplyMissing or a poisoned reply. Crude, but it is the only mitigation that also covers "the peer is slow or dead", which no graph analysis catches, and it is the backstop for growth.

Mitigation 6: ordered channels (levels) #

The lock-ordering idea, transposed: the level goes on the thing waited on — a channel, routine, or resource — rather than on a scoped guard. The rule:

A routine at level n may Ask/Call only channels at level > n.

Every wait-for edge then goes strictly upward, and the graph is acyclic by construction. This is the one row of the table that keeps the blocking call and its atomicity while removing deadlock, and it does so by prevention rather than failure.

  level 0   edge / UI conversations   ──▶
  level 1   application servers       ──▶
  level 2   entities / caches         ──▶
  level 3   storage, external I/O     ──▶  host effects (leaves, level ⊤)

Host effects (Sleep, ReadLine, disk) are leaves: the host is not a routine and cannot wait on you, so they are always allowed. The existing Ctx::ask/call on host effects need no check; only calls routed to other routines do.

Mapping from lock levels #

The transposition is simpler than the lock version because the "hold" is not a scoped guard but an obligation carried for the whole conversation, and the level that governs what you may wait on is fixed: your own. No key needs to be threaded through calls. Using surelock as the reference for the lock version:

lock levels (surelock)	channel levels (proposed)
Mutex<T, Level<N>>	Chan<M, Level<N>> — a handle to a routine's mailbox
MutexKey<Level<K>>, consumed and re-emitted per lock	Ctx<E, Level<K>>, fixed per routine
LockAfter<Before> bound on lock	WaitAfter<Level<K>> bound on ctx.call(chan, …)
Mutex::new_higher(&parent)	child level derived from the channels it will call
LockSet — atomic same-level multi-acquire	Perform::start fan-out — issue all asks first, then await
Bottom	the level of top-level conversations

The LockSet row is the satisfying one: fan-out is already the atomic multi-acquire. Two same-level requests issued together are not contingent on each other, so they need no ordering, for the same reason LockSet may skip levels.

Shape #

pub struct Level<const N: usize>;
pub trait WaitAfter<Before> {}

pub struct Ctx<E, L = Bottom> { /* … */ level: PhantomData<L> }
pub struct Chan<M, L> { addr: Addr, msg: PhantomData<(M, L)> }

impl<E, L> Ctx<E, L> {
    // Waiting on another routine: level-checked.
    pub fn call<A, R, M: WaitAfter<L>>(&self, chan: &Chan<Call<A, R>, M>, arg: A) -> Perform<'_, E, R>
    where
        E: From<Route<A, R>>,
    { /* … */ }

    // Fire-and-forget to another routine: no wait, no check.
    pub fn tell<A, M>(&self, chan: &Chan<Tell<A>, M>, arg: A) { /* … */ }

    // Host effects: leaves, no check. Existing API unchanged.
    pub fn ask<R, F: FnOnce(Ask<R>) -> E>(&self, make: F) -> Perform<'_, E, R> { /* … */ }

    // Children may share the parent's level: the parent→child edge is a tree
    // edge nobody else can reach. Their own calls are checked like anyone's.
    pub fn spawn<F>(&self, child: F) -> Child<L> { /* … */ }
}

The level module of surelock is no_std and independent of mutexes; extracting it, or depending on the crate with default features off, avoids re-deriving the WaitAfter impls. Semantic aliases read well per system: type Ui = Level<0>; type App = Level<1>; type Store = Level<2>;.

This composes with coeffects.md directly — the level is one more requirement in the signature, fn cache<E, L: Below<Store>>(ctx: Ctx<E, L>) — and degrades at the ABI the same way typed replies do: the host's edge map (Mitigation 4) enforces the identical invariant at runtime with a typed LevelViolation reply.

Cost #

• It is a layering commitment. Assigning levels is deciding the architecture. A genuine downcall — level 2 needs level 1's answer, atomically — must be restructured into a Tell plus a callback conversation, a fan-out, or a merge of the two parties. Databases and kernels force the same restructuring, and it is usually right, but it is forced.
• Composition needs offsets. Two libraries with independent level schemes need MaxLevel / new_higher-style shifting.
• It does not bound child-chain growth, because that pattern has no cycle. Deadlines and chain ids remain the tools for it.
• Static only within one host. Across FFI or Wasm the check is dynamic, consistent with everything else at the boundary.

Sans-io has the identical problem #

Take two sans-io machines, A in AwaitingReplyFromB and B in AwaitingReplyFromA. Both step functions have returned; neither is blocked in the thread sense; the host has no effect left to perform. That is a deadlock presenting as an idle event loop. A machine that rejects unrelated inputs while in an awaiting state — the witness_violated arm, or a Result::Err — is doing hold-and-wait: holding its obligations and refusing to progress until one specific input arrives.

So the sans-io actor has the same fork, spelled in its own idiom:

choice	sans-io form	consequence
hold-and-wait	reject or queue inputs while Awaiting…	deadlock across machines
keep stepping	accept other inputs while a request is outstanding	TOCTOU under the pending request
optimistic	version the request, recheck on arrival	redo
levels	order the channels between machines	atomic and deadlock-free

What the mechanism changes is the ergonomics of each leg, and the two designs are mirror images:

• Sans-io makes the reified-state leg cheap — InFlight { waiters } is another variant, and the wait-for graph is readable from the state enums — and the atomic leg expensive, at a state per step of any sub-conversation.
• Effect routines make the atomic leg cheap — the sub-conversation is straight-line code — and the reified-state leg cost explicit work, because the suspension point is invisible and shared state must be lifted into data by hand.

Neither escapes the trilemma; each picks a default quadrant. Sans-io's "a step cannot block" — the property strawman.md §6 credits it with — is not deadlock-freedom. It is that sans-io defaults to the keep-stepping quadrant and hands you the TOCTOU. It gets exactly what "servers never wait" gets, by the same trade, with the wait state written as a value instead of a stack frame.

That makes levels the same answer on both sides: they order channels between machines, and neither mechanism's internals are involved. This is the strongest form of the README's "wire vs. internals" point: deadlock is an actor problem, not an effect-routine problem, and its mitigation lives at the boundary where the two designs already converge.

Recommendation #

Several tools, each covering a case the others do not:

tool	use when	status in this repo
forward the Reply (2)	the answer is only relayed	works today; convention
fire-and-collect (3)	several independent waits; same-level atomic multi-ask	Perform::start
levels (6)	default structural guarantee for stateful parties calling each other	proposed; WaitAfter on Chan, Level on Ctx
InFlight per key, coalesced	shared state with many observers; avoid redo	pattern, no runner support needed
defer and revalidate (1)	the deferred work is state-independent I/O; redo is a cheap re-decision	needs Ctx::spawn for the child form
host wait-for graph + chain ids (4)	runtime enforcement at boundaries; bounding chain growth	proposed; ~40 lines in a scheduler
deadlines (5)	always, as the backstop for slow or dead peers	a timer per Call in each host

And the deterministic-simulation harness (TODO) is how the cycles that survive get found: seeded interleavings, reply reorderings, and an assertion at every step that the wait-for graph is acyclic.

Corrections to earlier documents #

• README.md §"The remaining structural cost" and strawman.md §6 present "servers never wait" as the mitigation and imply it is free. It breaks hold-and-wait, which is also the atomicity of a sub-call; the cost is the TOCTOU-then-redo leg above.
• The discipline was loosely attributed to Erlang. Erlang's clients block; only its servers defer, and the deadlock breaker is the call timeout. The total form is E's and Syndicate's.
• strawman.md §6's "sansio gets the same property from its shape" is true but is not deadlock-freedom; it is the keep-stepping default with its TOCTOU.