无 Leader 共识的时间模型：逻辑时钟、依赖图与 Avalanche 采样收敛

摘要：无 Leader 不是没有排序者，而是把排序成本摊到冲突图里

无 Leader 共识（Leaderless Consensus）解决的是 Leader 型协议的单点瓶颈：Raft 的 leader、PBFT 的 primary、共享测序器的核心节点，都可能成为吞吐上限和定向 DoS 目标。但无 Leader 并不等于“交易天然并行且免费排序”。EPaxos 通过依赖图（Dependency Graph）让任意副本都能发起命令，低冲突时走 fast path；Avalanche/Snow 系列通过随机二次采样和亚稳态收敛，让节点在没有全局 leader 的情况下获得概率安全。两者共同的问题是：高冲突交易会把并发提案重新压回协调路径，环路检测、依赖合并、采样参数和物理时钟漂移都会决定最终延迟。

本文把单调时钟（Monotonic Clock）、逻辑时钟（Logical Clock）、向量时钟（Vector Clock）和混合逻辑时钟（Hybrid Logical Clock / HLC）放进同一个模型，分析无 Leader 协议怎样判断“谁先影响谁”。对 AllSwap 这类跨链路由系统，关键问题不是某条链是否宣称高 TPS，而是高冲突订单、Solver 并发报价和跨链退款能否在没有中心 leader 的情况下保留可验证顺序。

问题边界：本文讨论的是共识时间，不是服务器时间同步教程

系统角色包括：副本节点、客户端、验证者、跨链路由器、Solver、Market Maker、桥验证器和用户。攻击者可以制造高冲突交易、延迟局部消息、向某些节点展示偏置样本、让物理时钟漂移、诱导并发命令形成环；本文不假设攻击者能伪造签名、控制所有随机采样对象、突破客户端代码或直接修改已提交状态。文章是防御性协议分析，不提供攻击真实网络的操作流程。

Leader 型协议把排序集中到一个角色。Raft 通过 leader 复制日志，PBFT 通过 primary 提议请求序号；好处是状态机容易理解，坏处是 leader 会成为延迟中心。无 Leader 协议把提案权开放给所有副本，目标是让离客户端近的副本直接发起命令，减少广域网往返和单点拥塞。但排序没有消失，只是从 leader 的线性日志转移到依赖图、冲突集合、随机采样和恢复协议中。

本文不把 EPaxos 和 Avalanche 写成同一种协议。EPaxos 面向确定性状态机复制，强调冲突命令的依赖关系和 fast/slow path；Avalanche/Snow 面向概率 BFT，强调随机采样带来的偏好放大和亚稳态决策。它们放在一起讨论，是因为两者都试图绕开固定 leader，同时都必须回答同一个问题：在并发事件没有自然全序时，协议如何构造一个足够安全、足够快、足够可审计的执行顺序。

时钟模型：物理先后不等于因果先后

Lamport 的 happened-before 关系给出一个基础结论：分布式系统中不存在免费全局时间。如果事件 `a` 发生在同一进程中早于事件 `b`，或 `a` 的消息被 `b` 接收，那么 `a` 可以因果影响 `b`。逻辑时钟只要求因果关系对应到单调递增的数值；它不保证数值小的事件一定在真实物理世界先发生。向量时钟进一步记录每个进程的计数，可以判断两个事件是否并发。

对无 Leader 共识，这个区别直接影响排序。若两笔交易修改完全不同的账户或流动性槽，它们可以并发执行；若它们争用同一个池、同一个 nonce、同一个跨链退款凭证，它们必须被排序。物理时钟只能给出“节点本地看到的先后”，逻辑时钟才能表达消息传播后的因果边。HLC 把物理时间和逻辑计数结合起来，工程上更适合日志、快照和跨分区追踪，但它仍不能把真正并发的冲突交易自动变成无冲突。

一个简单模型是：

```text tx_i = (read_set_i, write_set_i, clock_i, origin_i) conflict(i, j) = write_set_i intersects read_set_j or write_set_j intersects read_set_i causal(i, j) = clock_i happened before clock_j through messages order_needed(i, j) = conflict(i, j) or causal(i, j) ```

若 `order_needed` 为假，协议可以并行提交；若为真，协议必须产生稳定顺序。无 Leader 协议的扩展性来自前一种情况，延迟灾难来自后一种情况。在跨链交换中，热点 USDT 池、同一 Market Maker 库存、同一源链付款凭证和同一目标链释放队列都会显著提高冲突率。

EPaxos：依赖图如何替代 Leader 日志

