上一章我們了解了分散式系統是什麼、為什麼要讓系統分散，
也大概知道分散式系統會遇到節點死掉、網路斷掉的問題。

接著將更加深入探討，
2.1、2.2 分別介紹兩個思考實驗，
2.3 建立系統模型，也就是把各種情況分類，
以便未來在這些假設基礎上去設計演算法。
2.4 則談談 容錯（fault tolerance）與高可用（high availability）的衡量標準。

2.1 The two generals problem

arm1 與 army2 需要同時出動，才能把城市攻打下來。
他們可以透過信使互相確認要出發的日期，但信使可能會被抓走。

• a model of network
• 目標：同時出發攻打城市
• 困難：信使會被抓

No common knowdlege

兩位將軍永遠不能確定另一位會在同一天出動！
試想：

1. 將軍1 告訴 將軍2 出發日期，還沒收到將軍2 回信
   此時將軍1 不知道將軍2 是沒收到訊息，還是返回的信使被抓了，因此不能輕舉妄動。
2. 當將軍1 收到將軍2 回信，這樣將軍1 照時出發是一定安全的。
   因為將軍2 言出必行！
3. 將軍2 的狀況落回 step 1
   將軍2 並不知道將軍 1 是否收到這個回信的回信？如果沒收到，將軍1 為了不全軍覆沒，可能會不出兵。

這樣就會形成一個無限的 sequence，每次都把全軍覆沒的風險拋給另一個將軍，永遠不能確定另一組軍隊會在同一天出動；就像 distributed system 中的 nodes 沒辦法確定其他 node 的狀態。
順帶一提，這就是 [[TCP 3-way handshakes]] 的情形，基本上只要雙方都收到了一次回信，那只要相信對方會出兵，就沒問題了。

2.2 The Byzantine generals problem

同樣是要同時出動、以信使確認出發日期，
這次假設信使一定會送達，但將軍之中有叛徒！

• a model of node behavior
• 目標：同時出發攻打城市
• 困難：現在保證信使必達，但將軍中有叛徒

可能 scenario

• 將軍3 發現將軍 1 和 2 說得不一樣，但不知道誰說謊，到底要進攻還是撤退？

Theorem 和其他解法？

• Theorem: 3f + 1 個將軍可忍受 f 個將軍是 malicious
• digital cert 可讓 general 2 向 g3 證明當初收到的訊息（g1 簽名）來證明 g2 沒說謊。

2.3 System model

雖然 2.1 和 2.2 把網路和節點錯誤分開討論，但現實中很常兩者同時出錯！
如果要設計演算法，就要對整個系統有一些假設，這裏從 3 個面向來探討：network, node behavior, timing。

1. network behavior

• reliable (perfect) link
  訊息送出一定到達，順序不計較。
• fair loss link
  訊息可能會遺失、重複、順序亂掉。
• arbitrary link
  封包在網路上，每個經過的 node 都可以用 arbitrary 種方式處理（竄改、丟掉、或好好送）

link 可以透過網路協定而「升級」

• arbitrary -> fair loss: TLS
• fair loss -> reliable: retry + dedup

這樣好像只要能夠一直 retry，訊息總會送達。
但現實中，節點可能會 crash，然後某個訊息就永遠的消失。

2. node behavior

• crash-stop
  硬體錯誤之類
• crash-recovery
• byzantine
  a node is faulty if deviates from the algorithm.
  可能是 crash 了，也可能被駭做出其他惡意行為。

在 byzantine 下，如果所有的 node 都跑同樣的程式，而這些程式有同樣的 bug，那這個系統是無法 tolerate 的（根據理論，叛徒要少於 1/3）。

node behavior 不像 network 可以透過 protocol 的保證來做模型之間的轉換。

3. timing

• synchronous
• partially synchronous
• asynchronous

用 synchronous model 設計演算法會簡單，但如果有一點點的差錯（超過預設的 bounded latency / execution speed），就會出非常大的問題。
用 asynchronous model 設計的演算法會十分 robust，但有些問題在此模型下無法被解決。
paritially synchronous 是個 compromise。大部分狀況都是 synchronous，只有當一些 timing guarantines are off 時，則切換成 async。

無法達成 synchrony 的原因

Networks
通常 latency 是可被預測的，但有時會增加：

• message loss
• 網路很擠，在排隊
• network/route reconfiguration

Nodes
通常 node execution speed 是可被預測的，但也有暫停的時候：

• OS scheduling
• stop-the-world garbage collection
• page faults, swap, thrashing

node execution speed 是可被預測的?

因為 instruction 要幾個 cpu clock cycle 都是可以知道的，clock speed 也不會差太多 `[note p19]`

所以實際上，使用 synchronous model 來設計演算法，很不可行。

System models summary

If your assumptions are wrong, all bets are off!

2.4 Fault tolerance and high availability

Fault tolerance

• Failure：整個系統爛掉
• Fault：一部份出錯（節點或網路）
  因此會希望系統能夠容錯（fault tolerance），也就是在有部分爛掉的狀況，還能維持基本系統運作。
• Single point of failure(SPOF)：一個 fault 造成整個系統 fail。這是要盡量避免的狀況。

High availability

• 討論可用性時，不會說這個系統可不可用，而是要依據「可用的比率」來判定。
• availability == uptime == fraction of time that a service is functioning correctly

“Two nines” = 99% up = down 3.7 days/year
“Three nines” = 99.9% up = down 8.8 hours/year
“Four nines” = 99.99% up = down 53 minutes/year
“Five nines” = 99.999% up = down 5.3 minutes/year

• Service level objective (SLO)
  例如 "99.9% of requests in a day get a response in 200 ms"
• Service level agreement (SLA)
  標明 SLO 的合約，公司若沒達成可能要賠錢。