【分布式系统百科】可靠广播：从尽力而为到全序的五层抽象

三个副本需要以相同顺序执行同一批写操作。节点 A 先广播 x=1，再广播 x=2；节点 B 收到的顺序却是 x=2 然后 x=1。副本状态分叉了——A 认为 x=2，B 认为 x=1。更糟糕的是，如果 A 在发完第一条消息后崩溃，某些节点收到了 x=1，另一些没收到。此时系统中存在两类节点：知道 x=1 的和不知道的。后续所有基于 x 的决策都可能出现不一致。

这不是理论上的边界情况。任何状态机复制（State Machine Replication）系统——无论是数据库、配置中心还是协调服务——都需要解决的核心问题就是：如何让一组进程以相同的顺序看到相同的消息集合。

广播原语（broadcast primitive）是分布式系统中解决这类问题的基础抽象。从最弱的尽力广播到最强的全序广播，形成了一个严格的层次结构，每一层在下层基础上增加一个关键属性。理解这个层次是理解分布式系统核心机制的必经之路。

本文按照 Hadzilacos 和 Toueg 在 1994 年奠基性论文中建立的分类框架，逐层拆解五种广播抽象：尽力广播、可靠广播、FIFO 广播、因果广播和全序广播。每一层我们都会给出形式化定义、实现算法、伪代码和具体的失败场景，最终证明全序广播与共识的等价性，并讨论在 Kafka、ZooKeeper 和 etcd 中的工程实现。

一、尽力广播（Best-effort Broadcast）

1.1 问题场景

考虑一个最简单的分布式系统：三个进程 p1、p2、p3 通过网络互连。p1 想把一条消息 m 发给所有人（包括自己）。最朴素的做法就是 p1 对每个进程调用一次点对点发送（send）。

这看起来够用了——直到 p1 在发完给 p2 的消息之后、发给 p3 之前崩溃。结果是 p1 和 p2 收到了 m，p3 没收到。系统中出现了不一致。

尽力广播（Best-effort Broadcast，BEB）是最弱的广播抽象，它对这种情况不做任何保证。BEB 的设计哲学是：发送者尽力而为，如果发送者崩溃，不保证任何事情。

1.2 形式化定义

尽力广播定义在一组进程 \(\Pi = \{p_1, p_2, ..., p_n\}\) 上，提供两个接口：

• broadcast(m)：广播消息 m
• deliver(m)：交付消息 m（由广播层回调给上层应用）

注意”交付”（deliver）和”接收”（receive）的区别：receive 是网络层的概念，deliver 是广播抽象层的概念。广播层可能接收了一条消息但选择不交付（例如去重），也可能延迟交付（例如等待因果依赖）。

BEB 需要满足三个属性：

有效性（Validity）：如果一个正确的（correct）进程广播了消息 m，则每个正确的进程最终交付 m。

无重复（No Duplication）：每条消息最多被交付一次。

无凭空创造（No Creation）：如果一条消息被交付，则它之前一定被某个进程广播过。

这里”正确的进程”指在整个执行过程中不崩溃的进程。有效性属性只要求发送者正确时才保证交付——如果发送者崩溃了，BEB 不做任何承诺。

1.3 实现

BEB 的实现极其简单——对每个进程调用一次底层的完美点对点链路（Perfect Point-to-Point Link）发送：

class BestEffortBroadcast:
    def __init__(self, processes, link):
        self.processes = processes  # 所有进程列表
        self.link = link            # 完美点对点链路

    def broadcast(self, m):
        for p in self.processes:
            self.link.send(p, m)

    def on_receive(self, sender, m):
        self.deliver(m)  # 收到即交付

完美点对点链路（Perfect Point-to-Point Link）本身需要满足：可靠传递（如果发送者和接收者都正确，消息最终被接收）、无重复、无凭空创造。TCP 加上应用层去重可以实现这个抽象。

1.4 BEB 的局限

BEB 的问题在于：如果发送者在广播过程中崩溃，可能只有部分进程收到了消息。

时间线：
p1: broadcast(m) → send(p1,m) → send(p2,m) → [崩溃] → 未发送给 p3
p2: deliver(m)     -- 成功
p3: 永远不会收到 m  -- 失败

这违反了我们通常对”广播”的直觉期望：要么所有人都收到，要么都不收到。BEB 没有提供这种”全有或全无”的保证。在实际系统中，这意味着如果 BEB 用于状态机复制，副本状态可能分叉。

二、可靠广播（Reliable Broadcast）

2.1 问题：发送者崩溃后的一致性

BEB 的核心缺陷是：当发送者崩溃时，某些正确进程可能交付了消息，而另一些没有。可靠广播（Reliable Broadcast，RB）通过增加一个关键属性来解决这个问题。

2.2 形式化定义

可靠广播在 BEB 的三个属性基础上增加第四个属性：

一致性（Agreement）：如果任意一个正确的进程交付了消息 m，则所有正确的进程最终交付 m。

一致性属性的力量在于：即使发送者崩溃了，只要有一个正确进程交付了这条消息，所有其他正确进程也必须交付。这意味着系统不会出现”部分进程知道、部分不知道”的状态。

将四个属性合在一起：

2.3 急切可靠广播（Eager Reliable Broadcast）

最直接的实现思路是：每个进程在第一次交付某条消息时，把它转发给所有其他进程。这样，即使原始发送者崩溃了，只要有一个正确进程收到了消息，它就会转发给所有人，保证一致性。

class EagerReliableBroadcast:
    def __init__(self, processes, beb):
        self.processes = processes
        self.beb = beb             # 底层尽力广播
        self.delivered = set()     # 已交付的消息 ID 集合

    def broadcast(self, m):
        self.beb.broadcast(m)

    def on_beb_deliver(self, m):
        if m.id not in self.delivered:
            self.delivered.add(m.id)
            self.beb.broadcast(m)  # 转发给所有进程
            self.deliver(m)        # 向上层交付

正确性论证：假设某个正确进程 pi 交付了消息 m。根据算法，pi 在交付前会通过 BEB 转发 m 给所有进程。由于 pi 是正确的，BEB 的有效性保证所有正确进程最终收到 m。每个正确进程收到 m 后（如果未交付过）也会交付。因此一致性得到满足。

消息复杂度：O(n^2)。每条原始广播消息会被转发 n 次，每次转发又通过 BEB 发送 n 条点对点消息。在 n 较大时，这个开销是不可接受的。

2.4 懒惰可靠广播（Lazy Reliable Broadcast）

急切方案的问题在于：在没有故障的情况下，转发是多余的。如果所有进程都正确，BEB 本身就足够了。只有当某个进程崩溃时，才需要其他进程”接管”转发。

