Total order broadcast

Definition

总秩序广播（total order broadcast），有时也被称为原子广播（atomic broadcast）。FIFO broadcast 和 Causal broadcast 允许不同的节点以不同的顺序传递信息，total order broadcast 在各节点之间强制执行一致性，确保所有节点以相同的顺序传递信息。精确的传递顺序没有规定，只要它在所有节点上都是一样的。

所有三个节点都按照 \(m_{1}\), \(m_{2}\), \(m_{3}\) 的顺序传递消息

所有三个节点都按照 \(m_{1}\), \(m_{3}\), \(m_{2}\) 的顺序传递信息。只要节点同意，这两种执行方式都是有效的。

与 Causal broadcast 一样，节点可能需要保留消息，等待其他需要首先传递的消息。例如，节点 \(C\) 可以按任一顺序接收消息 \(m_{2}\) 和 \(m_{3}\)。如果算法确定 \(m_{3}\) 应该在 \(m_{2}\) 之前传递，但如果节点 \(C\) 首先收到 \(m_{2}\)，那么 \(C\) 将需要保留 \(m_{2}\)，直到收到 \(m_{3}\) 之后。

在这些图上可以看到另一个重要的细节：在 FIFO broadcast 和 Causal broadcast 的情况下，当一个节点广播一个消息时，它可以立即将该消息传递给自己，而不必等待与任何其他节点的通信。这在全序广播中不再是这样：例如，在 图_{total-order-broadcast-1} 上，\(m_{2}\) 需要在 \(m_{3}\) 之前被传递，所以节点 \(A\) 向自己传递 \(m_{3}\) 必须等到 \(A\) 从 \(B\) 那里收到 \(m_{2}\) 之后。

最后，FIFO-total order broadcast 和 total order broadcast 很像，多了一个先进先出的要求，即同一节点广播的任何消息都按其发送的顺序交付。实际上图_{total-order-broadcast-1} 和图_{total-order-broadcast-2} 的例子就是有效的 FIFO-total order broadcast，因为 \(m_{1}\) 都是在 \(m_{3}\) 之前被传递的。

Total order broadcast algorithms

Single leader approach:

• 指定一个节点为 leader
• 想要广播消息，将其发送给 leader，leader 再将其通过 FIFO broadcast 广播给其他节点。
• Problem: leader 崩溃 \(\Longrightarrow\) 没有消息被传递
• 安全地更换 leader 很困难

Lamport clocks approach:

• 每条消息附带上 lamport 时间戳
• 按照时间戳的总顺序传递消息
• Problem: 无法知道是否收到了所有时间戳小于 \(T\)¹ 的消息，需要在缓存中缓存来自每个节点时间戳大于等于 \(T\) 的消息。

上述两个方法，都不具有容错性。单个节点崩溃以及 leader 节点崩溃都会使得其他节点无法传递消息。

---