State Machine #
state machine = state + allowed transitions + invariants
It answers:
what states can this thing be in,
what events/actions move it,
and what must never be violated?
Role in the catalog: substrate, not peer. Queues, schedulers, boundaries, transactions, controllers, and protocols are built out of state machines. This block owns the formalism; the component blocks own their instantiations.
Central tension:
simple explicit states vs concurrency, retries, partial failure, and ignorance
Design Axes (the core module) #
Axis 1 — Locus of Transition Authority (who may transition it) #
single actor: one process owns the object (local FSM, cache entry)
two peers: legal message order = shared FSM (TCP, TLS, xDS ACK/NACK)
contested object: many concurrent actors, one object (k8s resource: scheduler +
controllers + kubelet + user)
replicated: many replicas apply identical
ordered commands (Raft/Paxos, etcd)
Each locus dictates its guard machinery:
single -> ordinary code discipline
peers -> phase checks; reject message-in-wrong-phase
contested -> optimistic concurrency: generation / resourceVersion / CAS on every write
replicated -> consensus orders first; apply must be deterministic
Interrogation:
Can two actors transition it concurrently? What rejects the loser?
Is a "transition" a local write, an accepted message, or a committed log entry?
For replicated: is command application deterministic? (wall clock, randomness, map order = bugs)
Axis 2 — Persistence & Reconstruction #
ephemeral: state lives in memory; crash = reset (connection object)
snapshot: current state persisted; history discarded (row with status column)
event-sourced: history persisted; state derived by replay (Temporal, ledger)
replicated log: consensus-ordered history; snapshot to compact (Raft log + snapshots)
Interrogation:
Can the machine be reconstructed after a crash? From what?
Event-sourced: is replay deterministic? (Temporal's entire discipline is this)
Snapshot: does the status column lie about reality? (status is a cached claim)
What compacts history, and does compaction destroy needed reconstruction?
Axis 3 — Transition Driver #
edge-triggered: events cause transitions; missing an event = wrong state
(TCP, TLS, classic FSM)
level-triggered: observe world, compute next transition toward desired state;
missing events is fine — convergence, not delivery
(k8s reconcilers)
timer-driven: timeout as first-class event; both styles fold it in
(TIME_WAIT, lease expiry, half-open probe)
The deep consequence:
edge-triggered -> demands reliable, ordered event delivery (or explicit resync)
level-triggered -> tolerates lost/coalesced events; latest-wins queues become safe
(this is why controller workqueues may dedupe — see queue.md)
Interrogation:
If an event is lost, is the machine wrong forever or eventually convergent?
What happens on timeout — and is timeout distinguished from failure? (it isn't; see axis 5)
Does every state have an exit timer, or can it wait forever?
Axis 4 — Side-Effect Coupling #
pure: transitions touch only own state
effectful: transitions fire external actions
For effectful machines, the ordering of {external effect, recorded transition} is exactly the commit point* — owned by queue.md, referenced here:
effect then record -> crash between = effect repeated on recovery
record then effect -> crash between = effect never happens (or replay re-derives it)
recipes: idempotent effects, transactional outbox,
record-intent / execute / record-result (Temporal's event-sourced sandwich)
Similarly, “status vs truth” is scheduler.md’s decision-view vs reality* — status/phase fields are cached claims about the world, guarded by generation/observedGeneration, corrected by feedback loops.
Interrogation:
Which transitions have side effects? Are they idempotent?
Is the effect before or after the durable transition record? What does a crash between them cost?
Does status carry the generation it observed? Can it describe an old spec?
Axis 5 — Adversity Completeness (is the state space honest?) #
The happy path is a fraction of the real state space. A production machine needs:
states for ignorance:
Unknown (2PC prepared, coordinator dead — outcome exists, you can't know it)
Suspect (SWIM's contribution: a state between alive and dead)
Half-open (circuit breaker: probing, neither trusting nor condemning)
TIME_WAIT (TCP: guarding against the network's own stale ghosts)
adverse events as legal alphabet, with drawn edges:
duplicate event -> idempotent transition (self-loop, not exception)
stale event -> generation/epoch guard rejects (a drawn edge, not a crash)
out-of-order -> phase guard rejects or buffers
missing event -> timeout edge exits the wait
Interrogation:
For every state: what if the expected event never arrives?
For every event: what if it arrives twice? late? from a previous epoch?
Which states are terminal, and does everything eventually absorb into one?
Is "Unknown" a state or an unhandled exception?
Technical Bottleneck: Modeling Ignorance* #
distributed machines cannot always know their own outcome.
you cannot design ignorance away —
you can only give it a state, a timer, and an exit.
Essential, no general solution. The canonical instances:
2PC Prepared + dead coordinator participant must block or guess
timeout indistinguishable from failure — always
half-open connection peer's view and yours diverged
lease expired mid-work old owner doesn't know it's old
crashed after effect, before record did it happen? (commit point's shadow)
Known recipes (bounded, none universal):
explicit Unknown/Suspect states with timeout-driven exits
epoch/generation/fencing guards on every transition
idempotent transitions (duplicate -> self-loop)
probing states (half-open) that convert ignorance to evidence cheaply
terminal-state absorption + TIME_WAIT-style quarantine of ghosts
A strong design says explicitly:
what states exist (including ignorance states),
what transitions are legal (including for duplicate/stale/missing events),
what invariants hold in every state,
which transitions have effects and where the commit point sits,
and how the machine is reconstructed after a crash.
Design Protocol (the checklist — keep) #
define states (include Unknown/Suspect/terminal)
define events/actions (include duplicate/stale/timeout in the alphabet)
define allowed transitions (illegal = drawn rejection, not surprise)
define guards (generation/epoch/phase checks)
define side effects per transition (+ commit-point placement)
define timers/timeouts (every waiting state gets an exit)
define retry/recovery transitions
define invariants (checkable in every state)
define persistence + reconstruction path
Instantiation Index (this block, appearing elsewhere) #
Not types — cross-references. Each row = the component block’s object, read as a vector on the five axes.
| Instantiation | Vector highlights | Owned by / study object |
|---|---|---|
| Queue item lifecycle | contested (workers), snapshot, edge, effectful — commit point lives here | queue.md; SQS visibility lease |
| Scheduler work item | contested, snapshot+generation, edge→level mix, binding = recorded transition | scheduler.md; Pending→Bound→Running |
| Controller/reconciler | contested object, snapshot+observedGeneration, level-triggered, idempotent effects | k8s reconcile loop |
| Resource lifecycle | contested, snapshot, level, deletion via finalizers (stuck-deleting = missing timeout edge) | Pod phases + finalizers |
| Protocol handshake | two peers, ephemeral, edge, phase guards | TCP/TLS; xDS ACK/NACK |
| Session/liveness | two peers + timers, ephemeral+server-side record, edge, Suspect states | ZooKeeper session; SWIM |
| Workflow | single logical actor, event-sourced, edge+timers, record-intent/execute/record-result | Temporal replay |
| Transaction | contested via coordinator, snapshot/log, edge, Unknown is the famous state | 2PC as cautionary baseline; saga = compensation edges |
| Replicated SM | replicated, log+snapshot, edge (ordered commands), effects must be deterministic | Raft |
| Failure-recovery | single, ephemeral-ish, timer-driven, half-open probing | circuit breaker open/half-open/closed |
Vocabulary #
state transition event action guard
precondition postcondition invariant
initial terminal absorption
timer timeout retry
generation epoch fence phase
history replay determinism snapshot compaction
idempotency side effect compensation
status observedGeneration
Unknown Suspect half-open quarantine
Deep Lesson #
State-machine bugs come from confusing pairs on different axes:
status vs truth (axis 4: cached claim vs reality — scheduler.md*)
event vs transition (an event is a proposal; guards decide)
retry vs safe repetition (axis 5: duplicate must be a drawn self-loop)
terminal vs temporary (missing absorption; stuck-deleting)
timeout vs failure (axis 5: timeout is ignorance, not evidence)
side effect vs committed transition (axis 4: commit point — queue.md*)
local state vs distributed state (axis 1: locus decides guard machinery)
happy path vs complete state space (axis 5: the native bottleneck*)
Design procedure: fix the locus, choose persistence, choose the driver, place the commit point, then complete the state space against ignorance. The domain instantiations live in their own blocks; this file owns the formalism.