⚡ electrical engineering

Partial Resilient Leader-Follower Consensus in Time-Varying Graphs

该论文针对时变图中网络鲁棒性不足导致传统算法失效的问题，提出了“部分领导者 - 跟随者共识”概念及一种名为 BP-MSR 的新型分布式算法，证明了即使在标准条件不满足的情况下，也能确保部分非对抗性跟随者成功跟踪领导者状态。

原作者： Haejoon Lee, Dimitra Panagou

发布于 2026-03-17

📖 1 分钟阅读☕ 轻松阅读

原作者： Haejoon Lee, Dimitra Panagou

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文讲述了一个关于**“在混乱中如何保持团结”**的故事，特别是当团队里混进了“捣乱者”时，大家还能不能达成共识。

我们可以把这篇论文的核心思想想象成**“在一个充满谣言的村庄里，如何确保一部分村民能听到村长的真实指令”**。

1. 背景：当“捣乱者”混入团队

想象一个由许多村民（智能体）组成的村庄，他们需要通过互相交流来达成某种共识（比如决定明天是晴天还是雨天，或者统一行动方向）。

正常村民：大家互相传递真实信息。
捣乱者（敌手）：有些村民是坏人，他们故意散布假消息（比如明明要下雨，他们却喊“大晴天”），试图把整个村庄搞乱。

以前的研究（传统算法）认为：只要村庄的整体结构足够紧密（比如每个人周围都有很多邻居，且邻居之间联系紧密），就能保证所有正常村民都能识破谎言，最终达成一致。这就像要求整个村庄必须是一个“铁桶阵”，没有任何漏洞。

但是，现实往往很骨感：
在能量受限或通信不稳定的情况下（比如无人机群、传感器网络），很难保证整个网络永远紧密。一旦网络结构变得松散，传统的“铁桶阵”策略就会失效，整个系统可能彻底崩溃，没人能听到村长的声音。

2. 核心创新：不求“全员”，但求“部分”

这篇论文提出了一个更务实的想法：既然无法保证所有人都听清，那我们就先保证“一部分人”能听清，并且让他们保持清醒。

这就好比：

在暴风雨中，虽然无法让整艘船都不进水，但我们可以确保船舱里的几个关键救生艇是干燥的，并且能准确接收到救援信号。

作者引入了**“部分弹性领导 - 跟随共识”**的概念：

目标：不要求所有正常村民都达成共识，只要求一部分聪明的、连接良好的村民（我们称之为“收敛者”）能成功跟随村长。
结果：即使剩下的村民因为网络太乱而暂时“晕头转向”，只要这部分人稳住了，整个系统就没有完全失败。

3. 解决方案：BP-MSR 算法（“bootstrap 渗透 + 过滤”）

作者设计了一个聪明的新算法，叫 BP-MSR。我们可以把它想象成村民们的**“自我体检”和“过滤机制”**。

第一步：自我体检（Bootstrap Percolation）

在每次大家准备交流之前，每个村民先做一个“自我检查”：

规则：如果你发现你周围有足够多的“活跃邻居”（比如至少 3 个邻居都确认收到了村长的信号），你就标记自己为**“活跃状态”**。
比喻：就像在人群中，如果你发现周围至少有 3 个朋友都确信“村长在说话”，那你就可以放心地认为“村长确实在说话”。如果周围只有 1 个朋友确认，或者全是捣乱者，那你就不敢乱动，保持**“静止状态”**。

第二步：选择性交流（MSR 过滤）

如果你处于“活跃状态”：你才敢参与讨论。在讨论时，你会把邻居传来的消息里最极端的几个（比如喊“太阳是绿色的”或“世界末日了”这种离谱的）直接扔掉，只取中间最合理的部分来更新自己的判断。
如果你处于“静止状态”：你闭嘴，保持现状，不传播任何可能错误的信息。

这个机制的妙处在于：
它像一道智能闸门。只有那些连接足够好、能识别出“安全区域”的村民才会参与更新。那些连接不好、容易受坏人影响的村民，会自动“隐身”，防止他们把错误信息传播给更多人。

4. 为什么这很厉害？

