分布式系统第10章

Topic 10 - Reliable Broadcast Algorithms

Dependable and Distributed Systems | Prof. Matthew Leeke | University of Birmingham

📌 关于考试的说明（来自课堂录音）：

• 教授不会要求你背诵向量时钟的具体实现条件（IC1/IC2）——“这不公平，也不能很好地体现理解程度”
• 对算法的考察方式是：能否解释算法的本质，并以合理的细节讲清楚
• 伪代码实现”仅供你验证自己的理解是否正确”，不需要逐字背诵
• 如果问答题中你能写出实现细节，当然加分，但不强制要求

---

一、整体架构与设计哲学

广播抽象的目的是对应用层隐藏可靠性细节。

┌─────────────────────────────────┐
│         Application             │  ← 只需调用一次 broadcast
├─────────────────────────────────┤
│    Broadcast Abstraction        │  ← 处理所有可靠性逻辑
├─────────────────────────────────┤
│  Failure Detector   │  Channels │  ← 底层工具
└─────────────────────────────────┘

核心思路（来自讲义）：

• 应用程序说”请广播这条消息”，完全不用操心底层如何实现
• 广播层负责把一次 broadcast 转化为若干次 send/receive
• 最终确保应用层每条广播只被 deliver 一次

---

二、基础工具包（The Toolkit）

工具	作用
Reliable Links	保证正确节点发送的消息最终被正确节点收到
Perfect Failure Detector	精确检测节点崩溃（Accuracy + Completeness）
故障模式	本课程只考虑 Crash 故障（节点停机，不考虑拜占庭）

---

三、五种广播抽象总览

强度从弱到强：

BEB  →  RB  →  URB  →  RFB  →  COB

缩写	全称	核心新增保证
BEB	Best-Effort Broadcast	发送者正确时才可靠
RB	Reliable Broadcast	发送者崩溃也能传播（Agreement for correct）
URB	Uniform Reliable Broadcast	故障进程也尽量交付（Uniform Agreement）
RFB	Reliable FIFO Broadcast	RB + 同一发送者的消息按序交付
COB	Causal Order Broadcast	RB + 全局因果顺序交付

---

四、Best-Effort Broadcast（BEB）

4.1 三条形式化性质

性质	内容
Validity	若 $p_i$（发送者）和 $p_j$（接收者）都正确，则 $p_j$ 最终交付消息
No Duplication	消息不被重复交付
No Creation	不凭空创造消息

💡 讲义重点：这三条性质是所有后续广播算法的共同基础，每种算法都继承它们，区别在于第四条性质如何定义。

4.2 关键缺陷

发送者崩溃时：

• 部分进程收到消息，另一部分收不到
• 没有一致性保证——同一系统里不同进程的状态不同
• 教授类比：”如果把这些进程类比为数据库服务器，这就会导致不一致性！”

4.3 算法（基于 Reliable Links）

Implements: BestEffortBroadcast (BEB)
Uses: ReliableLinks (rp2p)

upon BEBBroadcast(m):
    for all q in {p1,...,pn}:
        rp2pSend(q, m)     ← 逐一用可靠链路发送给所有人

upon rp2pDeliver(q, m):
    trigger BEBDeliver(q, m)

复杂度：每次广播 $N$ 条消息（最优也是 $N$）

---

五、Reliable Broadcast（RB）

5.1 新增第四条性质

在 BEB 三条基础上加：

Agreement：对任意消息 $m$，若任意一个正确进程交付了 $m$，则所有正确进程都必须交付 $m$。

5.2 直觉理解（来自讲义）

“提供 all-or-nothing 语义——要么大家（所有正确进程）都收到，要么大家都收不到。”
“Agreement 是活性（liveness）还是安全性（safety）性质？”（这是课上提问，值得思考）

关键点：

• 只对正确进程（correct processes）有要求
• 故障进程：可以交付也可以不交付，我们不在乎
• 一个进程崩溃了就不是 correct process，所以 P1 崩溃后，P1 之前是否交付了消息，对协议的正确性没有影响

5.3 典型场景图解

场景一：发送者崩溃，但有进程收到了消息

p1 → RBroadcast(m) → 崩溃
p2 → BEBDeliver(m) → 代为转发 → p3 也收到 ✓
p3 → RBDeliver(m) ✓

场景二：发送者崩溃，没有进程收到消息

p1 → RBroadcast(m) → 崩溃（发出前就崩了）
p2 → 从未收到 → 也不会交付（正确！）
p3 → 从未收到 → 也不会交付（正确！）

这是完全合法的——因为没有正确进程交付，Agreement 不被违反。

5.4 算法

核心思路：

1. 正常情况：RBroadcast → BEBBroadcast（直接依赖 BEB）
2. 发送者崩溃时：用 Perfect Failure Detector 检测到崩溃，代为转发该发送者的消息

Implements: ReliableBroadcast (RB)
Uses: BEB, PerfectFailureDetector (P)

Init:
    delivered = {}
    correct = {p1,...,pn}
    from[pi] = {} for all pi

