無 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