传统方法：如果网络不够紧密，大家要么全对，要么全错（系统崩溃）。
新方法：即使网络很乱，只要有一部分村民（比如 6 号、7 号、8 号）运气好，他们所在的局部小圈子足够紧密，他们就能自动识别出自己是安全的，然后只让他们自己达成共识。
安全性：那些没能达成共识的村民，虽然没跟上队，但他们的状态也被限制在正常范围内，不会跑得太离谱。

5. 总结与比喻

想象你在一个嘈杂的派对上（网络），有人在大声散布假新闻（敌手）。

旧方法：要求整个派对必须绝对安静，否则没人能听清谁在说话。
新方法（BP-MSR）：
1. 每个人先看看周围：如果周围有足够多的人都在认真听，我就加入讨论。
2. 如果周围太乱，我就闭嘴，不跟着瞎起哄。
3. 加入讨论的人，会自动过滤掉那些喊得最大声的怪话。

最终结果：虽然派对上还有人在乱喊，但一小群清醒的人（收敛集合）成功听到了主持人的指令，并达成了共识。这就足够了！

论文的贡献

承认现实：不再强求完美的网络环境，接受“部分人成功”也是成功。
新算法：提出了 BP-MSR，让每个节点能自己判断“我现在安全吗？”，安全了就动，不安全就停。
理论证明：证明了只要这部分人“经常”处于安全网络中，他们最终一定能跟上领导者的步伐。

简单来说，这就是一套**“在混乱中，让清醒者自动抱团，让糊涂者自动闭嘴”**的生存智慧。

论文技术总结：时变图下的部分弹性领导者 - 跟随者共识

1. 研究背景与问题定义

背景：
在多智能体系统中，共识（Consensus）是指多个智能体达成一致状态的过程。然而，标准共识协议在面对恶意攻击者（Adversarial Agents，如拜占庭节点）时非常脆弱，攻击者通过发送虚假信息可能导致系统性能下降甚至崩溃。现有的弹性共识（Resilient Consensus）研究通常依赖于网络拓扑的**强鲁棒性（Strong Robustness）**条件（如 $r$ -robustness 或 $(r, s)$ -robustness），以确保所有正常智能体都能达成共识。

核心问题：
现有的弹性领导者 - 跟随者共识（Resilient Leader-Follower Consensus）算法通常要求整个网络在任意时刻都满足严格的鲁棒性条件。然而，在实际应用中（如受能量或通信限制的系统），很难保证网络始终满足这些条件。当网络不满足全局鲁棒性条件时，现有算法往往完全失效，且关于此时系统的行为（即哪些智能体仍能达成共识，哪些不能）缺乏理论分析。

本文目标：
研究在任意时变图序列下，当网络不满足全局鲁棒性条件时，多智能体系统的行为。作者引入了**部分弹性领导者 - 跟随者共识（Partial Resilient Leader-Follower Consensus）**的概念，旨在确定在鲁棒性不足的情况下，哪些正常跟随者（Followers）能够成功跟踪领导者的参考状态，并设计相应的算法。

2. 方法论：BP-MSR 算法

为了解决上述问题，作者提出了一种新颖的分布式算法：Bootstrap Percolation and Mean Subsequence Reduced (BP-MSR)。

2.1 核心思想

BP-MSR 算法的核心在于局部验证与选择性参与：

引导渗透（Bootstrap Percolation, BP）： 在每个时间步 $t$ ，所有智能体首先同步运行一个引导渗透过程。该过程基于阈值 $r = 2F + 1$ （其中 $F$ 是局部攻击者数量的上限），用于检测每个跟随者是否属于一个相对于领导者集合（及攻击者集合）是强 $r$ -鲁棒的子图。
状态激活： 如果一个跟随者 $i$ 在 BP 过程中被激活（即 $q_i[t]=1$ ），意味着它当前处于一个足够鲁棒的子图中，能够抵抗 $F$ 个攻击者的干扰。
选择性共识更新：
- 若 $q_i[t] = 1$ ：该跟随者参与共识更新，使用改进的 W-MSR 算法（丢弃邻居中最大的 $F$ 个和最小的 $F$ 个值），以过滤攻击者的虚假信息。
- 若 $q_i[t] = 0$ ：该跟随者保持静止（不更新状态），避免将可能受污染的状态传播给网络。

