伯明翰·施皮尔·斯蒂芬森协议

该算法用于保持消息的因果关系顺序，即先发送的消息应该先被接收。如果执行 send(M1) -> send(M2)，那么所有接收到消息 M1 和 M2 的进程，应该先接收 M1，然后再接收 M2。特点/特征：

• 基于广播的消息传递方式。
• 这些消息的大小都很小。
• 发送的消息数量更多了。
• 有限的公开信息。

要点：

• 在发送消息时，每个进程都会将其向量时钟增加1。
• 如果某个进程已经接收了它之前的所有消息，那么该消息就会被传递给该进程。
• 否则，就先暂存这条消息吧。
• 更新该进程的向量时钟。

参考：

• 过程：Pi
• 事件：eij，其中i表示进程编号，j表示第i个进程中的第j个事件。
• Tm：消息m的向量时间戳。
• 与进程Pi相关的向量时钟；第j个元素即为Ci[j]，它包含了在时刻t时，进程Pj所拥有的Pi的最新值。

协议/规范： Pi正在向Pj发送消息——

• Pi会增加Ci[i)的值，同时设置时间戳tm为Ci[i)。这样，对于消息m来说，其时间戳就为Ci[i)。

Pj收到了来自Pi的消息。

• 当 Pj 满足 j!= i 的条件时，如果消息的时间戳为 tm，那么消息的传递将被延迟，直到这两个条件都得到满足之后才会进行传递。

Cj[i] = tm[i] - 1; and
for all k <= n and k != i, Cj[k] >= tm[k].

• 当消息被传递给Pj时，需要更新Pj的向量时钟。
• 检查缓冲区，看看是否有数据可以传输。

示例 –

• 所有进程的初始状态都是 000。
• M1的信号是从P3传输到P1和P2的。e31会更新向量时钟为(001)，然后向P1和P2发送信号。
• P2接受了带有时间戳(001)的M1消息。因为当P2将其与初始的时间戳(000)进行比较时，发现M1正是它接收到的第一条消息。
• 现在，我们假设在M1到达P1之前，P2先向P1和P3发送了带有时间戳(011)的M2。
• P1无法接受M2，因为当比较M2的时间戳与其初始时间戳时，发现存在差异。因为P1没有时间标记为“001”的消息被接收过，所以M2被存储在缓冲区中。
• 现在，M1被P1接收并接受了。
• M2被从缓冲区中移除，并被P1接收。
• 由于时间戳没有冲突，P3接受了M2。