💻 computer science

Hermes: Low Tail-Latency Via Prefix Consensus

Hermes 是一个针对 $n=5f+1$ 个进程的两轮轮转领导者 BFT 协议，它通过利用前缀共识从任何 $n-f$ 个投票中确定最重共同前缀，从而利用前缀共识来消除由缓慢或崩溃的领导者导致的尾部延迟停顿，进而确保即使在视图过期时也能保证进度。

原作者： Alejandro Ranchal-Pedrosa, Dakai Kang, Neil Giridharan, Dahlia Malkhi, Mohammad Sadoghi, Ben Marsh

发布于 2026-07-29

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Alejandro Ranchal-Pedrosa, Dakai Kang, Neil Giridharan, Dahlia Malkhi, Mohammad Sadoghi, Ben Marsh

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

想象一下，一群朋友正试图决定看哪部电影，但他们分散在世界各地，有些人网络信号很差，还有几个调皮的朋友试图通过发送虚假链接或假装离线来破坏决策。这就是**拜占庭容错（Byzantine Fault Tolerant, BFT）**的世界。在计算机科学中，这是指一个网络中的计算机如何达成对单一事实的共识——比如区块链中交易的顺序——而无需信任任何单一的中央管理者。其目标是即使在某些计算机崩溃或表现出恶意行为的情况下，也能快速达成一致（低延迟）。

多年来，这些系统一直依赖于一个“领导者”来提议下一步行动。如果领导者快速且诚实，大家就能迅速达成一致。但如果领导者变慢或崩溃，整个小组就必须等待计时器到期，放弃该领导者，并选出新的一位。这产生了一个痛苦的权衡：设置较长的计时器，你会为失效的领导者等待太久；设置较短的计时器，你又会浪费时间去放弃那些只是稍微变慢了的领导者。这种“超时困境”（timeout dilemma）是拖慢系统尾部性能的瓶颈。

这篇论文介绍了一种名为 Hermes 的新协议，旨在解决这个特定的难题。与其在领导者变慢时直接放弃，Hermes 让小组能够完成他们能够达成一致的工作，即使领导者失败了。它将一次浪费的超时转化为了一个富有成效的决策，确保无论发生什么，系统都能持续推进，而不会丢失已经取得的进展。

问题所在：“超时陷阱”

想象一场接力赛，队长（领导者）应该将接力棒交给下一位跑者。如果队长跑得快，比赛就会进行得很顺利。但如果队长绊倒或掉落了接力棒，整个团队就必须停下来，等待裁判的哨声（超时），然后才能挑选新队长并重新开始。

在传统系统中，这个哨声是一场赌博。如果裁判吹得太早，他们可能会叫停一位只是跑得稍慢但本可以完成比赛的队长。如果等得太久，团队就会在损坏的队长尝试恢复期间闲置很久。无论哪种情况，所花费的时间都是“无效时间”——没有进度产生，比赛也陷入停滞。这就是“尾部延迟”（tail latency）问题：最坏的情况拖累了整个系统的表现。

解决方案：Hermes 与“共同点”

Hermes 改变了游戏规则。它不再将缓慢的领导者视为完全的失败，而是将小组的部分共识视为一种胜利。

以下是它的运作方式，使用一个创意类比：想象团队正在尝试用积木搭建一座高塔。

旧的方式： 领导者放置一块积木。所有人等待。如果领导者停止了，团队等待超时，然后扔掉整座塔，并用新的领导者重新开始搭建。
Hermes 的方式： 领导者开始放置积木，但每个人同时也开始同时放置自己的积木。如果领导者很快，团队会完美地按照领导者的方案搭建塔；如果领导者卡住了，团队不会扔掉这座塔。相反，他们会查看所有人放置的所有积木，找到所有人都对积木顺序达成一致的最长部分，并将该部分宣布为“已完成”。

这是核心创新：前缀共识（Prefix Consensus）。在过去，如果两个人对稍微不同的塔进行了投票，他们的投票会被视为分歧并被丢弃。Hermes 则说：“等等，他们在塔的底部 90% 部分是一致的！让我们锁定那部分并继续前进。”

Hermes 如何运作：两轮舞步

Hermes 在“视图”（views，即轮次）中运行，每一轮都有一个指定的领导者。它使用了一个巧妙的两步舞步：

第一轮（提议）： 每个人都广播自己关于下一部分塔应该长什么样的想法。领导者的想法只是众多想法中的一个。
第二轮（投票）：
- 如果领导者很快： 每个人都看到了领导者的提议，表示同意，并为其投票。塔仅需两个消息延迟（2δ）即可增长完整的领导者区块。
- 如果领导者变慢或崩溃： 计时器到期。与其投票来“取消”这一轮，不如每个人都针对他们在收到的提议中能找到的最佳一致性进行投票。他们寻找“最重共同前缀”（Heaviest Common Prefix, HCP）——即所有人都能达成一致的最长序列，即使他们的提议在最后阶段出现了分歧。

