分散式系統之間不只是 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