探索自稳定的组合式理论

# 探寻自稳定化的组合化理论 来源：http://muratbuffalo.blogspot.com/2026/09/in-search-of-compositional-theory-of.html 我对亚稳态故障 ([https://muratbuffalo.blogspot.com/2023/09/metastable-failures-in-wild.html](https://muratbuffalo.blogspot.com/2023/09/metastable-failures-in-wild.html)) 原则性解决方案的探索，将我带回到自稳定化的根基 ([https://muratbuffalo.blogspot.com/search?q=stabilizing](https://muratbuffalo.blogspot.com/search?q=stabilizing))，因为最近的一篇论文将该问题与自稳定系统的组合 ([https://muratbuffalo.blogspot.com/2026/07/characterizing-metastable-faults-and.html](https://muratbuffalo.blogspot.com/2026/07/characterizing-metastable-faults-and.html)) 联系了起来。然而，我搜索关于组合自稳定系统最新工作的文献，却没有找到任何有用的东西。分层稳定的概念在2000年代初就已存在，此后似乎没有增加任何根本性的进展。令人沮丧。 因此，我决定用我手头的具体例子来攻克这个问题。我曾用两个带契约的组件，组合了一个重试风暴的**依赖-保证** TLA+ 模型 ([https://muratbuffalo.blogspot.com/2026/09/metastability-as-failed-conditional.html](https://muratbuffalo.blogspot.com/2026/09/metastability-as-failed-conditional.html))。该模型复现了亚稳态故障，因为从良好状态出发的组合在发生巨大冲击、破坏了支撑两个条件相互依存的基础情况时，就失效了。 搜索基于**依赖-保证**、从任意状态出发的组合方法，我找到了Kim、Arcak和Seshia在2017年发表的一篇控制理论论文，“参数化假设-保证契约的小增益定理” ([https://dx.doi.org/10.1145/3049797.3049805](https://dx.doi.org/10.1145/3049797.3049805))。这篇论文大致做了我想要的事：无需分层或阻塞，就能解决两个组件之间的循环推理问题。但它存在一些严重的局限性。在他们的形式化框架中，组件是信号上的输入输出关系，契约将输入边界与输出边界联系起来。这是一种对组件无记忆的视角，因此无法表达从之前几轮累积的积压。这排除了队列以及其他一些有用的分布式系统概念。它也与稳定化毫无关联。该论文没有讨论变体/势函数以及收敛推理。但其中仍有值得借鉴的部分，可用于构建自稳定化和亚稳态的组合理论。下面我尝试阐述这一点……但不太成功。 ## 理解参数化假设-保证契约 在我们最初的模型中 ([https://muratbuffalo.blogspot.com/2026/09/metastability-as-failed-conditional.html](https://muratbuffalo.blogspot.com/2026/09/metastability-as-failed-conditional.html))，重试器的保证是有条件且部分的：“如果队列低于6，我不发送任何重试”。这个契约没有说明队列长度为18时的情况。由于“if”条件不成立，承诺被空洞地满足，组件不欠我们任何东西。 参数化假设-保证论文的要点是，编写一整套覆盖所有情况的契约族，而不是编写一个带有前提条件的单一承诺。 **过时的方式：** *如果队列低于6，则不重试。* **新颖的方式：** *无论队列长度 $L$ 最终是多少，我最多发送 $\\lambda\(L\)$ 次重试。* 回忆一下我模型中的常数：每轮服务器容量 $S=3$ 个单位，每轮最大新到达量 $A\_\{max\}=2$，重试超时为 $T=2$ 轮，这使得延迟阈值为 $S \cdot T = 6$。这给出 $\\lambda\(L\) = \lfloor \(L\-6\)/2 \rfloor$，我们得到： | 如果队列最多为... | 我最多发送这么多重试 | |-------------------|----------------------| | 6 | 0 | | 8 | 1 | | 10 | 2 | | 12 | 3 | | 14 | 4 | | 16 | 5 | | 18 | 6 | 旧的契约仍然存在，对应表格的第一行：$\\lambda\(6\)=0$ 表示“队列低于6意味着最多零次重试”。尽管在队列长度为18时旧契约无效，但在参数化假设-保证方法下，表格的每一行都得到了承诺。因此，我们得到了一组普通契约，每个坏情况级别 $p$ 对应一个： $$\\varphi\_a = \\bigvee\_p \\psi\_a\(p\)$$ $$\\varphi\_g = \\bigwedge\_p \\left\( \\psi\_a\(p\) \\Rightarrow \\psi\_g\(\\lambda\(p\)\) \\right\)$$ 假设方 $\\varphi\_a$ 是析取式，因为这些级别是环境可能处于的备选项。“队列最多6，或最多8，或最多10，或...”基本上任何环境都能满足，因此没有环境能逃脱这个范围。 保证方 $\\varphi\_g$ 是对这些相同级别的合取。由于义务是累积的，我们必须同时满足所有义务。条件为假的行不会给我们带来任何成本，并且由于这些级别是嵌套的，多个级别同时适用，最严格的约束胜出。当队列为7时，“最多8”适用，组件最多欠我们1次重试；“最多10”也适用，它最多欠我们2次，但第一种情况已经蕴含了这一点。单调性在此变得关键。 ## 推导小增益规则 那么，是什么规则决定了这样一个循环会收敛？论文称之为小增益定理。让我先解释一下直觉。 你见过这种情况吧？当麦克风对着扬声器时，麦克风拾取声音，放大器将其放大。扬声器播放回来，麦克风再次拾取。每绕这个循环一圈，声音都会被放大，你就会听到尖锐的啸叫。 为了量化这个过程，我们需要每个组件一个数字：单位坏情况输入产生多少坏情况输出。这就是组件响应函数的**斜率**，控制理论称之为组件的**增益**。 当我们链接两个组件，并向第一个组件输入一个扰动 $x$，斜率为 $g\_1$，输出 $g\_1 x$。将其输入第二个组件，斜率为 $g\_2$，输出 $g\_2 g\_1 x$。绕一圈使扰动乘以 $g\_1 g\_2$。经过 $k$ 圈后，扰动变为原始大小的 $\(g\_1 g\_2\)^k$ 倍。如果乘积小于1，圈数以几何级数减小，循环收敛。如果大于1，则发散。证明来自几何级数。 小增益定理非常优雅，它给我们一个全局结果，一次性覆盖所有起始状态。但小增益设定是有局限的。在我们的情况下，有两件事阻止我们使用这个捷径。 首先，这需要直线。我们的重试器有线性斜率 $1/2$，但我们的服务器没有。它的服务份额按 $f/\(f\+d\)$ 比例分配，因此它的斜率取决于队列的位置。所以，没有一个单一的数字可以相乘。 其次，更糟的是，该捷径假设坏情况是一个数字。我们的系统有两个行为不同的队列：新工作 $q_f$ 和重复工作 $q_d$。对一个的约束不是对另一个的约束。因此，绕我们的循环一圈，需要一对数字映射到另一对数字。 这两个局限性背后，都是我在引言中抱怨的组件无记忆视角。在此设定中，增益是一个输入输出关系：它说明到达的东西有多少被传递下去。其中没有考虑我自己之前的积压还剩下多少。队列主要是积压，这就是下一节要讨论的内容。 ## 处理两个队列和四个斜率 让我们同时跟踪两个队列。我们可以将一轮写成作用于一对（新队列 $f$，重复队列 $d$）的规则：应用到达，应用重试，应用比例服务分割来计算下一对。然后我们问是否有任何一对映射到自身。 有一对：$\(f,d\) = \(8,4\)$。这里总队列为12，所以三单位容量分配两个给新队列，一个给重复队列。两个新服务恰好抵消了两个到达。重试率为 $\(8\-6\)/2 = 1$，一个重复服务恰好抵消了它。因此，接下来的几轮，队列仍然保持平衡。 问题是，如果我们从这个平衡点附近开始会发生什么。从 $\(9,4\)$ 开始，系统会回落还是逃逸？为了回答，我们需要知道一个小扰动如何传播。 我将省略计算过程，但表格如下： | | 对下一 $\f$ 的影响 | 对下一 $\d$ 的影响 | |--------|-------------------|-------------------| | 每单位 $\f$ | $11/12$ | $7/12$ | | 每单位 $\d$ | $1/6$ | $5/6$ | 让我们从对角线开始。这里我们考虑如果在一个队列中增加一个项目，下一轮该队列会增大多少？对于这个推理，只涉及服务器，我们得到 $11/12$ 和 $5/6$，它们是该项目在下一轮仍留在那里的比例。 现在，让我们考虑非对角线项，它们是关于跨队列交互的。如果你在这个队列中增加一个项目，下一轮会对另一个队列造成多大的冲击？服务器参与这个计算，因为一个队列拿走的东西会因服务器处的工作分配而使另一个队列损失。重试器也参与其中，因为它的待定计数跟踪新队列，并且它发送的重试会落入重复队列。数字 $7/12$ 包含来自重试器的 $1/2$（当 $T=2$ 时，新队列中一个额外项目最终会产生一个额外重试，但分布在两轮中），加上来自服务器的 $1/12$。另一个非对角线数字 $1/6$ 仅来自服务器，由于额外的重复项稀释了新队列在 S=3 容量分割中的份额。 ## 追踪不稳定性的根源 论文的小增益定理建议我们，将循环上的增益相乘并检查乘积是否小于1。 让我们选择表格中非对角线上的两个条目。它们表明，更长的新队列会产生更多重复项（$7/12$，$f$ 对下一 $d$ 的影响），而更多重复项会饿死新服务（$1/6$，$d$ 对下一 $f$ 的影响）。由于这涉及两个组件的交互，我们称之为**耦合**。将它们相乘，我们得到 $\\frac\{7\}\{12\} \cdot \\frac\{1\}\{6\} = \\frac\{7\}\{72\} \approx 0\.1$。这意味着，一个绕循环一圈的扰动返回其大小的十分之一。这表明系统是稳定的，并且有十倍的余量。但这是错误的，因为它只读取了表格中四个数字中的两个。 对角线上的两个数字，$11/12$ 和 $5/6$，描述了硬币的另一面：另一个队列不起作用时，每个队列有多少仍然存在于下一轮。回想一下，这两个数字都只来自服务器。我们称之为**记忆**。小增益定理只读取耦合项而忽略了记忆。 当我们把记忆考虑进去时，真实的每轮乘数变为 $1\.19$，大于1，因此几乎任何扰动都会增长而不是衰减。 我们通过标准的线性稳定性分析得到那个数字。我们寻找一个扰动 $\(x,y\)$，使得表格仅仅将其缩放某个因子 $r$。如果顶行是 $a,c$，底行是 $b,d$，那么 $ax\+cy=rx$ 且 $bx\+dy=ry$。当我们将每个方程解出 $y/x$，令它们相等，我们就得到了表格的特征多项式：$$r^2 \- \(a\+d\)\,r \+ \(ad \- bc\) = 0$$ 一个二次方程的两个根之和等于中间系数的相反数，乘积等于常数项。所以我们的两个因子（特征值）之和为 $a\+d$（迹），乘积为 $ad\-bc$（行列式）。 迹只来自对角线：$11/12 \+ 5/6 = 1\.75$。耦合项作为减法出现在行列式中：$0\.76 \- 0\.10 = 0\.67$。 如果我们去掉耦合项，行列式回到 $0\.76$，迹保持不变，得到 $0\.92$ 和 $0\.83$，都小于1。如果我们恢复耦合，行列式降至 $0\.67$，这将相同的和分裂为 $1\.19$ 和 $0\.56$，其中一个因子大于1，预示着麻烦。 这个算术也解释了两种已知的修复方法。重试预算使 $7/12$ 条目归零；优先处理新服务使 $1/6$ 条目归零。无论哪种方式，行列式中都没有减法，因子回落到 $0\.92$ 和 $0\.83$。每个队列每轮仍然传递超过80%的自身，但没有耦合来“喂养”这种传递，积压会以每轮8%的速度排空，而不是增长19%。 限制队列上限是同一招的另一种形式。对新队列设置上限 $M$ 意味着重试器永远不会发出超过 $\(M\-6\)/T$ 次重试，这是对 $7/12$ 耦合项的硬性上限。这是一种重试预算的形式。只有当上限低于余量时，积压才会排空：在 $M=7$ 时，上限允许零次重试，任何起点都会排空；而在 $M=8$ 时，它允许一次重试，空间中开始出现其他吸引子。进行模拟扫描表明，在 $M>8$ 时，上限限制了发散，但没有阻止故障。队列不是无限增长，而是爬升到上限并停在那里。在 $M=40$ 时，系统停留在 $\(39,38\)$：每轮服务的三个单位中，一个做有用工作，两个用于已经在进行中的请求的重复。这正是亚稳态的定义。 ## 结论 参数化假设-保证论文给了我一种更好的方法，将组件的承诺编写为按环境恶劣程度索引的一组契约族。但它没有给我实用系统的组合配方。由于论文的模型是无记忆的并且使用单一标量，它不适用于我们的例子。我通过写出两个队列如何共同演化来获得四个斜率，这意味着在那一步放弃了组合。然而，值得注意的是，表格中的每一项都来自单个组件，并且 $7/12$ 只是重试器的 $1/2$ 加上服务器的 $1/12$。因此，将来可能有一种方法可以在这里推导出组合方法。