这意味着，即使领导者失败了，小组也不会丢失该视图。他们完成共同部分的塔，并立即开始下一轮。原本作为死胡同的“超时”路径，现在能产生结果。

“前缀”与“跳过”的魔力

为了让这种方式在多条数据通道（类似于拥有许多车道的公路）中运作，Hermes 使用了一种特殊的编码，称为父相对增量切片（parent-relative delta tipcuts）。

这就像一本“选择你自己的冒险”类书籍，其中的每一页都引用了前一页。如果一条交通车道缺少了一辆车（一个区块），Hermes 不会说“错误”。它会明确地将该位置标记为“跳过”，并移动到下一辆车。这使得系统即使在处理缺失不同部分的提议时，也能进行比较。这就像是在比较两个故事：即使一个故事跳过了一个段落，而另一个故事包含了它，它们仍然可以对开头和结尾达成一致，系统也会锁定这种一致性。

结果：速度与安全

论文从数学上证明了 Hermes 是安全的（没有两个诚实的人会对最终确定的部分产生分歧）且是活跃的（系统总能持续推进）。

理想情况： 如果领导者诚实且快速，Hermes 与现有的最佳系统一样快，只需 2δ（两个消息延迟）即可完成最终确认。
糟糕情况： 如果领导者变慢或崩溃，Hermes 会以 2∆ + δ（其中 ∆ 是超时时间，δ 是网络延迟）的速度完成共同协议的确认。至关重要的是，这比以往等待完整视图切换（view change）的方式要快，因为它跳过了丢弃视图的“浪费”时间。

作者展示了通过使用纠删码（erasure coding）（一种将数据拆分为碎片以便在丢失部分数据时仍能重建的方法），即使在处理许多数据通道时，Hermes 也能保持较低的通信成本。

为什么这很重要

Hermes 通过让超时本身变得富有成效，解决了“超时困境”。它将失败的时刻转化为进步的时刻。与其问“领导者成功了吗？”并等待结果，Hermes 问的是“我们都达成了什么共识？”并向前推进。

对于一个好奇的青少年来说，可以把它想象成一个群聊，大家都在努力商定一个计划。如果通常负责提议计划的那个人卡住了，旧的方法是等待他们的回复或者开启一个新的聊天并更换领导者。Hermes 则像是说：“好吧，他们没回复，但看看我们发出的所有想法。我们对前三步都达成了一致。让我们锁定这些步骤，并开始规划第四步。”这是一种更聪明、更具韧性的方式，无论谁掉链子，都能让团队继续前进。

技术摘要：Hermes：通过前缀共识实现低尾部延迟

1. 问题陈述

基于领导者的拜占庭容错（BFT）协议通常仅在指定的领导者及时响应时才能完成交易定型。如果领导者崩溃或响应缓慢，则必须通过超时来终止当前视图（view），这会导致一个“浪费”的视图，即在该视图期间无法取得任何进展。这造成了超时配置中的一个根本性权衡：

保守超时： 容忍缓慢的领导者，但会将每一个崩溃的领导者转化为长时间的停顿。
激进超时： 快速跳过崩溃的领导者，但会使那些仅仅是响应缓慢（这在地理分布式系统中很常见）的领导者的视图失效。

在这两种情况下，过期的视图都是被浪费的，且请求必须等待视图切换以及下一轮领导者的往返通信后才能完成定型。这种权衡，而非“理想情况”下的性能，决定了系统的尾部延迟。此外，现代架构通常将数据分发（例如 DAG、基于通道的设计）与共识排序分离。在这种设置下，提案是流的前缀，由于网络抖动，诚实的提案在同一视图内往往仅在后缀部分存在差异。现有的协议将这些不匹配的投票视为分歧，未能利用它们所共享的共同前缀。

2. 方法论

Hermes 是一个针对 $n = 5f + 1$ 个进程设计的两轮轮询领导者协议，适用于部分同步环境。它引入了前缀共识（Prefix Consensus），其中投票携带由前缀关系（ $\preceq$ ）定义的有序值，且法定人数（quorum）要求的是可比性而非相等性。

核心机制

两轮结构：
1. 第一轮（提案）： 每个进程广播一个经过证明（justified）的提案。轮询领导者的提案是 $n$ 个提案之一。
2. 第二轮（投票）： 每个进程投出一张单票。
  - 如果领导者的提案被及时交付，进程会对该提案进行投票。
  - 如果超时（ $2\Delta$ ）发生且已收到 $n-f$ 个有效提案，进程将针对从可用集合中选出的**回退提案（fallback proposal）**进行投票。
