# Metastability

In my PhD, I studied the phenomenon of metastability in multi-clock systems.

Metastability is a psuedo-stable state in which a physical system can take an unbounded amount of time before transitioning to a stable state. This is commonly illustrated with the following mechanical analogy:

This is a “ball and hill” dynamical system with two stable states `S1` and `S2`. Assume the ball is initially placed at a random position somewhere on the hill then allowed to roll, measuring the time `t` till it reaches either `S1` or `S2`. You may be able to see that `t` will be higher the closer the initial placement of the ball was to the hill top (call this difference `Δd`). In a Newtonian universe, `Δd` can be infinitely reduced and consequently `t` can be arbitrarily increased. If the ball is initially placed at the hypothetical tipping point itself (`Δd = 0`), it will remain stuck there forever (`t = infinity`).

This begs the following interesting question ...

Is it possible to engineer the hill such that an upper bound can be placed on `t`?

For example, what about the following "clever solution"?

Here, we're attempting to make the ball roll to `S2` faster by changing the hill's shape. Alas, the hill still has a tipping point and `Δd` can still be arbitrarily small.

It's not that the new shape isn't good enough. It is in fact fundamentally impossible to place an upper bound on the resolution time of a continuous multistable system whose initial state is unconstrained. In the example above, no matter the shape of the hill, so long as:

1. there are two stable states, and
2. slope is continuous

then no upper bound can be placed on `t`.

It took decades of elusive failures and many fooled attempts before computer engineers finally accepted this hard truth (and even today, the counter-intuitive nature of the problem is still resulting in numerous design goofs).

So how does this problem affect modern computers?

Modern computers are built from multiple digital components that run with different time references (i.e. different clocks), such as processor cores, memory units and GPUs. Many of these components are synchronous systems but treat signals from their neighbors as asynchronous because they're derived from different time references. On every clock tick, each component must decide whether each of its asynchronous inputs is in a logic high or low state. However, asynchronous inputs can transition at any time, including times that are very close to the decision's tipping point. This situation is essentially the same as the ball and hill analogy: a binary decision is required but the distance to the tipping point (`Δd`) cannot be constrained. In consequence, there will always be a non-zero probability that the component will fail.

In this context a "failure" can refer to arbitrary violations of how the component (and consequently the whole computer) is intended to function. In practice, this can mean things like applications terminating unexpectedly, data corruption or one of the infamous OS fails.

These sorts of failures cannot be avoided but their risk can be arbitrarily decreased by allowing components longer times to decide if their asynchronous inputs are logic low or high (this is analogous to being extra patient before judging whether the ball has reached a stable state). The catch, however, is that the system must suffer a performance penalty because of decision delays.

I published a set of workaround speculation-based solutions that enable computer systems to perform decision-dependent computations before a metastable decision is made. A thorough discussion of these solutions and other thoughts on the problem are published in my PhD thesis.