2.2 算法流程

初始化： 领导者状态为 1，跟随者为 0。
BP 迭代： 每个智能体根据邻居的激活状态更新自己的激活状态（公式 1），迭代 $f$ 次。
决策与更新：
- 领导者：始终更新并广播参考状态。
- 跟随者：如果激活状态为 1，则执行 W-MSR 更新；否则保持当前状态不变。

3. 主要贡献

提出部分共识概念与 BP-MSR 算法：
首次定义了“部分弹性领导者 - 跟随者共识”，即在网络整体鲁棒性不足时，保证子集正常跟随者达成共识。提出了 BP-MSR 算法，使智能体能根据局部连通性动态决定是否参与更新。
建立个体收敛的充分条件：
不同于以往依赖全局网络鲁棒性的工作，本文建立了针对单个跟随者的收敛充分条件。
- 定理 1 证明：如果一个正常跟随者无限次地处于强 $(2F+1)$ -鲁棒子图中（即 $q_i[t]=1$ 无限次发生），那么它将收敛到领导者的参考状态。
- 即使网络整体不满足鲁棒性，只要部分跟随者满足上述条件，它们就能达成共识。
收敛集（Convergent Set）的界定：
由于攻击者可以操纵激活状态的传播，精确确定收敛集 $F_C$ 是困难的。作者提出了命题 1，通过构造两个极端场景（攻击者全部发送 0 或全部发送 1），给出了收敛集 $F_C$ 的子集下界和超集上界：
- 下界 ( $F_1^C$ )： 仅由正常智能体诱导的强鲁棒子图中的跟随者。
- 上界 ( $F_2^C$ )： 由正常智能体和攻击者（视为领导者）共同诱导的强鲁棒子图中的跟随者。
  这为预测哪些节点能收敛提供了理论框架。
安全性保证：
即使某些跟随者无法收敛（非收敛集），BP-MSR 算法也能保证它们的状态始终保持在正常智能体状态的凸包（Convex Hull）内，防止状态发散。

4. 仿真结果

作者通过仿真实验验证了理论结果：

场景设置： 使用三个时变图（ $G_1, G_2, G_3$ ）组成的序列，其中包含 1 个局部攻击者。这些图单独或组合均不满足传统算法（如 W-MSR 或 SW-MSR）所需的全局强鲁棒性条件。
对比结果：
- W-MSR 和 SW-MSR： 由于网络不满足全局鲁棒性，所有跟随者均无法跟踪领导者，共识失败。
- BP-MSR： 成功实现了部分共识。跟随者 $\{6, 7, 8\}$ 能够收敛到领导者状态，因为它们无限次地处于强鲁棒子图中。而跟随者 $\{4, 5, 9\}$ 虽然不收敛，但其状态被限制在正常智能体的凸包内，未发散。
收敛集验证： 仿真展示了当攻击者分别发送全 0 和全 1 的激活状态时，收敛集的大小分别达到理论下界和上界，验证了命题 1 的有效性。

5. 意义与总结

理论突破： 打破了弹性共识必须依赖“全局强鲁棒性”的传统假设。在现实世界中网络拓扑经常变化且难以维持高鲁棒性的场景下，该理论提供了更实用的分析框架。
实际应用价值： 为资源受限或通信不稳定的多智能体系统（如无人机编队、传感器网络）提供了新的容错策略。系统不需要所有节点都完美工作，而是允许“部分节点”在恶劣条件下依然保持功能，提高了系统的整体生存能力。
方法论创新： 将引导渗透（Bootstrap Percolation）机制引入共识协议，利用其作为“连通性过滤器”，实现了分布式、自适应的弹性控制。

总结： 本文通过 BP-MSR 算法，证明了即使在网络整体鲁棒性不足的情况下，只要部分跟随者能够周期性地连接到足够鲁棒的子图，它们就能实现弹性共识。这一成果极大地扩展了弹性共识理论的适用范围，为复杂动态环境下的多智能体系统控制提供了新的理论支撑。