分散式系统之间不只是 unicast，更多的是有 multicast 的需求，
因此这章将介绍广播。
广播的协定有很多种，差别在於 deliver（把讯息传给程序） 的顺序

前一章也提到讯息顺序与时钟息息相关，
因此 4.1 将介绍 2 种 logical time，
而 4.2 4.3 则开始讲广播。

4.1 Logical time

为了能够准确的排序讯息，
而不至於发生错乱的对话或错误顺序的资料库操作，
逻辑时间广泛用於分散式系统。

主要分为 2 种：

1. lamport clock
2. vector clock
   除了介绍演算法，也会以一些数学性质去探讨其与前一章提到的 happens before, causality 等等的关系。

Lamport clock

count the number of events that have occured

Algorithm

on 初始化 do  
	t := 0  // 每个 node 有独立的 timer
end on

// local 事件
on any event occurring at the local node do 
	t := t + 1
end on

// 传送 message m
on request to send message m do  
	t := t + 1; send (t, m) via the underlying network link
end on

// 收到 message m
on receiving (t′,m) via the underlying network link do 
	t := max(t, t′) + 1  
	deliver m to the application
end on

Properties

L(a) 代表 a 事件的蓝波时间

a -> b => L(a) < L(b)

这个性质与 causality 一致，
只要 a 事件先发生，L(a) 一定 < L(b)。
注意反过来不一定成立！

L(a) < L(b) 可能是：

1. a -> b
   • a 事件比 b 事件早发生
2. a || b
   • 不知道 a 与 b 事件谁先发生

延伸为 total order

