Metastable failures

My quest for a principled solution to metastable failures led me back to self-stabilization theory.

No recent work

Recent literature search for composing self-stabilizing systems found nothing useful.

Layered stabilization

The layered stabilization idea was already in place by the early 2000s.

Retry storm model

I composed a rely-guarantee TLA+ model of a retry storm as two components with contracts.

Metastable failure

The composition failed when a large shock removed the base case supporting both conditions.

2017 control theory paper

A 2017 paper by Kim, Arcak and Seshia proposed a small gain theorem for parametric assume-guarantee contracts.

“A Small Gain Theorem for Parametric Assume-Guarantee Contracts”

Component limitations

The paper's component model is memoryless and lacks connection to stabilization.

Memoryless view

This memoryless view cannot express backlog accumulating from previous rounds.

Queue contract

The retrier's guarantee was conditional: 'if the queue is under 6, I send no retries'.

“if the queue is under 6, I send no retries”

Parametric contracts

The paper's approach writes a family of contracts covering all queue lengths.

Queue table

For queue lengths up to 18, the retrier sends at most 0 to 6 retries.

Contract bundle

The contract bundle covers all queue lengths with a disjunction of promises.

Assumption side

The assumption side is a disjunction of queue length levels.

Guarantee side

The guarantee side is a conjunction of obligations across queue levels.

Small gain theorem

The small gain theorem quantifies when a loop settles by multiplying component gains.

Microphone loop

A microphone loop amplifies sound until it creates a high-pitched squeal.

Gain multiplication

After k laps, the nudge is multiplied by (g1 * g2)^k.

Stability condition

The product of gains must be under one for the system to stabilize.

Queue dynamics

The system tracks both fresh and duplicate queues with their own evolution rules.

Equilibrium point

The system reaches equilibrium at (8,4) where queues balance exactly.