- 至关重要的是，不存在作废（nullify）投票。
法定人数定义：
- M-公证（M-notarization）： 一组 $2f+1$ 个两两可比的投票。这允许视图推进到下一个视图。
- L-公证（L-notarization）： 一组 $n-f = 4f+1$ 个有效投票（这些投票不必完全相同）。该集合定型所有投票的最大公共前缀（Heaviest Common Prefix, HCP）。
处理超时：
Hermes 不通过废弃视图来处理缓慢的领导者，而是利用超时路径来定型 $n-f$ 个投票的 HCP。激进的超时现在仅以投票产生分歧的后缀为代价，而不是整个视图。HCP 在 $2\Delta + \delta$ 时定型。
值空间实例化：
该协议在抽象的前缀有序空间上进行实例化，并应用于两种特定场景：
1. 单通道（最终性组件）： 针对动态可用的链（如 Ethereum）。值是链顶（chain tips）；前缀关系是祖先关系。
2. 多通道（Autobahn 式）： 对并发的通道数据进行排序。这引入了三个特定挑战，并通过以下方式解决：
  - 确定性交织（Deterministic Interleaving）： 通道位置的全局顺序。
  - 相对于父节点的增量尖端切片（Parent-Relative Delta Tipcuts）： 一种紧凑的表示法，使用父标识符和显式跳过标记，以处理异构通道速度问题，而无需传输完整值。
  - 发送者索引的纠删码放大（Sender-Indexed Erasure-Coded Amplification）： 为了在不增加通信复杂度至 $O(n^3 \hat{m})$ 的情况下确保可用性，提案通过纠删码进行放大。证明（justifications）携带标识符，碎片按需重建。

3. 核心贡献

Hermes 协议： 一个针对 $n=5f+1$ $n = 5 f + 1$ 的两轮轮询领导者协议，没有作废路径。
- 理想情况： 在诚实领导者及时的条件下， $2\delta$ 完成定型。
- 异常情况： 在 $2\Delta + \delta$ 时定型任何 $n-f$ 个投票的 HCP。
- 安全性与活性： 在抽象的前缀值空间上得到了证明。
单通道实例化： 作为可用链（值为链顶）的最终性组件。
多通道实例化： 一个具有以下特征的 Autobahn 式通道设计：
- 确定性交织。
- 带有显式跳过认证的相对于父节点的增量尖端切片。
- 发送者索引的纠删码放大。
- 复杂度： 每视图的通信复杂度为 $O(n^2 \hat{m} + \lambda n^3)$ 比特，消息复杂度为 $O(n^2)$ （其中 $\hat{m}$ 是通道数量， $\lambda$ 是安全参数）。
实现与评估： 论文包含实现与评估（第 8 节），尽管提供的文本中具体的数值结果被标记为“添加结果”。

4. 结果与性能

延迟：
- 及时的领导者： 在 $2\delta$ 内完成定型。
- 缓慢/崩溃的领导者： 在 $2\Delta + \delta$ 内定型 HCP。相比于传统协议（在这些协议中，缓慢的领导者会导致完整的视图切换，并在随后的 $2\delta$ 轮次中总计耗时 $2\Delta + 3\delta$ 或更多），这是一个显著的改进。
通信：
- 在带有放大的多通道设置中，该协议避免了转发完整值所带来的四次方复杂度（ $O(n^3 \hat{m})$ ）。
- 理想情况下保持 $O(n^2)$ 消息。在发生故障时，由于放大流量，消息复杂度可能会上升到 $O(n^3)$ ，但比特复杂度仍受控制。
尾部延迟： 通过使超时路径具有生产力，Hermes 消除了“浪费视图”的惩罚。落在坏视图中的请求只需支付超时和 HCP 定型的代价，而不是等待完整的视图切换周期。

5. 重要意义

论文声称 Hermes 从根本上改变了响应性（视图切换的速度）与稳定性（多少次视图切换能产生进展）之间的权衡。

具有生产力的超时： 与以往设计中超时意味着视图失效不同，Hermes 确保即使是在失败的领导者视图中，也能定型数据流的一个有用前缀。
兼容现代架构： 它弥合了可用数据分发层（如 DAG 或基于通道的系统）与共识之间的鸿沟，允许最终性组件对已经传播但可能在分发层略有分歧的区块进行排序。
最优性： Hermes 在理想情况下实现了 $2\delta$ 的理论下界，同时解决了领导者 BFT 中长期存在的尾部延迟问题，且无需单独的恢复协议或竞速机制。

论文将 Hermes 定位为同类协议中唯一一个使失败领导者的视图本身也能完成定型的协议，这与 Minimmit（它会作废此类视图）和 Raptr（它在单个领导者的提案内使用前缀投票以保证可用性）形成了对比。