Warum die Small-Gain-Theorie bei Retry-Stürmen versagt
In Search of a Compositional Theory of Self-Stabilization
Murat Buffalo sucht nach einer kompositionellen Theorie der Selbststabilisierung und stößt auf ein Paper von Kim, Arcak und Seshia aus dem Jahr 2017 über parametrische Assume-Guarantee-Verträge. Deren Small-Gain-Theorem liefert ein globales Stabilitätskriterium, ignoriert aber Gedächtnis und zwei gekoppelte Warteschlangen. Am Beispiel eines Retry-Sturms zeigt er, dass die tatsächliche Verstärkung pro Runde 1,19 beträgt – also über eins liegt – und das System dadurch instabil wird.
Wenn wir das Gedächtnis berücksichtigen, wird der tatsächliche Multiplikator pro Runde 1,19, was über eins liegt, sodass fast jede Störung wächst statt abzuklingen.