Causal broadcast

Definition

Causal broadcast 算法有点类似于 FIFO broadcast：

每条被广播的消息附上的不是一个序列号，而是一个整数的向量。这种算法有时被称为向量时钟算法，向量时钟算法中，向量元素计算每个节点发生的事件数量，而在 causal broadcast 算法中，向量元素计算来自每个发送者的已发送的消息数量。

如果节点 $C$ 在 $m_{1}$ 之前收到 $m_{2}$，$C$ 的广播算法将不得不保留（延迟或缓冲）$m_{2}$，直到 $m_{1}$ 被传递之后，以确保消息按因果顺序传递​。在下图的例子中，消息 $m_{2}$ 和 $m_{3}$ 是​同时广播​的。节点 $A$ 和 $C$ 按照 $m_{1}$、$m_{3}$、$m_{2}$ 的顺序传递消息，而节点 $B$ 按照 $m_{1}$、$m_{2}$、$m₃$的顺序传递。这些传递顺序中的任何一个都是可以接受的，因为它们都与因果关系一致。

有因果关系的信息必须按因果顺序传递。并行的消息可以按照任何顺序传递。

上图：broadcast($m_{1}$) $\longrightarrow$ broadcast($m_{2}$) and broadcast($m_{1}$) $\longrightarrow$ broadcast($m_{2}$) and broadcast($m_{1}$) broadcast($m_{3}$) $\Longrightarrow$ valid orders are: ($m_{1}$, $m_{2}$, $m_{3}$) or ($m_{1}$, $m_{3}$, $m_{2}$)

Causal broadcast algorithm

每个节点的本地状态由 $sendSeq$、$delivered$ 和 $buffer$ 组成，它们的含义与 FIFO broadcast 算法中相同。当一个节点想要广播一个消息时，我们会附上发送节点的编号 $i$ 和 $deps$（表示该消息因果关系的向量）。$deps$ 就是节点本地 $delivered$ 的复制，统计了每个节点发送消息并传递到该节点的数量。在这次广播之前，所有已经在本地交付的消息必须出现在广播消息的因果顺序之前。然后将发送节点自己的这个向量的元素更新为等于 $sendSeq$，这就​保证了这个节点所广播的每条消息都与同一节点所广播的前一条消息有因果关系​。

当收到一个消息时，算法首先将其添加到 $buffer$ 中，就像 FIFO broadcast 一样，然后在 $buffer$ 中搜索任何准备好的消息。比较 $deps \leq delivered$。如果这个节点已经交付了所有在因果顺序上必须在这个消息之前的消息，那么，任何在因果关系上准备好的消息都会被传递给 Application，并从 $buffer$ 中移除，并且将 $delivered$ 中的相应条目被递增。

Summary

Causal broadcast 的保持因果顺序的原理和 Vector clocks 很相似，向量中的每个条目，前者是消息发送者已发送消息的数量，后者是每个节点发生事件的数量。deps 取代 FIFO broadcast 中的 sendSeq 附带在广播的信息中，这样通过在 Vector clocks 中介绍的向量比较方法，可以确定消息之间的因果关系来控制消息传递的顺序。