懒惰可靠广播（Lazy Reliable Broadcast）利用故障检测器（Failure Detector）来优化：只在检测到某个进程崩溃时，才转发从该进程收到的消息。

class LazyReliableBroadcast:
    def __init__(self, processes, beb, failure_detector):
        self.processes = processes
        self.beb = beb
        self.fd = failure_detector  # 完美故障检测器
        self.delivered = set()
        self.received_from = {}     # 进程 → 该进程收到的消息集合
        self.correct = set(processes)

        self.fd.on_suspect(self.on_crash)

    def broadcast(self, m):
        self.beb.broadcast(m)

    def on_beb_deliver(self, sender, m):
        # 记录从 sender 收到的消息
        if sender not in self.received_from:
            self.received_from[sender] = set()
        self.received_from[sender].add(m)

        if m.id not in self.delivered:
            self.delivered.add(m.id)
            self.deliver(m)

    def on_crash(self, crashed_process):
        self.correct.discard(crashed_process)
        # 转发所有从崩溃进程收到的消息
        if crashed_process in self.received_from:
            for m in self.received_from[crashed_process]:
                self.beb.broadcast(m)

消息复杂度：在无故障时为 O(n)——与 BEB 相同。只有当检测到崩溃时才产生额外的 O(n^2) 消息。这在故障率低的环境中显著优于急切方案。

但懒惰方案依赖完美故障检测器（Perfect Failure Detector，P 类），即不会误报也不会漏报的故障检测器。在异步系统中，完美故障检测器不可实现（FLP 不可能定理的推论）。实践中使用的是最终完美故障检测器（Eventually Perfect Failure Detector，◇P 类），它可能暂时误报，但最终会收敛到正确状态。使用 ◇P 类检测器时，算法需要额外处理误报的情况。

sequenceDiagram
    participant P1 as 进程 p1（发送者）
    participant P2 as 进程 p2
    participant P3 as 进程 p3

    rect rgb(230, 245, 255)
        Note over P1,P3: 尽力广播层（BEB）
        P1->>P2: send(m)
        P1->>P3: send(m)
        Note right of P1: p1 崩溃前发出
    end

    rect rgb(255, 245, 230)
        Note over P1,P3: 可靠广播层（RB）
        P2->>P3: relay(m)
        Note over P2,P3: p2 检测到 p1 崩溃后转发
    end

    rect rgb(230, 255, 230)
        Note over P1,P3: 因果交付层
        P2-->>P2: deliver(m) 按因果顺序
        P3-->>P3: deliver(m) 按因果顺序
    end

上图展示了分层广播的消息传递过程。在尽力广播层（BEB），发送者 p1 将消息直接发送给所有进程；在可靠广播层（RB），当 p2 检测到 p1 崩溃后主动转发消息，确保所有正确进程都能收到；最终在因果交付层，各进程按因果顺序交付消息。这种分层设计使得每一层的职责清晰，高层协议可以复用低层的保证。

flowchart LR
    subgraph Eager["急切可靠广播"]
        S1["发送者广播 m"] --> ALL1["所有进程收到 m"]
        ALL1 --> RE["每个进程首次收到时<br/>再次广播给所有进程"]
        RE --> DONE1["全部交付"]
    end
    
    subgraph Lazy["懒惰可靠广播"]
        S2["发送者广播 m"] --> ALL2["所有进程收到 m"]
        ALL2 --> DET["故障检测器<br/>检测到发送者崩溃"]
        DET -->|"仅在崩溃时"| RE2["转发崩溃者的消息"]
        ALL2 -->|"无崩溃"| DONE2["直接交付"]
        RE2 --> DONE2
    end

急切可靠广播的核心思想是”收到即转发”：每个进程首次收到消息时立即向所有进程重新广播，消息复杂度始终为 O(n^2)。懒惰可靠广播则利用故障检测器延迟转发——仅在检测到发送者崩溃时才触发重广播，无故障时消息复杂度仅为 O(n)。两种方案的取舍在于：急切方案简单可靠但通信开销大，懒惰方案高效但依赖故障检测器的准确性。

2.5 均匀可靠广播（Uniform Reliable Broadcast）

前面定义的可靠广播有一个微妙的问题：一致性属性只涉及”正确的”进程。如果一个即将崩溃的进程在崩溃前交付了消息 m，而某些正确进程没有交付 m，这不违反一致性——因为崩溃进程不是”正确的”。

但在某些场景中这是不可接受的。例如，一个进程在交付消息后、崩溃前执行了一个不可撤销的外部操作（比如给客户转账）。如果其他进程没有交付同一条消息，系统状态就不一致了。

均匀可靠广播（Uniform Reliable Broadcast，URB）用更强的属性替换一致性：

均匀一致性（Uniform Agreement）：如果任意进程（无论正确与否）交付了消息 m，则所有正确的进程最终交付 m。

实现 URB 需要在交付前收集多数确认。基本思路是：一个进程收到消息后不立即交付，而是先转发给所有进程并等待多数进程确认收到，然后才交付。

class UniformReliableBroadcast:
    def __init__(self, processes, beb, failure_detector):
        self.processes = processes
        self.n = len(processes)
        self.beb = beb
        self.fd = failure_detector
        self.delivered = set()
        self.pending = {}      # msg_id → message
        self.ack = {}          # msg_id → 已确认的进程集合
        self.correct = set(processes)

        self.fd.on_suspect(self.on_crash)

    def broadcast(self, m):
        self.pending[m.id] = m
        self.beb.broadcast(m)

    def on_beb_deliver(self, sender, m):
        if m.id not in self.ack:
            self.ack[m.id] = set()
        self.ack[m.id].add(sender)

        if m.id not in self.pending:
            self.pending[m.id] = m
            self.beb.broadcast(m)  # 转发

        self.try_deliver(m)

    def on_crash(self, p):
        self.correct.discard(p)
        for m_id in self.pending:
            self.try_deliver(self.pending[m_id])

    def try_deliver(self, m):
        if m.id in self.delivered:
            return
        # 只有当所有正确进程都确认时才交付
        if self.correct.issubset(self.ack.get(m.id, set())):
            self.delivered.add(m.id)
            self.deliver(m)

URB 的代价是更高的延迟：交付前需要等待多数确认，至少一个额外的网络往返。

三、FIFO 广播（FIFO Broadcast）

3.1 问题：同一发送者的消息乱序

可靠广播保证了”要么全交付、要么全不交付”，但没有对交付顺序做任何限制。考虑以下场景：

p1: broadcast(m1: "余额=100")
p1: broadcast(m2: "余额=80")