EPaxos 的核心思想是，每个副本都可以作为某个命令的 command leader。它不是把所有命令塞进一个 leader 日志，而是为每个命令收集冲突依赖和序列号。低冲突时，command leader 可以从 fast quorum 获得一致依赖集并快速提交；如果副本报告的依赖不一致，协议转入 slow path，用更传统的 Paxos 式接受阶段合并依赖并恢复一致性。

执行层看到的不是单条日志，而是一张有向图。顶点是命令，边表示“执行此命令前必须先执行另一个命令”。客户端命令提交后，副本把顶点加入依赖图；执行器对强连通分量做确定性排序，保证所有副本在遇到环时使用相同 tie-breaker。这个设计允许不冲突命令并行前进，但把冲突命令的成本显式转移到图维护和恢复逻辑中。

伪代码可以写成：

```text propose(cmd): deps = conflicts_seen_locally(cmd) seq = 1 + max(sequence(dep) for dep in deps) replies = preaccept(cmd, deps, seq) if all fast_quorum replies agree on deps and seq: commit(cmd, deps, seq) else: merged = union(replies.deps) accept_and_commit(cmd, merged, adjusted_seq) ```

高冲突场景下，问题集中在 `union(replies.deps)`。如果多个副本同时观察到不同冲突边，依赖图会变厚，强连通分量会变大，原本可以并行执行的命令被同一个环锁住。EPaxos Revisited 也指出，依赖图最终确定后仍要遍历执行顺序；在冲突负载和恢复场景中，执行延迟会抵消 fast path 的提交优势。

Fast Path 向 Slow Path 退化的数学阈值

设 `p` 为一笔命令与并发命令发生冲突的概率，`m` 为同一时间窗口内并发提案数量。粗略估算，某命令在窗口内没有冲突的概率接近：

```text P_fast ~= (1 - p)^(m - 1) ```

当 `p` 很小、`m` 适中时，fast path 成立，系统接近“离客户端最近副本直接提交”。当热点池或同一账户把 `p` 推高时，`P_fast` 会指数下降。更糟的是，冲突不是均匀分布。跨链流动性路由常有长尾：大量普通订单互不冲突，少数高价值资产池、稳定币路径和热门链出口形成瞬时热点。平均冲突率低并不能保证尾部订单快。

依赖图的成本也不是线性的。若冲突图是稀疏 DAG，拓扑排序和执行都轻；若冲突边形成大强连通分量，所有相关命令必须进入同一个确定性排序域。环路检测可以用 Tarjan 或 Kosaraju 这类强连通分量算法，复杂度是 `O(V + E)`，但在高频共识路径中，`E` 的增长速度比 `V` 更危险。因为每一条边都来自一次状态读写冲突、消息观察或恢复合并。

工程上，EPaxos 类协议需要维护：

- `conflict_index`：从状态 key 到最近命令实例的索引。 - `dependency_graph`：命令顶点和依赖边。 - `recovery_log`：未提交、部分提交和需要 slow path 的命令。 - `scc_scheduler`：对强连通分量做确定性执行。 - `clock_hint`：用逻辑时钟或 HLC 辅助调试和重放，但不能替代冲突证明。

这些结构会消耗内存和 CPU，且与存储层紧密耦合。如果应用层不能准确声明读写集，协议只能保守地把更多命令视为冲突，fast path 命中率会下降。

Avalanche：亚稳态采样不是免费的随机性

Avalanche/Snow 系列的路径完全不同。节点不是收集全局 quorum，而是反复随机抽样 `k` 个节点。如果样本中至少 `alpha` 个节点偏好同一个值，本节点就更新偏好并增加连续成功计数；当某个偏好连续满足条件达到 `beta` 次，节点把该值视为接受。随机采样会制造正反馈：一旦某个偏好略占优势，后续样本更可能观察到它，网络会向该偏好收敛。

简化状态机：

```text preference = initial_value confidence = 0 while confidence < beta: sample = query_random_validators(k) majority = count_preferences(sample) if majority[preference] >= alpha: confidence += 1 elif exists value v with majority[v] >= alpha: preference = v confidence = 1 else: confidence = 0 accept(preference) ```

这里的安全不是绝对 finality，而是参数化概率安全。`k` 越大、`alpha` 越高、`beta` 越高，错误接受概率越低，但消息轮数和延迟上升。官方 Snowman 文档也把 `alpha` 和 `beta` 作为关键参数描述。2022 和 2024 年的 Avalanche 分析论文进一步指出，随机采样、对手影响和 liveness/safety 之间存在复杂交互，不能只看白皮书里的直观正反馈。

