Contexte et objectif

Le blogueur rapporte qu’aucune avancée notable n’a été publiée depuis les années 2000 sur la composition de systèmes auto‑stabilisants. Face à ce vide, il exploite un modèle TLA+ de « retry storm » composé de deux composants : un retrieur et un serveur. Le modèle montre une défaillance métastable lorsque un choc important supprime l’état de base qui assurait la réciprocité des contrats.

Modèle assume‑guarantee paramétrique

Le texte s’appuie sur le papier de 2017 de Kim, Arcak et Seshia, A Small Gain Theorem for Parametric Assume‑Guarantee Contracts. Dans ce cadre, chaque composant est décrit comme une relation entrée‑sortie sur des signaux, les contrats liant une borne d’entrée à une borne de sortie. L’auteur transpose ce formalisme à son problème en remplaçant le contrat conditionnel « si la file < 6, aucune relance » par une famille de contrats couvrant tous les niveaux de « badness ». Le tableau suivant illustre la fonction λ(L) = ⌊(L‑6)/2⌋ utilisée pour déterminer le nombre maximal de relances en fonction de la longueur de la file L :

L  | λ(L)
---+------
 6 | 0
 8 | 1
10 | 2
12 | 3
14 | 4
16 | 5
18 | 6

Le contrat d’assomption ϕₐ est la disjonction de toutes les hypothèses ψₐ(p) ; le contrat de garantie ϕ_g est la conjonction des implications ψₐ(p) ⇒ ψ_g(λ(p)). Cette construction assure que, quel que soit le niveau d’encombrement, le système possède une promesse explicite.

Application du petit gain et limites

Le petit gain theorem stipule que si le produit des gains g₁·g₂ de deux composants est inférieur à 1, les boucles itératives convergent géométriquement. Dans l’exemple, le retrieur possède un gain constant de ½ (une relance pour deux unités de surcharge), alors que le serveur a un gain variable f/(f+d), dépendant des files fraîches f et dupliquées d. Cette non‑linéarité empêche l’attribution d’un gain unique, violant ainsi l’hypothèse du petit gain.

De plus, le modèle possède deux dimensions de « badness » : q_f (travail frais) et q_d (duplications). Le petit gain théorème ne gère qu’un seul scalaire, ce qui rend l’analyse inapplicable sans une réduction multidimensionnelle non fournie. Enfin, le formalisme est memoryless : il ne capture pas l’accumulation de backlog d’une itération à l’autre, excluant ainsi les files d’attente, élément central des systèmes distribués.

Perspectives pour une théorie compositionaliste

Malgré ces limites, le texte suggère que les idées de paramétrisation et de monotonicité pourraient être intégrées à une théorie de stabilisation. Une approche possible serait d’enrichir les contrats avec des états internes, par exemple en ajoutant un composant « historique » qui mémorise le backlog. Une autre piste consiste à généraliser le petit gain à des fonctions vectorielles, permettant de raisonner sur des paires (q_f, q_d) plutôt que sur un unique indice. En l’état, la composition auto‑stabilisante reste entravée par l’absence d’un cadre formel capable de concilier contrats paramétriques, mémoire d’état et critères de convergence.