分散式系統 Distributed Systems_Models of distributed systems_Week3筆記_CH2.拜占庭容錯2種經典解套方式&Availability

- 10月 15, 2025

https://physics.stackexchange.com/questions/402591/quantum-solution-to-the-two-army-problem
兩軍問題(Two Generals' Problem)

https://www.youtube.com/watch?v=IP-rGJKSZ3s

兩支軍隊由不同將軍領導，準備進攻一座堅固的城市。軍隊在城市附近的兩個山谷紮營。由於有另一個山谷將兩山隔開，兩名將軍只能透過派信使穿越山谷通信，但這山谷由城市護衛佔領，有可能俘虜途徑山谷傳遞消息的任何信使。

雖然兩軍已約定同時進攻，但尚未約定進攻時間。要順利攻擊，兩軍必須同時進攻。如果同一時間只有一支軍隊進攻就會戰敗，因此兩名將軍須約定攻擊時間，並確保對手知道自己同意了進攻計畫。

拜占庭將軍問題(The Byzantine generals problem)

由矽谷科學家Robert Shostak於1978年提出的情境難題。

古代某個大城市「拜占庭」正經歷一場戰爭，四位將軍散落在城內各處，必須在短時間內決定進攻還是撤退。條件在於，不論進攻或撤退，都必須四位將軍一致同意，才能保證最後勝利。

四位將軍決定各自寫信予其他三人，告知相關決定。當每位將軍都寄出信息，又同時收到其他三名將軍的來信後，就會知道決定是否一致，到底是進攻還是撤退。

https://www.youtube.com/watch?v=-D8aXZvzzww

https://www.youtube.com/watch?v=gJqmOf4mFEU

背後探討的延伸問題

如何防止其中一位將軍叛變？
又可能其中一位將軍已被暗殺，寄信的其實是間諜？
此外，寄出信件後也可能被敵方截取並篡改扭曲事實的內容，從而阻止四位將軍達成共識？

拜占庭容錯

第一種解套方式.Oral Messages

安排一個Leader發送進攻/撤退信號給另外三位將軍

情境1.三位將軍中剛好有一個判將，試圖分別給另外兩位將軍不同錯誤訊息。

然而引入了指揮官，因此將軍A、B各自所收到的進攻比撤退比例均為2:1，兩人皆發起進攻。

進攻就成功。

情境2.引入的指揮官是叛徒，其中一位傳入進攻訊息。

然而三位將軍都相互傳遞沒被竄改過的指令訊息，因此三人收到的撤退比進攻比例都是2:1。

撤退就成功。

第二種解套方式.消息簽名Signed message

此方案前提是簽名無法被偽造，並且任何改動皆會被記錄。

情境1.原始消息發送方被其中一個叛徒接收方給竄給。

假設將軍C為叛將，將軍A作為訊息傳送源頭，給B和C發送同樣進攻的消息。

當將軍B收到叛將C的訊息就會發現將軍C有竄改過將軍A的訊息。因此判斷出C為叛將。

情境2.當原始消息發送方本身就是叛將

當A和B互相傳遞訊息交流時就會察覺到C為叛將。因為C給它們各自傳遞的訊息不同。

在真實系統中，節點與網路都可能發生故障，因此在系統模型中需要考慮以下假設：

網路行為 network behaviour（例如：訊息遺失）
節點行為（例如：當機）
時間行為（例如：延遲）

需要針對上述各部分選擇合適的模型。

network behaviour

假設在兩個節點之間有雙向的點對點通訊，可能的情況包括：

Reliable (perfect) links 可靠（完美）連結
訊息「若且唯若」被送出就會被接收。訊息可能會被重新排序。
Fair-losslinks 公平遺失連結
訊息可能會遺失、重複或重新排序。但如果持續重試，訊息最終會成功傳送。
Arbitrary links (active adversary) 任意連結（主動攻擊者）
惡意攻擊者可能干擾訊息（竊聽、修改、丟棄、偽造、重播）。
Network partition 網路分割
某些網路連結可能在長時間內丟棄或延遲所有訊息，使得兩方在一段時間內無法通訊。

node behaviour

每個節點都會執行一個指定的演算法，並假設以下其中一種情況：

Crash-stop(失效停止)
節點若在任意時刻當機，即被視為故障。一旦當機，它將永遠停止執行。
Crash-recovery(失效恢復)
節點可能在任意時刻當機，並失去記憶體中的狀態。可能在之後的某個時間點恢復執行。
Byzantine(任意失效)
節點若偏離演算法，即被視為故障。故障節點可能做出任何行為，包括當機或惡意行為。

synchrony (timing) assumptions(時間)同步性假設

網路與節點的時間假設

同步 (Synchronous) =>在實務上，假設完全同步是危險的。
訊息延遲不會超過一個已知的上限，節點以已知的速度執行演算法。
部分同步 (Partially synchronous)
系統在某些有限（但未知）的時間內是非同步的，其他時間則是同步的
非同步 (Asynchronous)
訊息可能被任意延遲、節點可能任意暫停執行
系統完全沒有任何時間上的保證

實務上違反同步性理想化假設(Violations of synchrony in practice)

網路層面(網路延遲通常是可預測的，但偶爾會因如下原因而發生)

Message loss requiring retry(訊息遺失，需要重新傳送)
Congestion/contention causing queueing(網路壅塞／資源競爭，導致排隊等待)
Network/route reconfiguration(網路或路由重新配置)

節點層面(通常以可預測的速度執行程式碼，但可能會出現暫停，原因如下:)

Operating system scheduling issues(例如：優先權反轉)
Stop-the-world 垃圾回收 (Garbage Collection) 停頓
分頁錯誤 (Page faults)、交換 (Swap)、或記憶體抖動 (Thrashing)

PS:即時作業系統 (RTOS) 可以提供排程上的保證，然而大多數分散式系統並不使用 RTOS。

Availability (可用性)相關術語

Service unavailability = downtime = losing money
Availability = uptime = fraction of time that a service is functioning correctly
Service-Level Objective (SLO) :在多少時間內一定會有一個Response
Service-Level Agreement(SLA) : 類似一個合約，沒滿足SLO可能相應罰款賠償。
Failure: 整體系統都不能運作
Fault: 整體系統某部分仍然能運作，僅部分失能。
► Node fault:某節點發生crash (不會恢復/會恢復回來)、或是被攻擊。
► Network fault: 訊息被延遲或drop
Fault tolerance(容錯):
系統某節點失能，但其他節點仍然能提供服務。當然有一定容錯上限門檻，超過視為Failure。system as a whole continues working, despite faults (some maximum number of faults assumed)
Single point of failure (SPOF):
關鍵單一節點(Bridge Node/Leader Node)失能，進而造成全系統失能。
node/network link whose fault leads to failure

Failure detectors :不希望發生Failure，衍生出偵測演算法工具

Perfect failure detector: 會精準去對crashed 的節點Label為 faulty