不同 node 上可能有相同 timestamp
可以使用 (timestamp, identifier）使得这个 pair 是 unique 的，
就可以把 [[happens-before relation]] 的 partial order 延伸为 total order。
至於拥有相同 timestamp 的事件如何排序，演算法怎麽定，因此是 arbitrary 的。
（例如照 identifier 的字母顺序，(3,A) 就会排在 (3,B) 前面）

Summary

无论如何，只要有 lamport clock，
就能把分散式系统中的所有事件排出一个符合因果关系(causality)的顺序了！

举例

![[Screen Shot 2021-09-20 at 9.19.36 PM.png]]

Lamport clock 已经让我们能够排序系统中的所有事件，
但没办法透过 Lamport clock 知道到底两个事件是 concurrent？
还是某件事 happens-before 另一件？

Vector clock

detect if events are concurrent

Algorithm

// 各 node 初始化一个阵列代表所有 node 的 timestamp
on 初始化 at node Ni do
	T := ⟨0,0,...,0⟩
end on

// local 事件
on any event occurring at node Ni do
	T [i] := T [i] + 1
end on

// 传送时，把自己的 timestamp + 1 後，整个阵列送出去
on request to send message m at node Ni do 
	T [i] := T [i] + 1; 
	send (T , m) via network
end on

// 接收时，拿讯息中的阵列更新 local 阵列，并把自己的 timestamp + 1
on receiving (T ′, m) at node Ni via the network do 
	T[j] := max(T[j],T′[j]) for every j ∈ {1,...,n} 
	T[i] := T [i] + 1; deliver m to the application
end on

一组 timestamp 的意义，
除了代表 a 事件，还包含其他发生在 a 之前的事件。

Vector clock timestamp 排序

那如何比较两组 vector clock 呢？

• T = T′ iff T[i] = T′[i] forall i ∈{1,...,n}
• T ≤ T′ iff T[i] ≤ T′[i] forall i ∈{1,...,n}
  有了上面两个定义，可以简洁地写出：
• T < T′ iff T ≤T′ and T /=T′
• T || T′ iff T ̸≤ T′ and T′ ̸≤ T

为什麽不直接定 T < T′ 而要定义 T ≤ T′再用此来定？

比较简单ＸＤ
注意到 T < T' 不是指 T 所有元素 < T'。
而是可以 <=，（想想 (1,2,3,3) 和 (1,2,4,3)）
但又不能全部一样（这样就是同时了）
那当然先定义上面 T=T' 和 T≤T′ 比较省事啦

Properties

(V(a) < V(b)) ⇐⇒ (a→b)
(V(a) = V(b)) ⇐⇒ (a=b)
(V(a) || V(b)) ⇐⇒ (a||b)

举例

![[Screen Shot 2021-09-20 at 9.50.43 PM.png]]

Summary

vector clock timestamps 间的 partial order，
跟 [[happens-before relation]] 的 partial order 完全一致。
而

Lamport clock vs Vector clock

lamport clock: 足够排出 total order
vector clock: capture the partial order of happens before

4.2: Broadcast ordering

Receiving vs delivering

![[Screen Shot 2021-09-20 at 10.28.23 PM.png]]

先讲清楚几个名词：

• send: 电脑传送讯息
• receive: 电脑接收讯息
• deliver: receive 讯息後，可能先放在 buffer，或传给应用程序。

广播的演算法主要差别在於 deliver 的顺序。

Forms of reliable broadcast

• 这几种都是 reliable，并建立在 partially sync / asnc model 上，所以 no upper bound on message latency
• 差别：讯息被程序接收的**「顺序」**

1. FIFO
   只在乎同个节点传送的讯息有按序 deliver
2. Causal
   不同节点上广播的讯息，如果能排出先後，就要按照 causal order 来 deliver
   若有 concurrent 的 broadcast，则在前在後都可以，所以不同节点上的讯息顺序不一定相同。
3. Total order
   所有节点的讯息顺序都要完全一样
   对於传给自己节点的广播讯息，FIFO 或 Causal 都可以马上 deliver，只有 total order 可能需要 holdback 等待

证明 causal broadcast 满足 FIFO broadcast 的要求
证明 FIFO-total order broadcast 满足 causal broadcast 的要求

4.3 Broadcast Algorithms

认识了不同广播演算法後，这节讲实作。

广播演算法主要目的有：

1. reliably 送达
2. deliver in the right order

怎麽确保讯息确实被送到每个节点呢？

考虑 n1 想广播，如果只靠他传讯息到所有其他节点：

1. 使用 reliable link (retry + dedup)
2. 如果 n1 在传完所有讯息之前就挂掉，就没救ＱＱ

Eager reliable broadcast

光靠一个 node 不行，请所有其他 nodes 帮忙传：
如果没发生什麽事，还要花 O(n^2)，太贵ㄌ

Gossip protocols

上述两种情况都太极端，如果其他节点只随机广播给 m 个节点：
如果第一次收到，也随机传。
如果收到第二次以上，就忽略。
这样就会像八卦一样，人传人，传遍整个圈子～

Q1. 既然是随机送，会不会有一些节点永远收不到？
如果参数选择得好，节点没被广播到的机率很小，但这个演算法本身并不保证每个节点都能收到。

Q2. 不会有重复收到的问题吗？
一样要靠参数调整吧，这里没详细说，可能太数学。

FIFO

// 初始化
on initialisation do
	sendSeq := 0; 
	delivered := ⟨0, 0, . . . , 0⟩; 
	buffer := {}
end on

// 传送广播讯息
on request to broadcast m at node Ni do			
	send (i,sendSeq,m) via 	reliable broadcast 
	sendSeq := sendSeq + 1
end on

// 接收後 deliver 广播讯息给应用程序
on receiving msg from reliable broadcast at node Ni do
	buffer := buffer ∪ {msg}
	// 在 buffer 中寻找，任何一个讯息若带有期待的 sequence number，就 deliver
	while ∃sender , m.(sender , delivered[sender], m) ∈ buffer do
		deliver m to the application
		delivered[sender] := delivered[sender] + 1 end while
end on

Causal

使用一组 vector

on initialisation do
	sendSeq := 0; 
	delivered := ⟨0, 0, . . . , 0⟩; 
	buffer := {}
end on

on request to broadcast m at node Ni do 
	deps := delivered;
	deps[i] := sendSeq 
	send (i,deps,m) via reliable broadcast 
	sendSeq := sendSeq + 1
end on

on receiving msg from reliable broadcast at node Ni do 
	buffer := buffer ∪ {msg}
	while ∃(sender,deps,m) ∈ buffer.deps ≤ delivered do
		deliver m to the application
		buffer := buffer \ {(sender , deps , m)} 
		delivered[sender] := delivered [sender] + 1
end while end on

Total order broadcast

要能好好的实施 total order broadcast，
并顾及到 fault-tolerance 较为复杂，
这节先提出两个简单的解法提供大方向。

Single leader

既然要大家的顺序都一样，
那就有个 leader 决定顺序，
因此大家要广播，都先交给 leader，
让 leader 用 FIFO broadcast 告诉其他 follower 就可以啦

问题

leader 若挂掉，怎麽办？
也难以安全的换 leader。

Lamport clocks

前面有提到 lamport clocks 可以决定 total order，
那就根据讯息的 lamport timestamp 来 deliver。

问题：

只有当收到更大 timestamp 的讯息时，才能 deliver 前面比较小的 timestamp 的讯息，以免还有更小 timestamp 的讯息其实还在路上。
如果网路ㄅ

这两个解法都会有 SPOF 的问题，
要马 leader 挂了就没救，
要马随便一个节点挂了，大家收不到某个该收的广播讯息，就会一直不能 deliver 後面的讯息。
no fault tolerance :(((
下一章会讲 fault-tolerant total order broadcast