Bracha's Reliable Broadcast

1987 年，Gabriel Bracha 在论文 Asynchronous Byzantine agreement protocols 中提出分布式网络中的一种“Byzantine Fault Tolerance（BFT）”算法，我们把它称为 Bracha's Reliable Broadcast。注：这个算法其实在 1984 年，Gabriel Bracha 在论文 An Asynchronous [(n-1)/3]-Resilient Consensus Protocols 中就提出了。

在一个节点数为 $n$ 的分布式系统中，某节点（发消息的节点记为节点 $p$ ）向其它节点发布广播消息，比如消息内容是设置某个变量 v 的值，需要其它节点接受。对于这个问题， 采用 Bracha's Reliable Broadcast 算法，可以保证当恶意节点数 $t<n/3$ 时，下面两个结论会满足：

1. 如果 $p$ 是正常节点，则所有正常节点都会接受这个值。
   
2. 如果 $p$ 是恶意节点，则所有正常节点都或者接受一个相同的值，或者不接受任何值。
   

下面介绍 Bracha's Reliable Broadcast 协议。

假设所有的通信消息都有一个编号，比如第 $k$ 次广播中，每个消息都会带上编号 $k$ ，这样我们不用考虑不同次广播的消息会相互影响的情况，后面的介绍会省略这个 $k$ 。

这个协议中使用了 3 种类型的消息：initial/echo/ready：

1. 消息 (initial, v) 表示节点 $p$ 想通过广播来设置变量 v 的值；
   
2. 消息 (echo, v) 表示某节点向所有其它节点广播，我收到了 initial 消息；
   
3. 消息 (ready, v) 表示某节点向所有其它节点广播，我准备好了。
   

Bracha's Reliable Broadcast 协议如图 1 所示。

有一些实现把图 1 中的 step1 作了一些简化，仅当收到 (initial, v) 消息后才会广播 (echo, v)，如图 2（摘自 State Machine Replication with Byzantine Faults）所示。

图 3（摘自：https://youtu.be/u0nypF5AIF4?t=710 ）形象地展示了消息的发送过程。