Multicast 如何實作：排序、可靠傳遞與 View Change

封包抵達，不代表應用程式現在就能使用它。理解 multicast ordering，第一步就是把 receive（網路收到） 和 deliver（交給應用程式） 分開：前者由網路延遲決定，後者由協定判斷。

前面的時鐘筆記 介紹了 happened-before。這篇接著把課程裡的實作規則逐步算完，再加入程序失效與成員變更。例子使用 crash failure 模型，不包含惡意程序；排序演算法先假設群組固定，membership change 留到後半段處理。

先拆成三個問題

這裡的 correct process，是指在這次 execution 中不會 crash 的程序。對 correct process 的保證，不等於要求已經停止的程序把工作做完。

FIFO 保留每個 sender 自己的順序。Causal order 也保留跨 sender 的因果依賴，因此在相同群組內包含 FIFO。Total order 要求接收者對訊息的相對交付順序取得一致；單獨使用時，不保證遵守送出順序或因果。Causal-total 則同時提供兩種保證。

例如，所有人都先看到回覆、再看到原文，順序雖然一致，卻違反因果。反過來，所有人都先看到原文，但兩則互不相關的回覆出現順序不同，仍可能符合 causal order，只是不符合 total order。

FIFO：缺哪一號，就先等哪一號

每個 sender 都有自己的遞增序號。Receiver i 保存 delivered[j]，代表已交給應用程式的最後一則 sender j 訊息。注意，這是 delivery counter，不是網路上看過的最大序號。

收到 (sender j, sequence s, payload)：
    若 s <= delivered[j]：丟棄重複訊息
    若 s > delivered[j] + 1：先放進 buffer
    若 s == delivered[j] + 1：
        deliver 這則訊息
        delivered[j] = s
        持續檢查 buffer 裡是否已有下一則

假設 P3 尚未 deliver 過 P1 的任何訊息：

flowchart LR
  A["網路收到第 2 則"] --> B["Buffer：等待第 1 則"]
  C["網路收到第 1 則"] --> D["Deliver 1"]
  D --> E["下一個期待序號變成 2"]
  B --> F["Deliver buffer 裡的 2"]
  E --> F

這套規則不比較 P1 和 P2 誰的訊息該先交付。它也不負責補回遺失的封包：如果第 1 則永遠不到，第 2 則就永遠卡在 buffer。重傳與失效處理，必須另外補上進展的保證。

Causal multicast：把前置依賴一起帶過去

P2 讀過 P1 的貼文後才回覆，第三個人就應先看到貼文，再看到回覆。兩則訊息來自不同 sender，FIFO 無法單獨處理這個要求。

課程的 causal protocol 使用向量 V。在程序 i，其他 sender 的格子記錄已 deliver 的 multicast 數量；自己的格子記錄自己送出的 multicast 數量。每次送出，先把自己的格子加一，再附上整個向量。

這與「每個 local event 都增加 counter」的通用 vector clock 不同。這裡的數字只計算 multicast。模型也假設相關通訊經過同一個群組協定；若另外透過未追蹤的通道交換資訊，就可能產生向量沒有記錄的依賴。

Receiver i 收到 sender j 的訊息，訊息帶著向量 T。必須同時滿足：

T[j] == V_i[j] + 1                 // 正好是這個 sender 的下一則
T[k] <= V_i[k]，對所有 k != j 成立  // 其他前置訊息都已 deliver

接著才能 deliver，設定 V_i[j] = T[j]，再重新檢查 buffer。不能先把 buffered message 的向量合併進 delivery vector。 知道某個依賴存在，與已經交付那則訊息，是兩回事。Sender 自己送出的訊息也只能在本機計入一次，網路繞回來的副本不能再增加 counter。

完整算一次：兩則回覆都比原文早到

向量位置固定為 [P1, P2, P3, P4]：

1. P1 multicast 原文 a，向量是 [1,0,0,0]。
2. P2 deliver a 後 multicast 回覆 b，向量是 [1,1,0,0]。
3. P4 也 deliver a，獨立 multicast 回覆 c，向量是 [1,0,0,1]。
4. P3 先收到兩則回覆，最後才收到原文。