p2 的交付顺序：m2, m1 → 最终看到余额=100（错误）
p3 的交付顺序：m1, m2 → 最终看到余额=80（正确）

p1 先发了余额 100，再发了余额 80（扣了 20）。但 p2 先收到 m2 再收到 m1，如果用后到的消息覆盖先到的，p2 最终认为余额是 100。这种同一发送者消息乱序的问题，在可靠广播中是允许的。

3.2 形式化定义

FIFO 广播（FIFO Broadcast）在可靠广播的基础上增加：

FIFO 顺序（FIFO Order）：如果某个正确的进程广播了消息 m1，之后又广播了消息 m2，则没有正确的进程在交付 m1 之前交付 m2。

换言之：来自同一发送者的消息必须按发送顺序交付。不同发送者之间的消息顺序不受约束。

3.3 基于序列号的实现

实现 FIFO 广播的标准方法是让每个发送者维护一个单调递增的序列号（sequence number）。接收方为每个发送者维护一个计数器，记录下一个期望的序列号。如果收到的消息序列号不是期望值，就缓存起来，等到前面的消息都交付后再交付。

class FIFOBroadcast:
    def __init__(self, processes, rb, my_id):
        self.rb = rb               # 底层可靠广播
        self.my_id = my_id
        self.send_seq = 0          # 本进程的发送序列号
        self.next_deliver = {}     # sender → 下一个期望的序列号
        self.pending = {}          # sender → {seq: message} 缓存

        for p in processes:
            self.next_deliver[p] = 1
            self.pending[p] = {}

    def broadcast(self, m):
        self.send_seq += 1
        tagged_msg = FIFOMessage(
            sender=self.my_id,
            seq=self.send_seq,
            payload=m
        )
        self.rb.broadcast(tagged_msg)

    def on_rb_deliver(self, fm):
        sender = fm.sender
        seq = fm.seq

        # 缓存消息
        self.pending[sender][seq] = fm

        # 按顺序交付
        while self.next_deliver[sender] in self.pending[sender]:
            next_seq = self.next_deliver[sender]
            msg = self.pending[sender].pop(next_seq)
            self.next_deliver[sender] += 1
            self.deliver(msg.payload)

消息复杂度：与底层可靠广播相同，FIFO 层本身不增加额外消息——只是通过缓存和排序来控制交付时机。

3.4 FIFO 的局限：无法捕获跨进程因果关系

FIFO 保证了单发送者内的顺序，但对跨发送者的因果关系无能为力。考虑经典的”聊天室”场景：

p1: broadcast("今晚吃什么？")
p2: [交付了 p1 的消息] → broadcast("去吃火锅吧")
p3 的交付顺序可能是："去吃火锅吧", "今晚吃什么？"

p2 的回复是因为看到了 p1 的问题。这两条消息之间存在因果关系（causal dependency）：p2 的消息因果依赖于 p1 的消息。但 FIFO 广播不关心跨发送者的因果关系——它只保证 p1 的消息之间有序、p2 的消息之间有序。p3 完全可能先收到 p2 的回答再收到 p1 的问题。

在人类聊天中这只是令人困惑；在分布式系统中，如果操作之间有因果依赖（读后写、写后读），FIFO 的无序可能导致数据不一致。

四、因果广播（Causal Broadcast）

4.1 因果关系的定义

因果广播（Causal Broadcast）解决的是跨发送者的因果顺序问题。要理解因果广播，首先需要精确定义”因果关系”。

Lamport 在 1978 年定义的”先发生”（happens-before）关系 \(\rightarrow\) 是因果关系的形式化：

1. 进程内顺序：如果同一进程中事件 a 发生在事件 b 之前，则 \(a \rightarrow b\)
2. 消息传递：如果 a 是消息 m 的发送事件，b 是 m 的接收事件，则 \(a \rightarrow b\)
3. 传递性：如果 \(a \rightarrow b\) 且 \(b \rightarrow c\)，则 \(a \rightarrow c\)

如果既不是 \(a \rightarrow b\) 也不是 \(b \rightarrow a\)，则 a 和 b 是并发的（concurrent），记为 \(a \| b\)。

在广播的语境中，消息 m1 因果先于（causally precedes）消息 m2，记为 \(m1 \prec m2\)，当且仅当 m1 的广播事件先发生于 m2 的广播事件。

4.2 形式化定义

因果广播在可靠广播的基础上增加：

因果顺序（Causal Order）：如果消息 m1 因果先于消息 m2（\(m1 \prec m2\)），则没有正确的进程在交付 m1 之前交付 m2。

注意：因果顺序严格强于 FIFO 顺序。同一发送者的连续消息天然满足 \(m1 \prec m2\)（进程内顺序），所以因果顺序蕴含 FIFO 顺序。但因果顺序还额外要求跨发送者的因果依赖也被尊重。

4.3 因果过去（Causal Past）

一条消息 m 的因果过去（causal past）是所有因果先于 m 的消息集合。形式化地：

\[\text{past}(m) = \{m' \mid m' \prec m\}\]

因果广播的交付规则可以等价地表述为：进程只有在交付了 m 的所有因果过去之后，才能交付 m。

4.4 基于向量时钟的实现

实现因果广播的经典方法是使用向量时钟（Vector Clock）。每个进程维护一个长度为 n 的向量（n 是进程总数），其中第 i 个分量记录该进程从进程 i 交付的消息数量。

class CausalBroadcast:
    def __init__(self, processes, rb, my_id):
        self.rb = rb
        self.my_id = my_id
        self.n = len(processes)
        self.process_ids = {p: i for i, p in enumerate(processes)}
        self.my_index = self.process_ids[my_id]

        # 向量时钟：vc[i] = 从进程 i 交付的消息数量
        self.vc = [0] * self.n
        self.pending = []  # 缓存的待交付消息

    def broadcast(self, m):
        # 发送时，先递增自己的分量
        self.vc[self.my_index] += 1
        # 消息携带发送者的向量时钟副本
        causal_msg = CausalMessage(
            sender=self.my_id,
            vc=list(self.vc),  # 深拷贝
            payload=m
        )
        self.rb.broadcast(causal_msg)

    def on_rb_deliver(self, cm):
        self.pending.append(cm)
        self.try_deliver_pending()

    def try_deliver_pending(self):
        delivered_something = True
        while delivered_something:
            delivered_something = False
            for cm in list(self.pending):
                if self.can_deliver(cm):
                    self.pending.remove(cm)
                    sender_index = self.process_ids[cm.sender]
                    self.vc[sender_index] += 1
                    self.deliver(cm.payload)
                    delivered_something = True

    def can_deliver(self, cm):
        sender_index = self.process_ids[cm.sender]
        msg_vc = cm.vc

        # 条件 1：消息的发送者分量 = 本地对应分量 + 1
        if msg_vc[sender_index] != self.vc[sender_index] + 1:
            return False

        # 条件 2：对于所有其他进程 j != sender，
        #          消息的向量时钟分量 <= 本地分量
        for j in range(self.n):
            if j != sender_index:
                if msg_vc[j] > self.vc[j]:
                    return False

        return True

