分散式系統 Distributed Systems_Models of distributed systems_Week3筆記_拜占庭容錯2種經典解套方式
兩軍問題(Two Generals' Problem)
兩支軍隊由不同將軍領導，準備進攻一座堅固的城市。軍隊在城市附近的兩個山谷紮營。由於有另一個山谷將兩山隔開，兩名將軍只能透過派信使穿越山谷通信，但這山谷由城市護衛佔領，有可能俘虜途徑山谷傳遞消息的任何信使。
雖然兩軍已約定同時進攻，但尚未約定進攻時間。要順利攻擊，兩軍必須同時進攻。如果同一時間只有一支軍隊進攻就會戰敗，因此兩名將軍須約定攻擊時間，並確保對手知道自己同意了進攻計畫。
拜占庭將軍問題(The Byzantine generals problem)
由矽谷科學家Robert Shostak於1978年提出的情境難題。
古代某個大城市「拜占庭」正經歷一場戰爭，四位將軍散落在城內各處，必須在短時間內決定進攻還是撤退。條件在於，不論進攻或撤退，都必須四位將軍一致同意，才能保證最後勝利。
四位將軍決定各自寫信予其他三人，告知相關決定。當每位將軍都寄出信息，又同時收到其他三名將軍的來信後，就會知道決定是否一致，到底是進攻還是撤退。
背後探討的延伸問題
- 如何防止其中一位將軍叛變？
- 又可能其中一位將軍已被暗殺，寄信的其實是間諜？
- 此外，寄出信件後也可能被敵方截取並篡改扭曲事實的內容，從而阻止四位將軍達成共識？
拜占庭容錯
第一種解套方式.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。
Ref:
https://newsletter.scalablethread.com/p/what-is-the-two-generals-problem
https://www.dianyao.co/net-course/%E5%BC%95%E5%85%A5/%E4%B8%A4%E5%86%9B%E9%97%AE%E9%A2%98.html
拜占庭將軍問題的前世與區塊鏈今生
拜占庭将军问题 (The Byzantine Generals Problem)
【入門必讀】從拜占庭容錯協議，看虛擬貨幣的關鍵：信息驗證＆容錯
The Byzantine Generals Problem在 1982 年發表的論文
趣谈拜占庭将军问题
https://courses.edx.org/asset-v1:KTHx+ID2203.1x+2016T3+type@asset+block@3._Basic_abstractions.pdf
留言
張貼留言