概述
本文将介绍什么是广播、为什么有广播、广播有哪些分类、如何实现广播，广播有哪些应用。
为什么要有广播？
构建分布式的难点在于不可避免的并发以及提供全局控制，这可以通过group communication来降低难度。相比点对点通信，group communication原语提供了更高的保证。
broadcast protocols 广播协议将消息发送给组内全部节点。组内成员可以是固定的，也可以加入或离开。
broadcast 是一个 group communication ，total order broadcast是一种broadcast。
当应用给组内全部节点发送消息时，可以使用一种算法去broadcast。
broadcast和delivery理解
broadcast和delivery 是更高维度的概念。send/receive是点对点的维度。
广播的分类
total order broadcast protocol 要满足下面四个属性：
- validity (正确性)：如果一个正确的进程广播了一条消息，那么其他所有正确的进程都接收到这条消息
- uniform agreement: 如果一个进程接收到消息m，那么所有正确的进程都接收到消息m
- uniform integrity: 一个进程最多接收一次消息m
- uniform total order: 如果进程p和q都接收到消息m和m’，当且仅当q接收消息m早于m’时，进程p接收消息m早于m’
满足前三个属性的叫reliable broadcast。简要概括可靠广播：没有时间保证，所有消息都被没有错误的节点接收。
根据节点接收消息的顺序不同，可以得到几种广播：FIFO、causal、Total order Broadcast。
FIFO 广播
定义：如果同一个节点发送的消息m1和m2，m1早于m2，那么接收上m1要早于m2。
如下图黑线所示。但可能出现节点C接收m2早于m1，那么符合FIFO（m1早于m3)，但不符合因果（因为节点B是接收m1后才广播m2）。
Causal 广播
定义：如果一个消息的广播 happens before 另外一个消息，那么所有节点的接收顺序也要保持这个顺序；如果两个消息并发，那么一个节点可以以任意接收。
如下图所示 broadcast(m1) -> broadcast(m2) 并且 broadcast(m1) -> broadcast(m3)，那么有效的顺序是:
(m1,m2,m3) 或 （m1,m3,m2)
Total Order 广播，又叫atomic broadcast 原子广播
定义：保证节点的一致性，确保所有节点以相同顺序接收消息。
广播算法
广播算法可以分成两步骤：
- 尽最大努力可靠的广播，通过重发丢失的消息
- 基于可靠广播，保证接收顺序
可靠广播
尝试1：广播节点直接给其他节点发送消息
当消息丢失 并且 发送节点崩溃时，将会有节点无法收到该消息。
为了改善这种情况，我们需要依赖其他节点的帮助。已经收到消息的节点，可以将其全部消息广播给其他节点。但是该算法并不高效：没有错误时，每个消息要发送O(n^2)次，每个节点至少收到n-1次消息。
有很多算法可以进行优化。比如 Broadcast Protocols for Distributed Systems中的trans protocol
。当然最有名的是 gossip protocols。
基于可靠广播（使用eager reliable broadcast or gossip protocol），我们可以构建FIFO,causal,total order 广播。
FIFO broadcast algo
sendSeq 是发送节点自增的序号；delivered：一个发送节点是一个向量，记录接收节点已经接收的发送节点的数据。buffer：记录收到的节点，直到能够被delivere。
算法核心：对于每个发送，检查是否有预期seq匹配的，如果有则deliver m 给application；反之则等待消息接收。
Causal broadcast algo
Total broadcast algo
采用共识算法