交付条件解释：

• 条件 1 确保来自同一发送者的消息按序列号顺序交付（FIFO 顺序）。
• 条件 2 确保发送者在广播这条消息之前交付的所有其他进程的消息，接收方也已经交付了（因果依赖满足）。

两个条件合在一起，精确地编码了”交付 m 之前必须先交付 m 的所有因果过去”这一要求。

4.5 具体示例：FIFO 满足但因果违反

下面用具体例子说明 FIFO 广播和因果广播的区别：

系统包含三个进程：p1, p2, p3

事件序列：
1. p1 广播 m1: "写入 x=1"
2. p2 交付 m1
3. p2 广播 m2: "写入 y=x+1"  （m2 因果依赖 m1）
4. p3 交付 m2
5. p3 交付 m1

FIFO 检查：
- p1 只发了 m1，p3 交付了 m1 → FIFO 满足
- p2 只发了 m2，p3 交付了 m2 → FIFO 满足
结论：FIFO 顺序未被违反

因果检查：
- m1 → m2（p2 先交付 m1 再广播 m2，因果链）
- p3 先交付 m2 再交付 m1 → 违反因果顺序
结论：因果顺序被违反

在这个例子中，p3 在不知道 x=1 的情况下就执行了 y=x+1。如果 p3 使用的是旧的 x 值（比如 x=0），则 p3 计算出 y=1，而 p2 计算出 y=2。副本状态分叉。

使用向量时钟的因果广播可以避免这个问题：p3 收到 m2 时检查向量时钟，发现 m2 依赖 m1（m2 的向量时钟中 p1 的分量大于 p3 本地记录的值），于是将 m2 缓存，直到 m1 被交付后才交付 m2。

sequenceDiagram
    participant P1 as 节点 A
    participant P2 as 节点 B
    participant P3 as 节点 C

    P1->>P1: broadcast(m1)
    P1->>P2: m1
    P1->>P3: m1（网络延迟较大）
    
    Note over P2: 交付 m1
    P2->>P2: broadcast(m2)，因果依赖 m1
    P2->>P3: m2（先于 m1 到达 C）
    P2->>P1: m2
    
    Note over P3: 收到 m2 但 m1 未到达
    P3-->>P3: 缓存 m2，等待 m1
    
    Note over P3: 收到 m1
    P3->>P3: 交付 m1
    P3->>P3: 交付 m2（因果依赖已满足）

上图展示了因果广播中消息延迟导致乱序到达的典型场景。节点 B 在交付 m1 后广播 m2，因此 m2 因果依赖于 m1。当 m2 先于 m1 到达节点 C 时，因果广播协议会将 m2 缓存，直到其因果依赖 m1 被交付后，才按正确的因果顺序交付 m2。

4.6 向量时钟工作示例：三节点场景

下面通过一个三节点（p1、p2、p3）的完整示例，逐步追踪向量时钟在因果广播中的运作过程。每个步骤展示事件发生后各节点的向量时钟状态，以及交付决策的依据。

初始状态：所有节点的向量时钟均为 [0, 0, 0]，三个分量分别对应 p1、p2、p3 的逻辑时钟。

步骤  事件                           p1.VC      p2.VC      p3.VC      说明
──── ───────────────────────────── ────────── ────────── ────────── ──────────────────────────────
 0   初始状态                       [0,0,0]    [0,0,0]    [0,0,0]    所有节点向量时钟清零
 1   p1 广播 m1                     [1,0,0]    [0,0,0]    [0,0,0]    p1 递增自身分量后广播
 2   p2 收到 m1，检查 VC            [1,0,0]    [1,0,0]    [0,0,0]    m1.VC=[1,0,0]，p2.VC[0]=0
                                                                      需要 VC[0]>=1，满足（取 max）
                                                                      → 交付 m1，更新 VC
 3   p2 广播 m2（因果依赖 m1）       [1,0,0]    [1,1,0]    [0,0,0]    p2 递增自身分量：VC[1] → 1
                                                                      m2 携带 VC=[1,1,0]
 4   p3 收到 m2，检查 VC            [1,0,0]    [1,1,0]    [0,0,0]    m2.VC=[1,1,0]，p3.VC=[0,0,0]
                                                                      需要 VC[0]>=1，但 p3.VC[0]=0
                                                                      → 不满足，缓存 m2
 5   p3 收到 m1，检查 VC            [1,0,0]    [1,1,0]    [1,0,0]    m1.VC=[1,0,0]，p3.VC=[0,0,0]
                                                                      需要 VC[0]>=1，满足（取 max）
                                                                      → 交付 m1，更新 VC
 6   p3 重新检查缓存中的 m2         [1,0,0]    [1,1,0]    [1,1,0]    m2.VC=[1,1,0]，p3.VC=[1,0,0]
                                                                      需要 VC[0]>=1 且 VC[1]>=1
                                                                      VC[0]=1>=1 ✓，VC[1]=0？
                                                                      对于发送者 p2 的分量：
                                                                      只需 m2.VC[j]<=p3.VC[j]
                                                                      对所有 j≠sender 成立
                                                                      → 交付 m2，更新 VC

关键观察：

• 步骤 4 是因果广播的核心机制体现：m2 的向量时钟 [1,1,0] 表明 m2 依赖于 p1 的第 1 个事件（即 m1），但 p3 尚未交付 m1（p3.VC[0]=0），因此必须缓存 m2。
• 步骤 5-6 展示了因果依赖的解除过程：m1 交付后 p3 的向量时钟更新，使得 m2 的交付条件得到满足。
• 整个过程保证了因果顺序：尽管 m2 在网络层先于 m1 到达 p3，但在应用层 p3 仍然先交付 m1、后交付 m2。

4.7 向量时钟的开销

向量时钟方案的消息开销是 O(n)——每条消息需要携带一个长度为 n 的向量。当进程数很大时（例如大规模集群中 n = 10000），这个开销变得不可接受。

实践中的优化方案包括：

