У пошуках композиційної теорії самостабілізації

Допис від 21 вересня 2026 року в блозі Metadata ставить питання, чи існує композиційна теорія самостабілізації. Пошук принципового пояснення метастабільних відмов повернув автора до самостабілізації, а огляд літератури про композицію самостабілізованих систем не дав нічого корисного. Його приклад — rely-guarantee TLA+ модель шторму повторів із двох компонентів із контрактами, яка відтворює метастабільну відмову, коли шок прибирає базовий випадок, що тримав обидві умови.

Від однієї обіцянки до родини контрактів

Пошук композиції rely-guarantee з кожного стану вивів на статтю з теорії керування 2017 року (Kim, Arcak, Seshia). Вона знімає циклічні міркування між компонентами без шарування та блокування, але компонент тут — непам'ятна модель «вхід-вихід» на сигналах: беклог виразити неможливо, черги недосяжні, про стабілізацію не сказано.

Ідею все ж варто позичити. Замість однієї обіцянки з передумовою — «якщо черга менша за 6, повторів не надсилаю» — пишеться родина контрактів на всі випадки: хоч яка довжина черги L, компонент надсилає не більше ніж λ(L) повторів. З константами моделі таблиця йде від «черга до 6 → 0 повторів» до «черга до 18 → 6 повторів»; бік припущень — диз'юнкція, бік гарантій — кон'юнкція.

Чому короткий шлях малого підсилення не працює

Теорема малого підсилення каже, що петля заспокоюється, коли добуток підсилень компонентів менший за одиницю. Тут заважають дві речі: потрібні прямі лінії, але фіксований нахил має лише ретраєр (1/2), тоді як частка сервера поводиться як f/(f+d); і припускається, що «погане» — одне число, тоді як черг дві: свіжа робота та дублікати.

Стеження за обома дає нерухому точку (8,4) і чотири нахили. Діагональні, 11/12 і 5/6, — пам'ять: частка черги, що лишається на наступний раунд. Позадіагональні, 7/12 і 1/6, — зв'язок між чергами. Множення лише зв'язку дає 7/72 ≈ 0.1 — «стабільність із десятикратним запасом», і це хибно, бо ігнорує пам'ять. Коректний аналіз стійкості дає 1.19 і 0.56: власні значення в сумі 1.75, одне понад одиницю, тож майже будь-яке збурення зростає.

Відомі виправлення і стеля, яка не рятує

Арифметика пояснює й відомі виправлення. Бюджет повторів обнуляє 7/12, «свіже спершу» — 1/6. Тоді множники повертаються до 0.92 і 0.83, і беклог спадає на 8% за раунд замість зростання на 19%. Обмеження черг — той самий хід: межа M дає не більше ніж (M−6)/T повторів. За M=7 повторів немає; за M=8 дозволено один, і з'являються інші атрактори. Понад 8 симуляція показує: стеля обмежує розбіжність, але не запобігає відмові. За M=40 система зупиняється в (39,38): з трьох одиниць за раунд одна робить корисну роботу, а дві йдуть на дублікати вже надісланих запитів — це визначення метастабільності.

Підсумок частковий. Стаття дала кращий спосіб записати обіцянку компонента як родину контрактів, але не рецепт композиції, і її непам'ятна скалярна модель не підходить до прикладу. Чотири нахили автор дістав, виписавши обидві черги разом — на цьому кроці від композиції відмовився. Утім, кожен елемент таблиці належить одному компоненту: 7/12 — це 1/2 ретраєра плюс 1/12 сервера.