Characterizing Metastable Faults and Failures
Metastability has been studied in previous work as a self-sustaining degradation in goodput that persists even after the trigger is gone. The degraded state loiters on entirely due to the system's own internal feedback loops (retries, queues), and there is no simple reset button to press in distributed systems. So this is not a rare exotic problem. Since production systems would have already been hardened to handle the obvious failures, what remains is these hard-to-detect emergent failures. The "Metastable Failures in the Wild" paper (OSDI'22) reports 22 incidents across 11 organizations. Four of the 15 major AWS outages in a decade were metastable failures, with durations ranging from 1.5 to 73 hours.
This paper (June 2026) argues that the systems community has treated metastability phenomenologically, which led people to chase symptoms rather than causes. The paper sets out to give the first analytical causal account of these failures. This framing leads to two connections I found delightful. The first casts a metastable failure as a sin of composition among self-stabilizing systems. The second ties the healing mechanism to scheduling. Since I have worked on self-stabilizing systems for a long time (between 1998-2010), and thought hard about how they compose, these two connections really excite me.
I do have some reservations, though, which I will get to in my review. The paper overlooks prior work on the composition of stabilizing systems. It also pulls a bit of a sleight-of-hand in its formalization to argue that the metastable fault tolerance (MFT) design can be done via local pairwise reasoning between components. I don't buy that as I explain below.
These reservations do not dampen how much I enjoyed this paper. This is an idea paper, and it has been a while since I saw one of these in distributed systems. Moreover, the author list includes two of my all-time favorite distributed systems researchers: Robbert Van Renesse and Lorenzo Alvisi.
So let's dive in.
Sins of Composition and Self-Stabilization
The authors give formal definitions of a metastable fault and a metastable failure, and they draw a distinction between the two.
A metastable fault is what they beautifully call a sin of composition. (I am guessing this is Lorenzo being poetic.) Loosely speaking, the metastable fault appears when two or more components that are perfectly stable on their own get wired together into a cyclic interference/destruction loop. When a shock (say overload or loss of cache) then triggers the system, each component runs its local corrective action to stabilize itself, and in doing so it destabilizes its neighbor.
Let me back up and explain self-stabilization. A self-stabilizing system can start in any state and, with no outside intervention, converge on its own to a legitimate state and stay there. It lays out an elegant unified framework to tolerate any transient fault: A transient fault just leaves the system in some arbitrary state, and stabilization gradually heals it from there.
The paper leans hard on this stabilization theory going back to the 1980s. It defines a potential function (also called a variant or metric function) $f$ for each component, measuring how far the component is from a good state. A component is stabilizing if it eventually drives $f$ to zero, provided it runs inside a well-behaved "environment" $E$.
To formulate composition of stabilizing components, they add a compatibility check: if component A can stabilize when B is stable, and B can stabilize when A is stable, the two are compatible. But compatibility is not enough for guaranteeing composition of stabilization. Right after a shock, neither component is stable, so they hit a bootstrapping problem. Each waits for the other to recover first, and they get stuck in mutual destabilization, as their actions during recovery interfere with each other's healing progress.
This "sin of composition" is defined as the metastable fault. The fault turns into a failure only when the shock lands and the system's scheduler keeps favoring the locally stabilizing but globally destabilizing interactions over the stabilizing ones.
None of this surprises a stabilization researcher. Stabilization is famously hard to compose, precisely because the recovery strategies of the components interfere with each other. The challenge is to keep the components from corrupting each other during recovery. One clean way is layered composition: let the lower layer stabilize first (the higher layer can read it but not write to it), and let recovery flow upward. In general, though, when you compose systems you have to design the correction actions deliberately, check that they don't interfere, and prove they stabilize together.
Overreaching for Local Reasoning
The paper's theoretical framework defines metastability nicely, however, I disagree with the claim that finding and fixing the fault is a local pairwise activity. That claim rests on the developer guessing the right potential function $f$ and the right environment predicate $E$. And it is not possible to derive a good potential function without reasoning about the system globally.
It is also worthwhile to discuss about the environment predicate $E$. In the classical stabilization literature, $E$ is usually trivial or vacuous, because a self-stabilizing system is supposed to recover from any state. The paper improves on this for compositionality by defining $E$ to capture the assumption that a component's neighbors behave well. But this generalization punts the hard parts to the developer: which environment predicate actually holds for the composed components, and which potential function is right for each component. These are questions that require global reasoning. Assuming a benevolent environment predicate $E$ in which everything else behaves perfectly ignores the reality that in a distributed system the "environment" is the other components, which are just as likely to be failing. Note that both the Definition 3 (compatibility) and Definition 4 (destabilizing action) quantify over a single global environment predicate E for the whole composition.
Use the Graph to Fix, Not Just to Flag
The authors extract a composition blueprint, a directed graph of writes-to relations among components, which they search for cycles of destabilizing actions. But they use the graph only defensively, to flag faults. Once a fault is found, the proposed fix is to hand-inject ad-hoc timers that delay the destabilizing actions.
This leaves the constructive side of self-stabilization on the table. Leal and Arora's "Scalable self-stabilization via composition" (ICDCS 2004) showed you can enforce correct composition by leveraging this graph directly. The motivation for Leal (my academic brother) and Arora (my advisor) was to address the interference problem between actions which forces global reasoning over the whole system, and that reasoning explodes as systems grow. The key idea in their framework was to make two relations explicit: for each component, which other components it can corrupt, and which components must be corrected first before it can correct itself. Given per-component stabilizers (detectors and correctors), they offer several ways to coordinate correction depending on what you actually know about the corruption and correction relations. This framework aims to reduce design and reasoning to local activity between a component and its neighbors in order to allow local recovery and avoid blocking of components and distributed reset as much as possible. In other words, it proposed a topological answer to the sins of composition. Instead of guessed empirical timers and tentative scheduling, you use the direction of the edges to enforce the scheduling discipline.
I ran into a similar problem in my own work, "A hierarchy-based fault-local stabilizing algorithm for tracking in sensor networks". There we used layered/hierarchical healing, and tuned the timing of the corrective actions: we deliberately delayed the propagation waves of correction to higher levels of the hierarchy, so that more recent waves from lower levels could catch up. That delay gave us fault-local stabilization instead of a global cascade of corruption.
Scheduling as a First-Class Citizen
The paper also introduces Nyx, a DSL that forces you to model queues and resources explicitly and promotes the scheduler to a first-class citizen. The goal is to defer destabilizing interactions until stabilizing ones have achieved global stability. I like the intuition, but I think the paper reaches too far, and assumes a "God scheduler" that can serialize and control all concurrent actions from above. A central coordinator like that does not scale, and is not feasible to have in distributed systems. But the good news is that once you have framed the problem as a scheduling problem, you may not need a God scheduler to fix it. You can implement the fix with locally tuned timers. You don't have to be perfect; you only have to rig the odds toward stabilization.
Reading this paper gave me a concrete next step for MESSI, the metastability simulator tool Aleksey Charapko had developed to catch failures that hide in the seams between system components. We introduced MESSI in our recent paper, "A Case for Simulation-Driven Resilience in Agentic Data Systems". It models any subsystem as a graph of Logic Nodes (which express policy: where does this work go next?) and Processors (which express resource constraints, via delays for both service time and queuing time). Runs are deterministic and replayable, with full internal state captured every tick, and the runtime is scriptable, so you can inject failures, slowdowns, and config changes mid-run. The premise here is that production is too complex to tune by trial and error, so we need to trace how overload propagates before we deploy. To explore the effects of scheduling in MESSI, we can add a ~SendAt()~ method, that allows delaying a potentially destabilizing message by a prescribed amount.
In sum, this is a thought-provoking paper. It correctly reframes metastability: not a mere symptom of overload, but a fundamental failure of recovery to compose across distributed boundaries. A metastable fault becomes a failure only under destructive interference among components. I think the paper's formal verification framework demands too much subjective guesswork to be practical, and its bet on the scheduler as a central coordinator may not be feasible. But the diagnosis of metastability is really a good one. Once you can name the interference (the sin of composition), accounting for it becomes a much more tractable problem.
Finally, I am adding a link to my marked up copy of the paper. Even with the availability of LLMs, I still believe in deep manual reading, and illustrating one's thought-processes to teach/train others.
Comments