upon RBBroadcast(m):
    BEBBroadcast([Data, self, m])

upon crash(pi):                          ← 检测到 pi 崩溃
    correct = correct \ {pi}
    for all [pj, m] in from[pi]:
        BEBBroadcast([Data, pj, m])      ← 替 pi 转发它还没广播完的消息

upon BEBDeliver(pi, [Data, pj, m]):
    if m not in delivered:
        delivered += {m}
        RBDeliver(pj, m)
        if pi not in correct:            ← pi 已经崩溃，要帮它转发
            BEBBroadcast([Data, pj, m])
    from[pi] += {[pj, m]}

5.5 复杂度分析

情形	消息数
最优（无故障）	$N$ 条
最差（全部进程级联转发）	$N^2$ 条

💡 讲义提示：$N^2$ 的情况对应”每个进程都需要转发”——级联失败场景。教授说：”我每次看到级联失败，都怀疑有人在恶意发消息触发进程崩溃——这是安全漏洞的特征。”

---

六、Uniform Reliable Broadcast（URB）

6.1 与 RB 的唯一区别

RB Agreement vs URB Uniform Agreement 的对比：

	触发条件	要求
RB Agreement	正确进程交付了 $m$	所有正确进程也交付 $m$
URB Uniform Agreement	任意进程（含故障）交付了 $m$	所有正确进程也交付 $m$

本质上就是去掉了”correct”这个词的限定。

6.2 为什么需要 URB

讲义原话：故障进程在崩溃前可能已经交付了消息，这在实时系统中可能已经被用户观察到，或被写入日志。URB 保证这种”已观察到的交付”不会导致不一致。

6.3 算法思路：等待所有存活进程确认

核心思路：

• 每条消息附带一个 ack[m] 集合，记录哪些进程已经 BEBDeliver 了该消息
• 只有当所有当前存活进程都确认后，才触发 URBDeliver
• 同时采用 eager relay（急切转发）——收到消息立刻转发给所有人

Implements: UniformReliableBroadcast (URB)
Uses: BEB, PerfectFailureDetector (P)

Init:
    delivered = {}, pending = {}, correct = {p1,...,pn}
    ack[m] = {} for all m

upon crash(pi):
    correct = correct \ {pi}

upon URBBroadcast(m):
    pending += {[self, m]}
    BEBBroadcast([Data, self, m])

upon BEBDeliver(pi, [Data, pj, m]):
    ack[m] += {pi}                           ← 记录 pi 已确认
    if [pj, m] not in pending:
        pending += {[pj, m]}
        BEBBroadcast([Data, pj, m])          ← 急切转发

when [pj,m] in pending
     AND correct ⊆ ack[m]                   ← 所有存活进程都确认了
     AND m not in delivered:
    delivered += {m}
    URBDeliver(pj, m)

6.4 正确性证明思路（Lemma）

引理：若某正确进程执行了 BEBDeliver(m)，则它最终也会 URBDeliver(m)。

证明链：

1. 执行 BEBDeliver(m) 的进程会执行 BEBBroadcast(m)（eager relay）
2. 由 BEB Validity，所有正确进程最终都会 BEBDeliver(m) → 都加入 ack[m]
3. Failure Detector 的 Completeness 保证：崩溃进程最终从 correct 中移除
4. 因此条件 correct ⊆ ack[m] 最终成立 → URBDeliver(m) 触发 ✓

---

七、FIFO Reliable Broadcast（RFB）

7.1 新增性质

FIFO Order：若 $p_i$ 先广播 $m_1$ 再广播 $m_2$，则任意其他进程 $p_j$ 不得在交付 $m_1$ 之前交付 $m_2$。

7.2 重要理解（来自讲义）

FIFO 是per-process 顺序：

• 保证你收到 Alice 发的消息按 Alice 的发送顺序排列
• 保证你收到 Bob 发的消息按 Bob 的发送顺序排列
• 但不保证 Alice 和 Bob 的消息之间有任何顺序关系

举例：Alice 发 A→B，Bob 发 X→Y，以下顺序都合法：

• X, A, B, Y ✓
• X, Y, A, B ✓
• A, X, B, Y ✓

7.3 算法（在 RB 基础上加序列号+缓冲区）

Implements: ReliableFifoBroadcast (RFB)
Uses: ReliableBroadcast (RB)

Init:
    buffer = {}
    next[src] = 1 for all src   ← 每个发送者下一个期待的序号
    seq = 1                     ← 本进程的发送序号

upon RFBBroadcast(m):
    RBroadcast((seq, m))        ← 带上序列号
    seq += 1

