State-Machine Cycle Detection¶
Analytical method — instantiates Progress-Guarded Livelock Disruption
Models the coupled actors as one state machine and finds the non-progress cycle in its reachability graph — the exact set of states they keep revisiting.
State-Machine Cycle Detection treats the whole coupled system as a single state machine: each actor's move is a transition, and the joint configuration is a state. It then looks for the thing that a watchdog can only sense as silence — a cycle in the reachability graph: a set of joint states the actors keep re-entering while the progress measure never advances. Where a timeout says only that the system is stuck, this method says which states form the loop and how the actors' responses close it. Its defining move is to compress the loop into a reusable cycle signature — a fingerprint of the offending pattern — so the same livelock can be recognized on sight the next time it forms, instead of re-diagnosed from scratch.
Example¶
Two routers at a network boundary begin route flapping: router A withdraws a route, B recomputes and re-advertises an alternate, which makes A re-advertise the original, which makes B withdraw again — the tables churn continuously, updates propagate outward, but reachability never settles. Modeled as a state machine, each router is a small set of route-advertisement states and the pair's joint state is the product. Running visited-state detection over a captured update stream, the cycle pops out: the joint states (A: primary, B: alt) → (A: primary, B: primary) → (A: alt, B: primary) → back, none of which improves a convergence measure. That loop is recorded as a signature — "A↔B two-route oscillation" — and the fix (a dampening hold, or a tie-break making one router authoritative) is aimed precisely at the states the signature names, rather than at the general symptom of churn.
How it works¶
The method builds a transition model of the coupled actors — who responds to whom, and how — then walks the resulting joint-state graph looking for a strongly connected region the system cannot leave while the progress invariant stays flat. At runtime this is often done cheaply by hashing each visited joint state and flagging a re-visit that carries no progress; offline it can be a full reachability analysis in the style of model checking, where a livelock shows up as a reachable cycle with no progressing exit. Either way, the output is not an alarm but a structure: the states in the loop, the responses that close it, and a signature stored for reuse.
Tuning parameters¶
- State abstraction — how coarsely a "joint state" is defined. Coarse states make cycles easy to find but blur distinct loops together; fine states distinguish them but explode the graph.
- Detection mode — runtime visited-state hashing (cheap, reactive, live) versus offline reachability analysis (exhaustive, predictive, expensive). Match it to whether you need to catch this livelock now or prove a class of them cannot happen.
- Signature granularity — how much of the loop the stored signature captures — just the state set, or the triggering responses too. Richer signatures match more precisely but recognize fewer near-variants.
- Progress predicate — the measure a genuine transition must advance; loosen it and benign oscillations get flagged as livelocks, tighten it and real stalls slip through as "progress."
When it helps, and when it misleads¶
Its strength is explanatory: it converts "we're stuck" into "here is the loop, these are the states, this response closes it" — which is what lets a fix target the mechanism of the livelock instead of its symptoms, and lets the same pattern be caught instantly on recurrence via its signature. It is the diagnostic that makes the other interventions aimable.
Its costs are the costs of modeling. The joint-state space suffers combinatorial explosion: for many coupled actors the graph is too large to enumerate, and the model is only as faithful as the transition map fed into it — a missing response or a too-coarse abstraction hides the very cycle you are hunting. It is also mostly a diagnosis, not a cure; naming the loop does not break it. And a stale signature registry can mislabel a new failure as an old one. The discipline is to keep the abstraction as coarse as it can be while still separating distinct cycles, to treat detection as input to an intervention rather than a resolution, and to age out signatures as the system evolves.[n1]
How it implements the components¶
State-Machine Cycle Detection realizes the archetype's structural-diagnosis side — the components that characterize the cycle, not the ones that sense a stall or reset the system:
non_progress_cycle_detector— its core act: finding the reachable cycle of joint states that carries no progress.cycle_signature_registry— it distills each detected loop into a reusable fingerprint and files it, so recurrences are recognized rather than re-diagnosed.coupled_actor_response_map— it builds the transition model of which actor's move triggers which, the substrate the cycle search runs over.
It does not sense a stall at runtime and reset — that black-box deadline-and-recovery job is Liveness Watchdog's (joint_state_progress_invariant, recovery_checkpoint_and_reentry_rule) — nor emit the raw progress signal (Progress Counter Heartbeat's liveness_observability_signal), and it does not change the coordination rule the loop exposes — that is Quiescence Barrier's or Randomized Retry Desynchronization's work.
Related¶
- Instantiates: Progress-Guarded Livelock Disruption — it supplies the structural account of the livelock that the interventions are then aimed at.
- Sibling mechanisms: Liveness Watchdog · Progress Counter Heartbeat · Joint-State Cycle Trace · Contention Trace Replay · Quiescence Barrier · Randomized Retry Desynchronization · Bounded Priority Rotation · Leader Election or Token Passing · Circuit Breaker and Cooldown · External Arbitration/Escalation · Exponential Backoff with Jitter
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: State-Machine Cycle Detection operates as an analytical, modeling, inference, comparison, or optimization procedure that derives insight or a solution because it models the coupled actors as one state machine and finds the non-progress cycle in its reachability graph — the exact set of states they keep revisiting.
Independent corroboration: The frozen evidence defines State-Machine Cycle Detection as 'Models the coupled actors as one state machine and finds the non-progress cycle in its reachability graph — the exact set of states they keep revisiting', so its operative form is Analysis, Modeling & Optimization.
Nearest alternative: Monitoring, Sensing & Alerting — State-Machine Cycle Detection includes features of ongoing observation, sensing, or alerting that detects and surfaces state without itself executing the response, but its defining operation is an analytical, modeling, inference, comparison, or optimization procedure that derives insight or a solution.
Review outcome: Independent reviewer agreement; medium confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Single lineage
Present-day reach: Multi-domain
Rationale: Finding repeated nonprogress states is graph cycle detection on a state machine.
Related originating lineages:
- Engineering & Design — Engineering design, reliability, and systems-safety practice supplies a parallel or contributing lineage for the mechanism's defining operation: models the coupled actors as one state machine and finds the non-progress cycle in its reachability graph — the exact set of states they keep revisiting.
- Mathematics — Graph theory formalizes cycles.
- Systems Thinking & Cybernetics — Feedback explains persistence.
Review resolution: The blind reviewers agree that computer_science is the primary origin and differ only on alternate origin disagreement, domain reach disagreement. I preserve every independently explained alternate from both records rather than imposing a numeric cap. I retain single_lineage because the combined evidence shows one traceable formative lineage. The broader reach of multi_domain records portability separately from historical provenance; encyclopedia_synthesis=false preserves the affirmative synthesis judgment where either reviewer identified one.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
It is worth separating this method from its two trace-based siblings, since all three touch cycles. State-Machine Cycle Detection reasons over the model — the joint-state graph — and can therefore find loops that a given run never happened to exhibit. Joint-State Cycle Trace instead reads the empirical time-ordered log of joint states and finds where a real run looped; Contention Trace Replay re-runs a recorded contention to reproduce it. Model-first detection generalizes and can even prove a class of livelocks impossible; trace-first detection is grounded in what actually occurred. They are complements, not substitutes.
[n1] In liveness-oriented model checking a violation characteristically appears as a "lasso" — a finite path leading into a cycle that the system can traverse forever without satisfying its progress goal. Naming the reachable non-progress cycle is exactly what this method borrows from that setting; the caveat it also inherits is state-space explosion, which is why the state abstraction is the first dial to reach for. ↩