• 压缩向量时钟：只携带自上次发送以来变化的分量（差量编码）
• 哈希向量时钟：使用哈希映射代替固定长度数组，只存储非零分量
• 矩阵时钟：携带更多信息，允许垃圾回收旧的因果依赖
• 柏林团队的 Bloom Clock：使用概率数据结构压缩因果元数据

五、全序广播（Total Order Broadcast）

5.1 问题：并发消息的顺序

因果广播解决了因果相关消息的顺序问题，但对并发消息不做排序。如果两个进程同时广播了两条没有因果关系的消息，不同接收方可能以不同顺序交付它们。

在状态机复制中，这是不可接受的。所有副本必须以完全相同的顺序执行所有操作——包括并发操作——才能保持状态一致。

p1: broadcast(m1: "x = x + 1")        （并发）
p2: broadcast(m2: "x = x * 2")        （并发）

初始状态: x = 1

p3 交付顺序 m1, m2: x = (1+1)*2 = 4
p4 交付顺序 m2, m1: x = (1*2)+1 = 3

结果：p3 认为 x=4，p4 认为 x=3 → 状态分叉

5.2 形式化定义

全序广播（Total Order Broadcast，TOB），也称原子广播（Atomic Broadcast），在可靠广播的基础上增加：

全序（Total Order）：如果任意两个正确的进程 pi 和 pj 都交付了消息 m1 和 m2，则 pi 和 pj 以相同的顺序交付 m1 和 m2。

这是最强的顺序保证：不仅因果相关的消息有序，并发消息也必须被所有进程以相同顺序交付。注意全序广播并不要求交付顺序与因果顺序一致（虽然实践中通常会同时满足）。如果需要同时满足因果和全序，则称为因果全序广播（Causal Total Order Broadcast）。

5.3 为什么全序广播如此困难

全序广播的困难之处在于：它要求所有正确进程对消息的交付顺序达成一致。而”对某个值达成一致”——这恰恰是共识（Consensus）问题的定义。

事实上，全序广播在计算能力上等价于共识。这意味着：

1. 全序广播不比共识更难解决——如果你能解决共识，就能实现全序广播
2. 全序广播不比共识更容易解决——如果你能实现全序广播，就能解决共识
3. FLP 不可能定理适用于全序广播——在异步系统中，没有确定性算法能在存在即使一个进程可能崩溃的情况下实现全序广播

这个等价性是分布式计算理论中最重要的结果之一。下一节将给出详细的证明。

六、全序广播与共识的等价性

这一节是本文的理论核心。我们将严格证明全序广播（Total Order Broadcast）和共识（Consensus）在计算能力上等价，即它们可以互相归约。

6.1 共识问题的回顾

首先回顾共识问题的定义。在共识问题中，每个进程提出一个值（propose），所有正确进程最终决定（decide）一个值，需要满足：

• 终止性（Termination）：每个正确的进程最终决定一个值
• 一致性（Agreement）：所有正确的进程决定相同的值
• 有效性（Validity）：决定的值是某个进程提出的值
• 完整性（Integrity）：每个进程最多决定一次

6.2 方向一：全序广播归约到共识（TOB → Consensus）

命题：如果有全序广播的实现，则可以用它解决共识问题。

构造：给定全序广播原语 TOB，构造共识算法如下：

class ConsensusFromTOB:
    """用全序广播解决共识"""

    def __init__(self, tob):
        self.tob = tob
        self.decided = False
        self.decision = None

    def propose(self, v):
        # 步骤 1：将提案值通过全序广播发送
        self.tob.broadcast(ProposalMessage(value=v))

    def on_tob_deliver(self, msg):
        # 步骤 2：第一条交付的提案消息决定共识值
        if not self.decided:
            self.decided = True
            self.decision = msg.value
            self.decide(msg.value)

正确性证明：

终止性：每个正确进程都会广播提案。由全序广播的有效性，至少一条提案消息会被所有正确进程交付。第一条被交付的提案消息触发 decide。因此每个正确进程最终决定。

一致性：全序广播保证所有正确进程以相同顺序交付所有消息。因此所有正确进程交付的第一条提案消息是相同的。由此所有正确进程决定相同的值。

有效性：决定的值是第一条被交付的提案消息中的值，而提案消息中的值是某个进程提出的值。

完整性：decided 标志保证每个进程最多决定一次。

这个归约简单到令人惊讶：全序广播直接就把最难的部分——让所有人对第一个值达成一致——解决了。

6.3 方向二：共识归约到全序广播（Consensus → TOB）

命题：如果有共识的实现，则可以用它构造全序广播。

这个方向更复杂。基本思路是：运行一系列共识实例（consensus instances），每个实例决定下一批要交付的消息。

构造：

class TOBFromConsensus:
    """用共识实现全序广播"""

    def __init__(self, rb, consensus_factory):
        self.rb = rb                         # 可靠广播（用于初始分发）
        self.consensus_factory = consensus_factory
        self.unordered = set()               # 已收到但未排序的消息
        self.delivered = set()               # 已交付的消息
        self.round = 0                       # 当前共识轮次
        self.decided_batches = {}            # round → 该轮决定的消息批次
        self.next_deliver_round = 1          # 下一个待交付的轮次

    def broadcast(self, m):
        self.rb.broadcast(m)

    def on_rb_deliver(self, m):
        if m.id not in self.delivered:
            self.unordered.add(m)
            self.try_start_consensus()

    def try_start_consensus(self):
        if not self.unordered:
            return

        self.round += 1
        current_round = self.round

        # 用当前未排序的消息集合作为提案
        proposal = frozenset(self.unordered)
        consensus = self.consensus_factory.create(current_round)

        def on_decide(decided_set):
            self.decided_batches[current_round] = decided_set
            self.deliver_decided()

        consensus.propose(proposal, callback=on_decide)

    def deliver_decided(self):
        while self.next_deliver_round in self.decided_batches:
            batch = self.decided_batches[self.next_deliver_round]
            # 在批次内用确定性排序（如消息 ID 排序）
            ordered = sorted(batch, key=lambda m: m.id)
            for m in ordered:
                if m.id not in self.delivered:
                    self.delivered.add(m.id)
                    self.unordered.discard(m)
                    self.deliver(m)
            self.next_deliver_round += 1
        # 如果还有未排序的消息，启动下一轮共识
        self.try_start_consensus()

正确性证明：

有效性：如果正确进程广播了 m，可靠广播保证所有正确进程最终收到 m 并放入 unordered 集合。当启动共识时，m 会被包含在某个提案中。由共识的终止性和有效性，某一轮的共识结果中会包含 m。因此 m 最终被交付。

