分散式系統 Distributed Systems_Time, clocks, and ordering of events_Week4筆記_part2.Lamport跟Vector Clocks計算

做個課堂筆記紀錄，因為坐在教室後面會照到前面同學後腦杓。歹勢....

分散式系統中的 Lamport Clock 與 Vector Clock

Lamport Clock（Lamport 時鐘）

用途：

用來在分散式系統中決定事件（Event）的先後順序，避免物理時鐘不同步所造成的混亂。

結構與運作：

1. 每個節點都維護一個整數計數器（Lamport Clock）。
2. 當本地有事件發生時，計數器加一。
3. 發送訊息時，附加目前的 Lamport Clock 值。
4. 接收訊息時，將本地計數器設為收到時鐘值與本地時鐘的最大值後再加一。

Vector Clock（向量時鐘）

用途：

用來追蹤每個節點彼此之間的事件先後關係，比 Lamport Clock 更進一步，可以判斷事件是否真正平行（concurrent）。

結構與運作：

1. 每個節點都維護一個長度為 N（節點數）的向量，每個元素分別表示此節點對自己和其他節點事件次數的看法。
2. 本地事件發生時，將自己對應的一格加一。
3. 發送訊息時，附上自己的 Vector Clock（整個向量）。
4. 接收訊息時，將收到的 Vector Clock 與本地 Vector Clock 逐格比較，大者為新值，再把自己格加一。

總結

• Lamport clock 只能粗略判斷時間順序（數字比大小），但無法區分平行事件或真實先後。
• Vector clock 若 v1 < v2（全小於），就可以明確判定 v1 happens-before v2；若無法比較，就是平行事件。

第10題.一起修課的班代幫忙上台作答-Lamport Clock

給出四個節點 (A、B、C、D) 之間的訊息交換（m1 ~ m9），要求在每個訊息送出或接收事件標記 Lamport 時間戳（timestamp）。

初始值：每個節點的 Lamport Clock 都是 0。

送出訊息：本地 Lamport Clock +1，送出訊息並將其值作為 timestamp 附加在消息上。

接收訊息：收到訊息後，把本地 Lamport Clock 更新為「max(本地, 收到的) + 1」。

節點 A 發送 m1、m2、m3，分別遞增自己的 Lamport Clock。

B, C, D 分別在收到訊息後按規則更新 Lamport Clock（最大值+1）。

每遇到接收/發送動作，都照規則隨時更新時間。

最後一欄 Final，是執行完所有訊息操作後四個節點各自的 Lamport Clock。

第12題.自己上台作答紀錄-Vecotr Clocks

給出四個節點 (A, B, C, D) 的訊息傳遞流程（m1~m9），要求在每次訊息送出或接收時，記錄每個節點的 Vector Clock 值。

Vector Clock 更新規則

初始： 所有節點都為 (0, 0, 0, 0)。

本地事件： 自己的那個欄位加 1（如 A 執行動作則 A 的第一格加 1）。

送訊息： 先本地加 1，再將目前整個向量附在訊息裡。

收訊息： 向量每個位元都取「本地」與「收到」的最大值，再將自己的欄位加 1。

每個 m1 到 m9 事件後，所有節點的 Vector Clock 都依上述規則更新。

例如：m1 是 A 發送訊息給 B

A: 將自己第 1 格加 1 → (1, 0, 0, 0)。

B: 收到 (1, 0, 0, 0) 後, 其本地也是 (0, 0, 0, 0)，所以 max 後為 (1, 0, 0, 0)，再將 B 的第 2 格加 1, 變 (1, 1, 0, 0)。

向量每格數字代表： 到目前為止自己看見各節點的本地事件次數。

比較向量大小： 若一個事件的向量所有元素都小於等於另一事件，就代表「先發生」。

第13題.綜合前面兩題的happens-before relationship抉擇

(老師解說)

利用前兩題計算出來的 Lamport timestamps 與 Vector timestamps，判斷下列三組事件 

send(m2) & send(m3)

send(m3) & send(m5)

send(m5) & send(m9) 

是否存在 happen-before（先後）關係。

1. send(m2) 和 send(m3)

Lamport：2 vs 3 → 2 < 3，所以 Lamport clock 認為 send(m2) "可能"早於 send(m3)。但是，Lamport clock 只比出可能的順序，無法判斷平行或直接有無關。

Vector clock：(2,0,0,0) < (3,0,0,0)（每個欄位皆不大於且有一個嚴格小於） → 代表 send(m2) happens-before send(m3)。

2. send(m3) 和 send(m5)

Lamport：3 vs 5 → Lamport clock 只看 3 < 5，但其實不一定有先後。解答直接寫 cannot tell。

Vector clock：(3,0,0,0) 與 (1,3,0,0) 無法比較（有的欄位大，有的欄位小）→ 也就是 concurrent（平行事件）。

3. send(m5) 和 send(m9)

Lamport：5 vs 11 → Lamport clock 只看數字，不能明確判斷先後，cannot tell。

Vector clock：(1,3,0,0) < (2,3,5,0)（每個欄位皆不大於且有一個嚴格小於），代表 send(m5) happens-before send(m9)。

Ref:

https://www.youtube.com/playlist?list=PLeKd45zvjcDFUEv_ohr_HdUFe97RItdiB

https://www.youtube.com/watch?v=x-D8iFU1d-o