本章我们将研究 Broadcast protocols广播协议（也称为multicast protocols 组播协议），即向多个接收者传递同一条信息的算法。正如我们将在第5讲中看到的那样，这些协议可以用来构成更高级分布式算法。在实践中，几种不同的广播协议都有采用，它们的主要区别在于传递消息的顺序order。正如我们在上一讲中看到的，顺序的概念与时钟和时间密切相关。因此，我们将在本章开始时，更深入地研究时钟如何帮助我们跟踪分布式系统中的顺序。
4.1 逻辑时间
之前我们看到来自物理时钟的时间戳可能与因果关系不一致，即使这些时钟是经过类似NTP的协议同步。也就是说，如果用send(m)表示发送消息m的事件，用send(m1)→send(m2) 表示 happen-before关系，那么可能发生send(m1)的物理时间戳（根据m1发送者的时钟）小于send(m2)的物理时间戳（根据m2发送者的时钟）。
相比之下，logical clocks 逻辑时钟的重点是正确捕捉分布式系统中的事件顺序。我们要研究的第一种逻辑时钟是Lamport时钟，由Lamport[1978]在分布式计算论文中引入。
Lamport时间戳本质上是一个用来计算已发生事件数量的整数。因此，它与物理时间没有直接关系。在每个节点上，时间都会增加，因为每个事件的计数会递增。该算法假设了一个crash-stop崩溃-停止模型（如果时间戳被保持在稳定的存储中，比如磁盘上，则等价于crash-recovery崩溃-恢复模型）。
Lamport 时钟：
- 每个节点都有一个计数器
t，在每个本地事件e发生时递增 - 设
L(e)为该增量后的t值 - 在通过网络发送的信息中附加当前
t - 收件人将其时钟向前移动到消息中的时间戳（如果大于本地计数器），然后增加
Lamport 时钟的属性：
- 如果
a → b，那么L(a) < L(b) - 然而，
L(a) < L(b)并不意味着a → b - 当
a ≠ b时，可能存在L(a) = L(b)
当传递网络消息时，发送者将其当前的Lamport时间戳附加到该消息上。在上面的例子中，t = 2被附加到m1，t = 4被附加到m2。当收件人收到消息时，它将其本地Lamport时钟增加到消息中的时间戳加1；如果收件人的时钟已经领先于消息中的时间戳，就只进行递增。
Lamport时间戳的特性是，如果a发生在b之前，那么b的时间戳总是比a大；换句话说，时间戳与因果关系一致。然而，反过来说是不成立的：一般来说，如果b的时间戳比a大，我们知道b⇏a，但我们不知道是a→b还是a‖b（并发）的情况。
两个不同的事件也有可能具有相同的时间戳。在上面的例子中，节点A上的第三个事件和节点B上的第一个事件的时间戳都是3。如果我们需要每个事件都有一个唯一的时间戳，可以用该节点的名称或ID来扩展时间戳。在单个节点的范围内，每个事件都被分配一个唯一的时间戳；因此，假设每个节点都有一个唯一的名字，时间戳和节点名的组合就是全局唯一的（在所有节点上）。
happens-before关系 是一个偏序。使用Lamport的时间戳，我们可以将这个partial order 偏序扩展为total order 全序。我们在（时间戳，节点名）上使用字典序：也就是说，我们首先比较时间戳，如果它们相同，我们通过比较节点名称来打破平局。
全序关系≺将所有的事件归入一个线性顺序：对于任何两个事件a≠b，我们有a≺b或b≺a。这是一个因果顺序：只要a→b我们就有a≺b。也就是说，≺是偏序→的linear extension线性扩展。然而，如果a‖b（并发），我们可以有a≺b或b≺a，所以这两个事件的顺序是由算法任意决定的。
给定两个事件的Lamport时间戳，一般来说，我们不可能知道这些事件是否同时发生，或者一个事件是否发生在另一个之前。如果我们确实想检测事件是否同时发生，我们需要一种不同类型的逻辑时间：vector clock向量时钟。
Lamport的时间戳只是一个单一的整数（可能附有一个节点名），而向量时间戳是一个整数的列表，系统中的每个节点都占一位。按照惯例，如果我们把n个节点放入一个向量(N_1, N_2, ..., N_n)，那么一个向量时间戳就是一个类似的向量(t_1, t_2, ..., t_n) 其中t_i对应于节点N_i。具体来说，t_i是在节点N_i发生的已知事件的数量。在一个向量T=(t_1, t_2, ..., t_n)中，我们通过T[i]获取元素t_i，如同一个数组的索引。
除了标量和向量的区别外，向量时钟算法与Lamport时钟非常相似。一个节点初始化它的向量时钟，为一个零向量。每当节点N_i发生事件时，它就会增加向量钟中的第i个条目（它自己的条目）。(在实践中，这个向量通常被实现为一个从节点ID到整数的map，而不是一个整数数组）。当一个消息在网络上发送时，发送者当前的向量时间戳被附加到该消息上。最后，当一个消息被接收时，接收者将消息中的向量时间戳与它的本地时间戳合并，取两个向量的元素的最大值，然后接收者增加它自己的条目。
请注意，当C收到来自B的消息m2时，A的向量条目也被更新为2，因为当前事件与发生在A的两个事件有间接的因果关系。这样一来，向量时间戳就反映了happens-before关系的传递性。
我们在向量时间戳上定义一个偏序。
- 如果一个向量的每个元素都小于或等于另一个向量的相应元素，那么这个向量小于或等于另一个向量。
- 如果一个向量小于或等于另一个向量，并且至少在一个元素中存在差异，那么这个向量就严格小于另一个向量。
- 如果一个向量相比另一个向量，在一个元素的值较大，而另一个元素的值较小，那么两个向量是不可比的。
例如，T_1=(2,2,0)和T_2=(0,0,1)是不可比的，因为T_1[1]>T_2[1]但T_1[3]<T_2[3]。
向量时间戳的偏序与happens-before关系所定义的偏序完全对应。因此，矢量时钟算法提供了一种在实践中计算happens-before关系的机制。
我们已经看到了两种关键算法：Lamport时钟和矢量时钟，一个提供全序，另一个描述happens-before的偏序。当然也存在其他各种构造：例如，有一些混合时钟，结合了逻辑时钟和物理时钟的一些特性[Kulkarni et al.，2014]。
4.2 Delivery order in broadcast protocols
许多网络提供点对点（单播）的信息传递，即每个信息有一个指定的收件人。现在我们来看看broadcast protocols 广播协议，它对网络层通信进行了推广，使一条消息被发送到某个组的所有节点。组的成员可能是固定的，但系统也可能为节点提供加入和离开组的机制。如果一个节点出现故障，其余的节点可以继续收发消息。
一些局域网在硬件层面上提供组播或广播（例如，IP组播），但互联网上的通信通常只允许单播。此外，硬件组播通常是在best-effort尽力而为的基础上提供的，这允许消息被丢弃；为了要使消息传递可靠，需要使用这里讨论的重传协议。
之前第2章关于节点行为和同步性的系统模型假设依然适用于广播组：
- 网络可以是best-effort尽力而为（可能会丢包）或者reliable可靠（非故障节点可以通过重传信息，保证每条信息的传递）
- 异步/部分同步的时间模型→信息延迟没有上限
在我们讨论细节之前，我们应该澄清一些术语（broadcast，send，receive，deliver）。当一个应用程序想向一个组发送消息时，它使用一种算法来broadcast 广播。然后，广播算法通过点对点链接向其他节点sends发送消息，而另一个节点在消息抵达时receives接收。最后，广播算法可能将消息deliver递交给应用程序。在receive收到消息和deliver递交消息之间会有延迟。
我们来研究三种不同形式的广播。所有这些都是reliable可靠的：每个消息最终都会被传递到每个非故障节点，没有时间保证。然而，它们在每个节点上传递信息的顺序方面有所不同。事实证明，这种顺序上的差异对实现广播的算法有非常根本的影响。
最弱的广播类型称为FIFO broadcast先进先出广播，它与先进先出（FIFO）链接密切相关。在这个模型中，由同一节点发送的消息按其发送的顺序传递。例如，m1必须在m3之前被deliver递交，因为它们都是由A发送的。然而，m2可以在m1和m3之前、之间或之后的任何时间被递交。
另一个细节是：每当一个节点广播一个消息时，它也会将该消息传递给自己（在图上表示为一个回环箭头）。这一点乍看没有必要，（毕竟节点知道它自己广播了哪些消息，）但在这全序广播中是需要的。
图上的执行示例是有效的FIFO先进先出广播，但它违反了因果性：B在m1递交之后广播m2，但是节点C在递交m2之后才递交m1。Causal broadcast 因果广播提供了一个比先进先出广播更严格的排序属性。顾名思义，它确保消息按因果顺序传递：也就是说，如果一条消息的广播发生在另一条消息的广播之前，那么所有节点必须按这个顺序传递这两条消息。如果两个消息是同时广播的，一个节点可以按任何一个顺序传递它们。
在前一个例子中，如果节点C在m1之前收到m2，C的广播算法必须hold back扣留（delay延迟或buffer缓冲）m2，直到m1先被递交，以确保消息按因果顺序传递。在当前例子中，消息m2和m3是并发广播的。节点A和C按照m1, m3, m2的顺序传递消息，而节点B按照m1, m2, m3的顺序传递。这些传递顺序中的任何一个都是可以的，因为它们都与因果关系一致。
第三种类型的广播是total order broadcast 全序广播，有时也被称为atomic broadcast 原子广播。先进先出和因果广播允许不同的节点以不同的顺序传递消息，而全序广播则在各节点之间强制执行一致性，确保所有节点以相同的顺序传递消息。精确的传递顺序没有定义，只要它在所有节点上是相同的。
这里显示了两个全序广播的执行实例。在图1中，所有三个节点都按m1, m2, m3的顺序传递信息，而在图2中，所有三个节点都按m1, m3, m2的顺序传递信息。只要节点同意，这两种执行方式中的任何一种都是有效的。
与因果广播一样，节点可能需要扣留消息，等待其他需要先递交的消息。例如，节点C可以按任一顺序收到消息m2和m3。如果算法确定m3应该在m2之前递交，但如果节点C先收到m2，那么需要保留m2直到收到m3。
在这些图上可以看到另一个重要的细节：在先进先出和因果广播的情况下，当一个节点广播一个消息时，它可以立即将该消息传递给自己，而不必等待与任何其他节点的通信。这在全序广播中是不成立的：例如，在图1上，m2需要在m3之前递交，所以节点A必须等到A从B收到m2之后再向自己递交m3。同样，在图2上，节点B向自己递交m2必须等待m3先递交。
最后，FIFO-total order broadcast 先进先出-全序广播就像全序广播一样，但有一个额外的先进先出的要求，即同一节点广播的任何消息都按其发送的顺序递交。图1&2上的例子实际上是有效的先进先出-全序广播，因为在这两个例子中，m1都在m3之前被递交。
我们可以把这些不同的广播协议排列成一个层次结构。例如，先进先出-全序广播是比因果广播更严格的模型；换句话说，每个有效的先进先出-全序广播协议都满足因果广播协议。
4.3 广播算法
现在我们看看实现广播算法。大致上要分两步：第一，确保每个节点都能收到每个消息；第二，以正确的顺序递交这些消息。我们将首先看一下可靠地传播消息。
我们可以尝试的第一个算法是：当一个节点想要广播一个消息时，它通过reliable links可靠链接（即重传丢包）单独向其他每个节点发送该消息。然而，可能发生的情况是，一条消息被丢弃，而发送者在重传之前就崩溃了。在这种情况下，其中某些节点将永远不会收到该消息。
为了提高可靠性，我们可以争取其他节点的帮助。例如，当一个节点第一次收到某个特定的消息，它就把它转发给其他每个节点（这被称为eager reliable broadcast 急性可靠广播）。这种算法确保了即使一些节点崩溃，所有剩下的（非故障）节点都会收到每条消息。然而，这种算法是相当低效的：在没有故障的情况下，每条消息在一个由n个节点组成的小组中要发送O(n^2)次，因为每个节点将收到每条消息n-1次。这意味着它使用了大量的冗余网络流量。
这种算法的许多变种沿着不同的维度进行优化，如容错性，所有节点收到信息的耗时，占用的网络带宽。一个特别常见的广播算法系列是Gossip协议（也被称为epidemic protocols流行病协议）。在这些协议中，一个希望广播信息的节点将其发送给随机选择的少量特定节点。在第一次收到信息时，节点将其转发给固定数量的随机选择的节点。这类似于八卦、谣言或传染病在人群中传播的方式。
Gossip协议并不严格保证所有节点都能收到信息：在随机选择节点时，有可能总是遗漏一些节点。然而，如果算法的参数选择得当，信息遗漏的概率就会非常小。Gossip协议之所以吸引人，是因为在正确的参数下，它们对信息丢失和节点崩溃有很强的适应性，同时也能保持高效。
现在我们有了可靠的广播（急性可靠广播或Gossip协议），我们可以在此基础上建立FIFO先进先出、causal因果或total order全序广播。让我们从先进先出（FIFO）广播开始。
节点N_i发送的每个FIFO广播消息都被标上节点编号i和一个序列号（从0计数）。每个节点的本地状态由序列号sendSeq（计数该节点广播的消息数量）、delivered（每个节点每个条目的向量，计数该节点已经递交的来自每个发件人的消息数量）和buffer（用于保留消息直到它们准备交付的缓冲区）组成。该算法检查来自任何发件人的与预期的下一个序列号相匹配的消息，然后增加该数字，确保来自每个特定发件人的消息按照序列号增加的顺序被传递。
因果广播算法与先进先出（FIFO）广播有些类似；但不是给每个广播的消息附上一个序列号，而是附上一个整数向量。这种算法有时被称为vector clock向量时钟算法。在因果广播算法中，向量元素计算每个发送者已经发送的消息数量。
每个节点的本地状态由sendSeq、delivered和buffer组成，它们的含义与FIFO广播算法中相同。当一个节点想要广播一个消息时，我们会附上发送节点的编号i和deps（deps向量表示该消息的causal dependencies 因果关系）。算法通过复制delivered来构建deps（delivered向量用于计算每个发送方有多少消息在这个节点被递交）。这种机制表明，之前已经递交的消息，在因果顺序上必须出本条广播消息之前。然后，将发送方节点在向量中的元素更新为sendSeq，这就确保了这个节点广播的每个消息都与同一节点广播的前一个消息有因果关系。
当收到一个消息时，算法首先将其添加到buffer缓冲区，就像FIFO广播中一样。然后在缓冲区中搜索任何准备递交的消息。比较deps≤delivered使用的是之前定义的向量运算符≤。如果这个节点已经递交了在因果顺序上必须在这个消息之前的所有消息，这个比较就是成立的。任何因果上预备好的消息都会被递交给应用程序并从缓冲区中移除，并且delivered向量的相应元素被递增。
最后，全序广播（和FIFO-全序广播）是比较棘手的。这里简单概述了两种方法:
单一领导：基于指定的领导节点
- 一个节点被指定为领导者leader（序号生成器 sequencer）
- 为了广播信息，先将消息发送给领导者；领导者通过FIFO先进先出的广播方式进行广播
- 问题：领导者崩溃 ⇒没有信息可以传递
- 不太可能安全地改变领导者
Lamport时钟：使用Lamport时间戳的无领导算法
- 将Lamport的时间戳附在每条消息上
- 按时间戳的全序递交信息
- 问题：你怎么知道你已经获得了所有时间戳<T的消息？需要使用FIFO链接并等待来自每个节点的时间戳≥T的消息
然而，这两种方法都不具有容错性：在这两种情况下，单个节点的崩溃会使所有其他节点无法传递信息。在单领导方法中，领导本身就是单点故障点。我们将在第6章中再次讨论容错全序广播问题。