一致性（Agreement）：如果某个正确进程交付了 m，说明某轮共识的决定包含了 m。由共识的一致性，所有参与该轮共识的正确进程决定相同的批次。由可靠广播的一致性和后续轮次的共识，所有正确进程最终也会交付 m。

全序：关键论证。所有正确进程按照相同的轮次序列交付消息（先交付第 1 轮决定的消息，再第 2 轮，依此类推）。在每一轮内，由共识的一致性，所有进程决定相同的消息集合。在集合内，使用确定性排序（如按消息 ID），所以集合内的顺序也相同。因此所有正确进程的交付顺序完全一致。

无重复：delivered 集合保证每条消息最多交付一次。

无凭空创造：只有通过可靠广播收到的消息才会被放入 unordered 集合，而可靠广播本身保证无凭空创造。

6.4 等价性的含义

两个方向的归约加在一起，证明了：

\[\text{Total Order Broadcast} \equiv \text{Consensus}\]

这个等价性有深远的理论和实践含义：

FLP 不可能定理适用：Fischer、Lynch 和 Paterson 在 1985 年证明：在异步系统中，即使只有一个进程可能崩溃，也不存在确定性算法能解决共识问题。由等价性，全序广播同样不可能在异步系统中被确定性地解决。这意味着所有实际的全序广播实现必须依赖某种形式的同步假设——超时、随机化或故障检测器。

共识算法可以直接用于广播：Paxos、Raft、PBFT 等共识算法本质上都在实现全序广播。Raft 的日志复制就是全序广播：Leader 决定日志条目的顺序，所有 Follower 按相同顺序应用。

广播层次与可解性边界：在五层广播抽象中，BEB、RB、FIFO 和因果广播都可以在异步系统中用确定性算法实现。全序广播是第一个碰到 FLP 不可能性壁垒的——它需要额外的假设才能实现。这个分界线恰好就在”不需要共识”和”需要共识”之间。

实践指导：如果你的系统只需要因果一致性，那么可以不用共识协议，用向量时钟就够了——系统可以是完全去中心化的、高可用的。但如果你需要全序——比如状态机复制——就不可避免地需要共识，也就不可避免地需要 Leader 选举或随机化，也就不可避免地在某些故障场景下牺牲可用性（CAP 定理的 C 与 A 的权衡）。

6.5 均匀全序广播

需要强调的一点是：上述证明中的全序广播指的是均匀全序广播（Uniform Total Order Broadcast），即全序属性对所有进程（包括崩溃进程）成立。非均匀版本虽然看起来更弱，但在崩溃-恢复模型中，证明等价性也成立。

Chandra 和 Toueg 在 1996 年的论文中进一步细化了这个结果，证明了在不同故障检测器类别下共识和全序广播的精确关系。他们证明了最弱的能解决共识的故障检测器是 \(\Omega\) 类——一个最终选出唯一 Leader 的检测器。

七、实现方案

全序广播等价于共识，因此所有全序广播的实现本质上都包含某种形式的共识机制。根据排序决策的方式，实现方案大致分为三类。

7.1 基于 Leader 的方案（单定序器）

最简单的全序广播实现是指定一个 Leader（定序器/sequencer）。所有消息先发给 Leader，Leader 为每条消息分配一个全局递增的序列号，然后将带序列号的消息广播给所有进程。

发送者 → Leader（定序器）→ 所有接收者
         分配序列号
         seq: 1, 2, 3, ...

class SequencerBasedTOB:
    """基于单定序器的全序广播"""

    def __init__(self, processes, leader, rb, my_id):
        self.processes = processes
        self.leader = leader
        self.rb = rb
        self.my_id = my_id
        self.global_seq = 0           # Leader 维护的全局序列号
        self.next_deliver_seq = 1     # 下一个待交付的序列号
        self.pending = {}             # seq → message

    def broadcast(self, m):
        # 所有进程将消息发给 Leader
        self.send_to_leader(m)

    def on_receive_at_leader(self, m):
        # Leader 分配序列号并可靠广播
        self.global_seq += 1
        ordered_msg = OrderedMessage(seq=self.global_seq, payload=m)
        self.rb.broadcast(ordered_msg)

    def on_rb_deliver(self, om):
        self.pending[om.seq] = om
        while self.next_deliver_seq in self.pending:
            msg = self.pending.pop(self.next_deliver_seq)
            self.next_deliver_seq += 1
            self.deliver(msg.payload)

优势：实现简单，延迟低（理想情况下 2 次网络跳转：发送者→Leader→接收者），吞吐量在 Leader 不是瓶颈时很高。

劣势：Leader 是单点故障和性能瓶颈。Leader 崩溃后需要重新选举，选举期间系统不可用。新 Leader 需要知道旧 Leader 分配的最后序列号，这本身又是一个共识问题。

7.2 基于共识的方案（Paxos/Raft）

更健壮的方案是对每批消息运行一次共识。这正是上一节证明中 Consensus → TOB 构造的具体化。

Raft 是这种方案的典型代表：

1. 客户端将请求发给 Leader
2. Leader 将请求追加到自己的日志
3. Leader 通过 AppendEntries RPC 将日志条目复制给 Followers
4. 当多数派确认后，Leader 提交该条目
5. Leader 通知 Followers 提交

每个日志条目的位置就是全局序列号。由于所有节点最终拥有相同的日志，这实现了全序广播。

与纯定序器方案的区别是：Raft 的 Leader 选举和日志复制是共识协议的一部分，Leader 崩溃后可以安全地选出新 Leader 并恢复。

Multi-Paxos 的做法类似：每个日志槽位（log slot）运行一个 Paxos 实例。Leader 优化使得正常情况下每个槽位只需要一轮通信（Phase 2），Leader 变更时需要完整的两轮 Paxos（Phase 1 + Phase 2）。

7.3 基于 Gossip 的方案（概率全序）

在大规模系统中（成百上千个节点），基于 Leader 的方案面临扩展性问题。基于 Gossip 的方案通过概率性方法实现近似全序。

典型做法是将全序与 Gossip 协议结合：

1. 每个节点将消息通过 Gossip 协议传播给所有节点
2. 每个节点在本地对收到的消息进行确定性排序（例如按消息哈希、时间戳等）
3. 当一条消息被认为已”稳定”（所有节点都已收到），按确定性排序交付

“稳定”判断是关键难题。严格的稳定性检测本身需要共识，因此纯 Gossip 方案通常只能提供概率性保证或在特定条件下的确定性保证。

7.4 方案对比

八、ISIS 与虚拟同步

8.1 历史背景

在讨论了广播抽象的理论框架之后，有必要回顾一个对这些理论产生深远影响的系统：ISIS。Kenneth Birman 和 Thomas Joseph 在 1987 年发表的论文”Reliable Communication in the Presence of Failures”提出了虚拟同步（Virtual Synchrony）模型，开创了群组通信（Group Communication）的研究方向。