sequenceDiagram
  participant P1
  participant P2
  participant P3
  participant P4
  P1->>P2: a [1,0,0,0]
  P1->>P4: a [1,0,0,0]
  P2->>P3: b [1,1,0,0]
  Note over P3: Buffer b：還缺 a
  P4->>P3: c [1,0,0,1]
  Note over P3: Buffer c：還缺 a
  P1->>P3: a [1,0,0,0]
  Note over P3: Deliver a，再 deliver b 和 c<br/>b、c 先後皆可

圖中只畫出解釋 P3 判斷所需的訊息；每次送出實際上都是送往整個群組的 multicast。

先釋放 c、再釋放 b 也合法。兩個回覆的向量各有一格比對方大，彼此沒有因果先後。Causal ordering 要求前置事件先發生，但不替獨立工作硬加一個順序。

若群組有 N 個程序，每則訊息要攜帶 O(N) 個 counter。這份 metadata 讓接收者能檢查依賴，卻不會消除等待慢訊息的成本。

Total order：讓 sequencer 決定每則訊息的位置

Sequencer 維護一個全域 counter，替每則 multicast 分配位置，例如 41、42。每個 receiver 保存 lastDelivered，必須同時拿到 payload 和序號分配，才能檢查是否可交付。

只有以下條件都成立，才能 deliver m：
    已有 m 的 payload
    已有 sequencer 的分配 (m, s)
    s == lastDelivered + 1

flowchart TD
  A["Sender A：訊息 x"] --> S["Sequencer"]
  B["Sender B：訊息 y"] --> S
  S --> X["分配 x = 41、y = 42"]
  X --> R1["Replica 1：先 x，再 y"]
  X --> R2["Replica 2：先 x，再 y"]
  X --> R3["Replica 3：先 x，再 y"]

Replica 2 即使先拿到 y 和序號 42，只要 lastDelivered = 40，就還是得等 41。網路收到的順序可以不同，應用程式的交付順序必須一致。課程版本由 sender multicast payload，再由 sequencer multicast 帶有序號的訊息；這張圖只聚焦在誰決定順序。

這個基本演算法假設 sequencer 持續可用。失效後重新選一個 leader 還不夠：新 sequencer 必須保留舊的序號分配，也要避免兩個 sequencer 同時產生互不相容的歷史。這需要額外的協定。

名詞也要小心。課程介紹 total order 時使用了「atomic broadcast」這個名稱；但完整的 atomic broadcast 規格，還包含 reliable delivery 等性質。單靠一個 counter，並不會自動取得完整的容錯與傳遞保證。

Reliable multicast：接收者一起把訊息傳完

用迴圈把訊息逐一送給所有成員，仍不夠可靠。假設 P1 把 m 送到 P2，接著 crash，還沒輪到 P3。即使 point-to-point link 可靠，也沒有人會替停止的 P1 繼續跑完迴圈。

課程的基本解法是 forwarding：每個 receiver 第一次收到 m，都把它再傳給群組裡所有成員。訊息需要唯一 ID，才能避免重複轉送，以及重複交付給應用程式。

sequenceDiagram
  participant P1
  participant P2
  participant P3
  P1->>P2: m
  Note over P1: 尚未聯絡 P3 就 crash
  P2->>P3: 第一次收到 m，協助轉送
  Note over P2,P3: 兩個 correct receiver 都能 deliver m

假設群組固定、correct process 之間的 link 可靠，而且 correct process 會持續執行。只要 correct P2 收到 m，它最終就會轉送給所有正常成員，包含 P3。若宣稱 P3 永遠收不到，就與前述假設矛盾。實作成逐一傳送時，也不能因為聯絡某個失效成員而永久卡住，導致後面的正常成員永遠輪不到。

規格不能只寫「大家拿到一樣的集合」，否則全部都不 deliver，也會符合這句話。需要分開描述：

• Validity： correct sender 發出的 multicast，最終會交付給正常接收者。
• Agreement： 只要一個 correct process deliver，其他正常接收者最終也會 deliver。
• Integrity： 每則訊息最多 deliver 一次，而且必須真的有人 multicast 過它。

