無 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