ISIS 系统诞生的背景是 1980 年代的分布式系统实践需求：当时的分布式系统（金融交易系统、航空管制系统、工业控制系统）需要可靠的组播通信，但缺乏系统化的编程模型。Birman 的洞察是：如果将进程组织成”组”（group），在组成员变化（加入、离开、崩溃）时提供明确的语义，就能大大简化分布式编程。

8.2 虚拟同步模型

虚拟同步的核心思想可以概括为：所有组成员对”谁在组里”和”发生了什么消息”有一致的认知。具体来说：

视图（View）：系统的当前成员关系称为一个视图。视图由一个单调递增的编号和一个成员集合组成。当有成员加入、主动离开或被检测为崩溃时，系统安装一个新视图。

视图变更协议（View Change Protocol）：视图变更不是瞬间完成的——它是一个分布式协议。关键保证是：

1. 在同一个视图内广播的消息要么被该视图中所有正确成员交付，要么都不交付
2. 所有正确成员以相同的顺序经历视图变更
3. 视图变更充当”同步屏障”——在旧视图中的消息在视图变更之前交付完毕

Flush 协议：视图变更的实现依赖 Flush 协议。当检测到成员变化时：

1. 有进程检测到成员变化，发起视图变更
2. 所有成员停止发送新消息
3. 所有成员将已发送但未被所有人收到的消息重传（flush）
4. 所有成员确认 flush 完成
5. 安装新视图，恢复正常通信

状态转移（State Transfer）：当新成员加入时，需要从现有成员获取当前状态。虚拟同步保证状态转移和消息交付的一致性：新成员在安装视图后开始接收消息，而状态转移的快照对应于视图安装的精确时间点。

8.3 ISIS 的广播语义

ISIS 提供了多种广播原语，恰好对应本文讨论的层次：

• CBCAST：因果广播，使用向量时钟保证因果顺序
• ABCAST：全序广播（原子广播），所有成员以相同顺序接收
• GBCAST：用于视图变更的特殊广播，具有最强的顺序保证

Birman 最初声称 CBCAST 可以用于实现虚拟同步而不需要全序广播。这一声明引发了与 Cheriton 和 Skeen 的著名争论（1993 年）。Cheriton 和 Skeen 质疑虚拟同步的实用性，认为它的语义过于复杂且限制过多。Birman 和其合作者做出了回应，但这场争论暴露了虚拟同步模型在理论精确性方面的一些问题。

8.4 虚拟同步为何逐渐式微

尽管 ISIS 在学术界和工业界产生了重大影响，虚拟同步模型在 2000 年代后逐渐被更简单的 Paxos/Raft 风格方案取代。主要原因包括：

复杂性：视图变更协议的实现极其复杂。处理并发视图变更、网络分区、部分故障等情况需要大量边界条件处理。ISIS 的代码库超过 10 万行，维护难度极高。

扩展性：虚拟同步要求所有成员对视图达成一致，这在大规模系统中成为瓶颈。视图变更的延迟与成员数量线性相关（甚至更差），这限制了组的大小。

语义争议：虚拟同步的精确语义在不同的论文和实现中存在微妙差异。Friedman 和 van Renesse 在 1995 年的论文中提出了多种”虚拟同步”的变体，说明这个概念并非铁板一块。

替代方案：Lamport 的 Paxos（1998 年发表，1989 年提出）和后来的 Raft（2014 年）提供了更简单、更容易理解和实现的共识和全序广播方案。它们不需要显式的视图管理——成员变化通过共识本身处理（如 Raft 的配置变更协议）。

历史意义：尽管如此，ISIS 和虚拟同步对分布式系统的发展功不可没。它们奠定了群组通信的理论基础，向量时钟在因果广播中的应用、视图变更的概念、状态转移协议等都深刻影响了后续的分布式系统设计。JGroups（Java 实现的群组通信库）至今仍然使用虚拟同步模型。Spread Toolkit 和 Corosync 也受到了 ISIS 的直接影响。

九、工程实践中的广播

9.1 Kafka：分区内全序

Apache Kafka 的消息排序模型直接对应广播抽象的层次。

分区内全序：每个 Kafka 分区（partition）是一个有序的、不可变的消息序列。分区的 Leader 副本负责分配偏移量（offset），偏移量就是全局序列号。所有消费者以相同的偏移量顺序读取消息。这实现了单分区内的全序广播。

Partition 0:  [msg_0] [msg_1] [msg_2] [msg_3] [msg_4] ...
               offset=0  offset=1  offset=2  offset=3  offset=4

副本机制：每个分区有一个 Leader 和多个 Follower（ISR，In-Sync Replicas）。Producer 将消息发给 Leader，Leader 写入本地日志后将消息复制给 ISR 中的 Follower。当所有 ISR 确认后，消息被认为已提交（committed）。这对应均匀可靠广播——已提交的消息不会丢失，即使 Leader 崩溃。

跨分区无全序：Kafka 刻意不提供跨分区的全序。不同分区的 Leader 可能在不同的 Broker 上，它们之间没有协调。如果应用需要跨分区的顺序，必须在应用层自己处理（例如使用单分区，或在消费端进行归并排序）。

这是一个关键的工程权衡：

Producer 端的 FIFO：Kafka Producer 的幂等性（idempotence）和事务（transaction）机制保证了来自同一 Producer 到同一分区的消息按发送顺序写入——即 FIFO 广播。幂等 Producer 使用序列号（producer sequence number）实现去重和排序，与上文 FIFO 广播的序列号实现完全对应。

9.2 ZooKeeper 与 Zab 协议

ZooKeeper 使用 Zab（ZooKeeper Atomic Broadcast）协议实现全序广播。Zab 是专门为 ZooKeeper 设计的原子广播协议，与 Paxos 有相似之处但不完全相同。

Zab 的两个模式：

1. 恢复模式（Recovery）：Leader 选举和状态同步。当系统启动或 Leader 崩溃时进入此模式。
2. 广播模式（Broadcast）：正常运行。Leader 接收客户端写请求，分配单调递增的 zxid（ZooKeeper Transaction ID），将事务广播给 Followers。

zxid 的结构：zxid 是 64 位整数，高 32 位是 epoch（Leader 任期号），低 32 位是该 epoch 内的事务计数。这个设计保证了不同 Leader 任期的事务有全局唯一且可比较的标识。

zxid = (epoch, counter)
epoch: Leader 变更时递增
counter: 同一 Leader 任期内单调递增