上面的 forwarding 證明只針對 correct process。Uniform agreement 把前提加強成「任何 deliver 的程序」，包含之後會 crash 的程序。如果某個程序先 deliver、還沒轉送就 crash，就不能直接假設已經有這個更強的保證。

這個簡單方法，每次 multicast 最多可能產生 O(N²) 次 point-to-point 傳輸。它方便理解正確性，不代表是一套高效率的正式環境 transport。若網路永久分割，最終能通訊的假設也不再成立。

Virtual synchrony：跨入新 view 前，先對齊舊 view

View 是帶有識別的 membership configuration，例如 V7 = {P1,P2,P3}。成員加入、離開，或被懷疑失效，都可能導致安裝新的 view。View identity 不能省略：成員名字相同的兩個 configuration，也可能是不同的 epoch。

Virtual synchrony 把 membership event 與 multicast delivery 綁在一起。從同一個舊 view 一起進入同一個新 view 的程序，必須對舊 view 內已交付的訊息集合取得一致。在課程模型裡，訊息的 sender 也必須屬於訊息交付所在的 view。

假設 P3 在 V7 送出 m 後 crash，P1、P2 準備安裝 V8 = {P1,P2}。如果 P1 已在 V7 deliver m，P2 就不能漏掉這次舊 view 的交付，直接跨入 V8，卻仍宣稱自己完成相同的轉換。

flowchart LR
  V["V7：P1、P2、P3"] --> M["P3 送出 m 後 crash"]
  M --> F["P1、P2 處理完舊 view 的交付"]
  F --> A["兩者都在 V7 deliver m"]
  A --> N["安裝 V8：P1、P2"]

這張圖表達的是必須達成的結果，不是完整的 membership 或 flush algorithm。

若失效 sender 的訊息從未被任何存活成員 deliver，最後不交付它可以是合法結果。但只要存活成員已在舊 view deliver，就不能再靠「大家都丟掉它」修補歷史。協定必須完成相容的 view transition，或依 membership 規則排除無法共同參與的成員。

相同 view，不代表相同實體時間

P1、P2 可以在不同 wall-clock time 安裝 V8。保證的是歷史與 view boundary，不是時鐘同步。View 內採 FIFO、causal、total 或 hybrid ordering，仍是另一個選擇；訊息集合相同，不等於訊息順序相同。

課程也畫出了可分割的情境：一邊繼續使用 {P1}，另一邊使用 {P2,P3}。因此不能把共同 view 的保證解讀成「任意兩個斷線的 component 都維持同一條全域 view 序列」。Virtual synchrony 本身不會阻止分割兩側做出競爭的決策。若系統需要唯一權威歷史，還必須加上適當的 membership 或 quorum policy；這個抽象沒有繞過 Paxos 筆記 討論的 consensus 限制。

自己檢查一次

1. 回覆比原文先到，FIFO 一定會擋住嗎？ 不會。原文與回覆來自不同 sender 時，需要 causal metadata 表達依賴。
2. 所有副本用相同序號，multicast 就可靠嗎？ 不一定。它們仍可能永遠等不到某個 payload 或序號分配。
3. P1、P2 最後拿到一樣的訊息，但其中一則被歸入不同 view，符合 virtual synchrony 嗎？ 不符合。View boundary 本身就是保證的一部分。
4. Causal order 要求兩則 concurrent reply 到處都同順序嗎？ 不要求。需要這個性質時，還要加上 total order。

想操作基本的排序情境，可以回到 CS 425 互動讀本 的 multicast 區段。

資料來源與整理方式

依據 Cloud Computing Concepts, Part 1 的 2.1 Multicast Ordering、2.2 Implementing Multicast Ordering 1、2.3 Implementing Multicast 2、2.4 Reliable Multicast、2.5 Virtual Synchrony，對照投影片與逐字稿整理。圖與訊息軌跡是重新設計的教學例子；forwarding 證明與 view 範例保留課程的 crash-failure 假設，實作提醒則指出簡化演算法尚未定義的部分。