对交易图来说，Avalanche 的优势在于不要求每个节点处理全网线性消息；缺点是冲突集合和样本偏置会影响收敛。如果两个冲突交易在不同网络区域同时获得局部偏好，采样过程需要足够多轮才能打破对称。若对手能影响样本可见性，系统可能在活性上出现拖延。概率共识很适合把大量非冲突交易并行接受，但对高价值跨链释放，应用层仍要根据金额和风险设置更保守的接受阈值。

单调时钟漂移会怎样破坏鲁棒性

无 Leader 协议通常会说自己不依赖同步物理时钟，这在安全证明层面常常成立；但工程系统仍大量使用本地单调时钟：超时、重试、缓存过期、采样窗口、请求去重、日志切片和指标告警都依赖它。单调时钟不会倒退，但不同节点的速率可以漂移，虚拟机暂停、NTP 校正、系统休眠和容器迁移都可能让“本地 500ms”在不同节点上含义不同。

EPaxos 中，超时过短会把可 fast path 的命令提前推入恢复；超时过长会让真实故障阻塞依赖图。Avalanche 中，采样间隔和查询超时影响一个节点观察到的偏好分布。若某一区域节点因为时钟或调度偏差更快重试，它们可能在样本图中产生过度代表。协议安全可以不依赖物理时间，但实现活性一定被物理时间影响。

因此，工程上需要把时钟分成三类使用：逻辑时钟用于因果和重放；HLC 用于跨节点日志、快照和审计；单调时钟只用于本地 deadline，不参与最终排序证明。任何把本地 wall clock 直接写进共识排序的设计，都必须证明时钟不确定性边界，否则会把网络延迟误判为经济顺序。

失败模式与防御边界

第一种失败模式是热点冲突放大。大量交易争用同一池、同一 nonce、同一库存账户或同一退款凭证时，EPaxos 依赖图会形成大强连通分量，fast path 命中率下降。防御是应用层提前声明读写集、对热点 key 做队列化、将大额订单与小额订单分层，并记录冲突边作为可审计指标。

第二种失败模式是依赖图恢复风暴。副本崩溃或网络分区后，未决命令需要恢复依赖。如果恢复过程不断发现新冲突，slow path 会反复合并依赖，执行器迟迟无法切开强连通分量。防御是限制单个实例的恢复 fanout、为过期命令设置 abort 语义、对跨链订单使用幂等状态机。

第三种失败模式是随机采样偏置。Avalanche 类协议依赖样本代表性；若对手通过网络拓扑、peer 选择或延迟操控让节点反复采到偏置集合，收敛可能变慢或偏向错误值。防御是改进 peer sampling、记录样本多样性、限制同一自治域或同一运营商权重，并按金额提高确认参数。

第四种失败模式是本地时钟误用。若系统把 wall clock 先后直接当作交易先后，跨区域订单可能因时钟漂移被错误排序。防御是只把时钟作为 hint，最终顺序仍由签名消息、依赖边和共识证据决定。

第五种失败模式是跨链释放过早。无 Leader 链的本地接受状态可能还没有被桥、轻客户端或目标链验证器观察到。防御是把 `local_accepted`、`network_finalized`、`bridge_observed`、`target_released` 拆成不同状态，而不是用一个“confirmed”字段概括全部。

AllSwap 相关性：路由需要的是冲突可解释性

AllSwap 的跨链交换不是在抽象吞吐数字上运行，而是在真实冲突图上运行。两个订单可能表面上都是 USDT 跨链，但它们是否冲突取决于源链支付凭证、目标链库存、Market Maker 额度、桥通道、退款地址和目标链执行队列。如果底层链或桥采用无 Leader 共识，路由器不能只读取“已接受”，还要理解接受背后的冲突域。

一个实用的路由评分可以包含：

- `conflict_domain`：订单会争用哪个池、库存账户或桥通道。 - `consensus_mode`：来源是 leader 日志、依赖图 fast path、slow path，还是概率采样接受。 - `clock_source`：时间戳来自逻辑时钟、HLC、桥观测时间还是本地 wall clock。 - `sample_confidence`：概率共识的采样参数和连续成功轮数。 - `refund_ordering`：退款凭证是否已经进入稳定顺序。

这类字段不会暴露给普通用户，但会决定系统如何报价、何时释放、何时退款。对小额订单，概率接受和快速路径可能足够；对高价值订单，系统应等待更强证据，或者要求 Solver 承担更高保证金。无 Leader 共识的价值不是“永远更快”，而是在低冲突条件下把中心瓶颈拆掉，同时在高冲突条件下诚实地暴露退化路径。