例如：
Leader 1, 第 1 条事务: zxid = (1, 1)
Leader 1, 第 2 条事务: zxid = (1, 2)
Leader 崩溃，Leader 2 当选
Leader 2, 第 1 条事务: zxid = (2, 1)

广播流程：

1. 客户端发送写请求给 Leader
2. Leader 分配 zxid，创建事务提案（Proposal）
3. Leader 将 Proposal 发给所有 Followers
4. Followers 将 Proposal 写入本地事务日志，回复 ACK
5. Leader 收到多数派 ACK 后，发送 COMMIT
6. Leader 和 Followers 按 zxid 顺序应用事务

Zab 与 Raft 的关键区别在于恢复机制。Zab 的恢复需要保证两个属性：

• 已提交的事务不丢失：如果事务 T 在旧 Leader 崩溃前已提交，新 Leader 必须包含 T
• 被跳过的事务不出现：如果旧 Leader 提出了事务 T 但未提交就崩溃了，T 不能在新 Leader 上被提交

这两个属性共同保证了全序广播的安全性。

9.3 etcd 与 Raft

etcd 使用 Raft 协议实现全序广播和线性一致性读。

写操作：客户端的写请求被 Raft Leader 转化为日志条目，通过 Raft 共识复制到多数派后提交并应用到状态机。所有节点按相同顺序应用日志条目——全序广播。

线性一致性读：etcd 的读操作也通过广播机制保证线性一致性。有两种实现方式：

1. ReadIndex：Leader 记录当前 commit index，向多数派发送心跳确认自己仍是 Leader，然后等待状态机应用到该 index 后返回读结果。这确保读操作看到的是最新已提交的数据。

2. LeaseRead：Leader 在心跳超时时间内假设自己仍是 Leader（因为选举超时大于心跳超时），直接从本地状态机读取。性能更高但在时钟漂移时可能违反线性一致性。

ReadIndex 流程：
1. 客户端发起读请求
2. Leader 记录当前 commitIndex = X
3. Leader 发送心跳，确认多数派响应
4. Leader 等待 applyIndex >= X
5. 从状态机读取并返回

9.4 广播语义在不同系统中的映射

下表总结了本文讨论的广播抽象与实际系统的对应关系：

这些系统的共同点是：它们都在某个范围内（全局或分区/Range）实现了全序广播，然后在全序广播之上构建更高级的抽象（状态机复制、线性一致性 KV 存储等）。

9.5 工程权衡

在工程实践中选择广播语义时，关键考虑因素包括：

全序的范围：全局全序提供最强的保证但限制了扩展性；分区全序（如 Kafka）通过缩小全序范围换取吞吐量。CockroachDB 的 Multi-Raft 进一步将全序范围缩小到单个 Range（默认 512MB），实现了近乎线性的水平扩展。

一致性与可用性：全序广播需要共识，共识在网络分区时需要牺牲可用性（CAP 定理的 CP 选择）。如果应用可以容忍因果一致性，使用因果广播（如 CRDT + 向量时钟）可以在分区期间保持可用。

延迟预算：共识协议的延迟下界是一个网络往返（Leader 到多数派）。在跨数据中心部署中，这可能是几十到几百毫秒。如果延迟敏感，可以考虑：将全序范围缩小、使用 LeaseRead 优化读延迟、或在可能时使用更弱的一致性语义。

消息批处理：所有实际系统都对广播消息进行批处理（batching）以均摊共识的开销。Kafka 的 linger.ms 参数控制 Producer 的批处理窗口；Raft 实现通常在一个 AppendEntries RPC 中包含多个日志条目。批处理是将全序广播的理论 O(n) 消息复杂度转化为实际高吞吐量的关键工程技巧。

十、总结

本文从最弱的尽力广播到最强的全序广播，系统地梳理了分布式系统中五层广播抽象的形式化定义、实现算法和工程实践。

核心结论：

1. 广播抽象形成严格的层次结构：BEB ⊂ RB ⊂ FIFO ⊂ Causal ⊂ TOB。每一层在下层基础上增加一个关键属性，对应更强的语义保证和更高的实现代价。

2. 全序广播与共识在计算能力上严格等价。这意味着全序广播受 FLP 不可能定理约束——在纯异步系统中没有确定性解。所有实际实现都依赖超时、Leader 选举或随机化来规避这一不可能性。

3. 因果广播是最后一个可以在纯异步系统中用确定性算法实现的广播抽象。从因果到全序的跨越需要共识——这是分布式计算中一个根本性的复杂度跳变。

4. 工程实践中，系统设计者通过限定全序的范围（分区、Range）来在一致性和扩展性之间取得平衡。Kafka 的分区模型、CockroachDB 的 Multi-Raft 都是这一策略的体现。

5. ISIS 和虚拟同步虽然在历史上逐渐式微，但它们提出的群组通信模型、视图变更协议和因果广播算法至今仍深刻影响着分布式系统的设计。

选择哪一层广播抽象，取决于应用对一致性的需求和对性能的容忍度。没有通用的最优解——只有在具体约束下的正确权衡。

参考文献

1. Hadzilacos, V., & Toueg, S. (1994). A Modular Approach to Fault-Tolerant Broadcasts and Related Problems. Technical Report, Cornell University. https://www.cs.cornell.edu/fbs/publications/HaijTou94.pdf
2. Birman, K., & Joseph, T. (1987). Reliable Communication in the Presence of Failures. ACM Transactions on Computer Systems, 5(1), 47-76.
3. Cachin, C., Guerraoui, R., & Rodrigues, L. (2011). Introduction to Reliable and Secure Distributed Programming (2nd ed.). Springer.
4. Défago, X., Schiper, A., & Urbán, P. (2004). Total Order Broadcast and Multicast Algorithms: Taxonomy and Survey. ACM Computing Surveys, 36(4), 372-421.
5. Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM, 32(2), 374-382.
6. Chandra, T. D., & Toueg, S. (1996). Unreliable Failure Detectors for Reliable Distributed Systems. Journal of the ACM, 43(2), 225-267.
7. Lamport, L. (1978). Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM, 21(7), 558-565.
8. Junqueira, F. P., Reed, B. C., & Serafini, M. (2011). Zab: High-performance Broadcast for Primary-backup Systems. In Proceedings of the 2011 IEEE/IFIP International Conference on Dependable Systems & Networks (DSN).
9. Ongaro, D., & Ousterhout, J. (2014). In Search of an Understandable Consensus Algorithm. In Proceedings of USENIX ATC. https://raft.github.io/raft.pdf

上一篇：Gossip 协议 | 下一篇：新硬件对分布式系统的冲击