upon RDeliver(src, (sn, m)):
    buffer += (src, sn, m)
    while (src', sn', m') in buffer where sn' == next[src']:
        RFDeliver(src', m')
        next[src'] += 1         ← 按序号顺序交付
        buffer -= (src', sn', m')

💡 本质：维护一个缓冲区，只有序号连续时才交付——类似 TCP 的有序交付机制。

---

八、Causal Order Broadcast（COB）

8.1 为什么需要因果广播

FIFO 只保证单进程内有序，但跨进程的因果依赖无法捕获：

讲义例子（Bloomberg）：Bloomberg 终端广播金融事件。事件 B 是因为事件 A 发生而产生的（因果关系）。如果 B 在 A 之前被交付，用户会看到”结果”先于”原因”出现。

8.2 因果关系的定义

$m_1 \to m_2$（$m_1$ 因果先于 $m_2$）成立，当且仅当满足以下任一条件：

规则	描述
FIFO Order	同一进程先广播 $m_1$ 再广播 $m_2$
Local Order	某进程先交付 $m_1$，然后广播 $m_2$
Transitivity	存在 $m_3$ 使得 $m_1 \to m_3$ 且 $m_3 \to m_2$

8.3 新增性质

Causal Order：若 $m_1 \to m_2$，则任何进程交付 $m_2$ 之前必须先交付 $m_1$。

8.4 两种实现

方法一：携带历史（非阻塞）

思路：每次广播时，把自己已知的全部历史消息一并打包发出。接收方先交付历史，再交付当前消息。

upon COBBroadcast(m):
    RBroadcast([Data, past, m])    ← past 包含所有之前的消息
    past += {[self, m]}

upon RDeliver(pi, [Data, past_m, m]):
    for all [sn, m'] in past_m:    ← 先处理历史中未交付的消息
        if m' not in delivered:
            CODeliver(sn, m')
            delivered += {m'}
    CODeliver(pi, m)
    delivered += {m}

缺点：随着历史增长，消息体积越来越大。

方法二：向量时钟（阻塞，更推荐）

思路：每个进程维护向量时钟 $VC$，只广播计数而非完整历史。收到消息后，检查本地 $VC$ 是否已”追上”消息的因果前提，未追上则放入 pending 等待。

Init:
    VC[pi] = 0 for all pi
    pending = {}

upon COBBroadcast(m):
    CODeliver(self, m)
    RBroadcast([Data, VC, m])
    VC[self] += 1

upon RDeliver(pj, [Data, VCm, m]):
    if pj != self:
        pending += {(pj, VCm, m)}
    trigger DeliverPending

upon DeliverPending:
    while (sx, VCx, x) in pending
          where VC[pj] >= VCx[pj] for all pj:   ← 本地时钟已满足因果前提
        pending -= (sx, VCx, x)
        CODeliver(sx, x)
        VC[sx] += 1

💡 讲义原话：向量时钟方法”更简洁”，因为”回到时钟，就完事了”。Bloomberg 使用的实现与此几乎相同。

⚠️ 考试提示：向量时钟的 IC1/IC2 形式化条件不需要背。但需要理解：向量时钟能捕获全局因果顺序的原因，以及它与 FIFO 的区别。

---

九、全局总结与层次关系

COB（因果广播）        ← "全局 FIFO"，跨进程因果顺序
    │
    └── RFB（FIFO广播）← 单进程内有序
            │
            ├── URB（统一可靠广播）← 故障进程也尽量交付
            │       │
            │       └── RB（可靠广播）← 发送者独立性
            │               │
            │               └── BEB（尽力广播）← 最基础
            │
            └── UFB（统一 FIFO 广播）← URB + FIFO

性质对比一览

性质	BEB	RB	URB	RFB	COB
Validity	✓	✓	✓	✓	✓
No Duplication	✓	✓	✓	✓	✓
No Creation	✓	✓	✓	✓	✓
Agreement	—	✓（correct）	✓（all）	✓	✓
FIFO Order	—	—	—	✓	✓
Causal Order	—	—	—	—	✓

---

十、关键概念辨析

Agreement vs Uniform Agreement

RB Agreement:       if a CORRECT process delivers m
                    → all correct processes deliver m

URB Uniform Agreement: if ANY process delivers m (even faulty)
                       → all correct processes deliver m

FIFO vs Causal Order

FIFO：   per-process 顺序
         Alice: A→B 保证，Bob: X→Y 保证
         但 A,B 与 X,Y 之间的顺序不保证

Causal： global 因果顺序
         只要 m1 → m2（因果关系），
         任何进程都必须在 m2 前看到 m1

为何 URB 需要等待所有进程确认

因为如果一个进程在崩溃前交付了 $m$，根据 Uniform Agreement，所有正确进程都必须也交付 $m$。所以必须在”确认所有存活进程都能看到这条消息”后，才能安全交付。

---

十一、考试备考要点

✅ 需要掌握：

• 五种广播抽象各自的核心性质（尤其是第四条）
• BEB → RB → URB 之间的演进逻辑（每步加了什么）
• RB 算法的 relay 机制与 Failure Detector 的配合
• URB 算法为何需要”等待所有存活进程确认”
• FIFO vs Causal Order 的本质区别
• 向量时钟为什么能解决因果顺序问题（不需要背公式）

❌ 不需要背：

• 向量时钟的 IC1/IC2 形式化条件
• 算法伪代码的完整逐行细节
• 具体的 rp2p、sp2p 实现细节