工程实现层：把冲突域做成一等对象

真正可用的无 Leader 路由系统，不能等到底层共识返回慢路径后才发现冲突。更稳妥的做法是在订单进入系统时就构造 `conflict_domain_id`。它可以由源链、源交易哈希、目标资产、目标链、Market Maker 库存账户、桥通道和退款凭证共同哈希得到。这样，路由器可以在报价阶段预估冲突，而不是在执行阶段被依赖图放大。

状态机可以拆成五个队列：

```text quote_queue -> reserve_queue -> source_observed_queue -> release_queue -> refund_queue ```

`quote_queue` 只处理价格和路径；`reserve_queue` 锁定库存额度；`source_observed_queue` 等待源链付款和共识证据；`release_queue` 处理目标链释放；`refund_queue` 处理失败回滚。每个队列都应携带同一个 `conflict_domain_id` 和 `causal_token`。如果两个订单的冲突域相同，系统可以主动串行化，而不是把它们同时推给底层无 Leader 共识再被动恢复。

这不是降低并发，而是把并发用在真正独立的订单上。稳定币小额兑换、不同目标链出口和不同库存账户可以并行；同一高价值库存槽、同一桥通道和同一退款凭证应当提前排队。若底层协议是 EPaxos 类依赖图，这能减少强连通分量；若底层协议是 Avalanche 类概率采样，这能减少冲突集合规模。路由层越早声明冲突域，底层共识越少承担应用语义猜测。

审计也依赖这个设计。订单失败时，日志应能回答：它是因为价格过期、源链未确认、依赖图进入 slow path、采样置信不足、桥未观测，还是退款顺序未稳定。若所有异常都写成“network delay”，用户和运营方都无法区分市场风险、共识风险和实现风险。

未解决问题

第一，应用层读写集声明仍不可靠。若合约或跨链路由不能提前给出准确冲突域，无 Leader 协议只能保守排序。

第二，概率最终性的产品语义还不统一。不同链对 `accepted`、`finalized`、`confidence` 的定义不同，桥和路由器缺少统一接口。

第三，依赖图和 MEV 的关系没有完全解决。谁能影响冲突边、谁能选择 tie-breaker，谁就可能影响跨链套利和清算顺序。

第四，HLC 和物理时钟不确定性很难在开放 P2P 网络里标准化。数据中心系统可以依赖更强时钟基础设施，公链节点不具备同样条件。

第五，随机采样协议在真实网络拓扑下的样本独立性仍需持续验证。云厂商集中、地理分布和 peer 发现策略都会改变理论参数的含义。

参考资料

[1] Leslie Lamport, Time, Clocks, and the Ordering of Events in a Distributed System, https://lamport.azurewebsites.net/pubs/time-clocks.pdf

[2] Friedemann Mattern, Virtual Time and Global States of Distributed Systems, https://homes.cs.washington.edu/~arvind/cs425/doc/mattern89virtual.pdf

[3] Kulkarni et al., Logical Physical Clocks and Consistent Snapshots, https://cse.buffalo.edu/tech-reports/2014-04.pdf

[4] Corbett et al., Spanner: Google's Globally-Distributed Database, https://research.google.com/archive/spanner-osdi2012.pdf

[5] Ongaro and Ousterhout, In Search of an Understandable Consensus Algorithm, https://raft.github.io/raft.pdf

[6] Castro and Liskov, Practical Byzantine Fault Tolerance, https://css.csail.mit.edu/6.824/2014/papers/castro-practicalbft.pdf

[7] Moraru, Andersen, Kaminsky, There Is More Consensus in Egalitarian Parliaments, https://www.cs.princeton.edu/courses/archive/fall19/cos418/papers/epaxos.pdf

[8] Tollman, Park, Ousterhout, EPaxos Revisited, https://www.usenix.org/conference/nsdi21/presentation/tollman

[9] Yin et al., Scalable and Probabilistic Leaderless BFT Consensus through Metastability, https://arxiv.org/abs/1906.08936

[10] Avalanche Builder Hub, Snowman Consensus, https://build.avax.network/docs/primary-network/avalanche-consensus

[11] Amores-Sesar, Cachin, Schneider, An Analysis of Avalanche Consensus, https://arxiv.org/abs/2401.02811

[12] Amores-Sesar, Cachin, Tedeschi, When Is Spring Coming? A Security Analysis of Avalanche Consensus, https://arxiv.org/abs/2210.03423