拜占庭將軍問題
什么是拜占庭將軍問題？
-
故事影射的問題
1. 拜占庭將軍問題是一個協議問題，只有所有將軍達成共識，一同攻擊某個敵軍，才能成功，（目的是達成共識，且結果代表大多數人的意見） 2. 分散的軍隊，軍隊內可能有叛徒和敵軍間諜，左右將軍們的決策，在已知有成員謀反的情況下，其余忠誠的將軍在不受叛徒的影響下如何達成一致的協議，拜占庭問題就此形成，（在缺少可信任的中央節點和可信任的通道的情況下，分布在網路中的各個節點應如何達成共識） 3. 拜占庭假設是對現實世界的模型化，由于硬體錯誤、網路擁塞或斷開以及遭到惡意攻擊，計算機和網路可能出現不可預料的行為，（點對點通信，在存在訊息丟失的不可靠信道上試圖通過訊息傳遞方式達到一致性是不可能的） -
問題剖析
1. 身份追溯 2. 資訊私密 3. 防偽簽名 4. 傳遞規則 -
解決方法：區塊鏈
1. 隨機成本（哈希演算法作業量） 區塊鏈輕而易舉地解決了這一問題，它為資訊發送加入了成本，降低了資訊傳遞的速率，而且加入了一個隨機元素使得在一定時間內只有一個將軍可以廣播資訊，這里所說的成本就是區塊鏈系統中基于隨機哈希演算法的“作業量證明”，哈希演算法所做的事情就是計算獲得的輸入，得到一串64位的亂數字和字母的字串， 2. 控制節奏(10分鐘的運算量) 算的輸入資料是指節點發送的當前時間點的整個總賬，當前計算機的算力使其可以實時計算出單個哈希值，但是區塊鏈系統只接受前13個字符是0的哈希值結果作為“作業量證明”，而前13個字符是0的哈希值是非常罕見的，需要整個網路花費10分鐘的時間才在數以億計的資料中找到一個，在一個有效的哈希值被計算出來之前，網路中已經生產了無數個無效值，這就是降低資訊傳遞速率并使得整個系統成功運行的“作業量證明”， -
每個位元幣交易賬號可以看作一個將軍
哈希演算法對資訊傳遞速率的限制加上加密工具使得區塊鏈構成了一個無須信任的資料互動系統，在區塊鏈上，一系列的交易、時間約定、域名記錄、政治投票系統或者任何其他需要建立分布式協議的地方，參與者都可以達成一致， -
區塊鏈思想：
1. 去中心化，避免依賴第三方中心平臺的信任擔保， 2. 只可記錄，不可修改（約束）， 3. 記賬有回報，記賬有成本（算力）， 4. 最長賬單鏈為有效鏈條（公共約束力，增加作惡算力成本），
拜占庭將軍問題與PAXOS演算法中的希臘民主選舉問題有什么區別？
1. 拜占庭將軍問題：在不可靠信道上試圖通過訊息傳遞的方式達到一致性是不可能的（Leslie Lamport證明，當叛徒不到1/3時，存在有效的演算法，不論叛徒如何折騰，忠誠的將軍們總能達成共識，當叛徒達到三分之一時，則無法保證一定能達成一致性），
2. Paxos演算法的前提是：不存在拜占庭將軍問題，即信道是安全的、可靠的，集群節點間傳遞的訊息是不會被篡改的，
ZAB與PAXOS什么關系？
1. Zookeeper Atomic Broadcast，zk原子性廣播協議，
2. ZAB是Paxos的工業實作，目的是構建一個高可用的分布式資料主從系統，follower是leader的從機，leader掛了可以馬上從follower選一個leader，ZAB為了解決活鎖問題，只允許一個行程提交提案，屬于3PC提交，而leader掛了時候選舉演算法是2PC，所有的follower都可以提交，就是我選我，
如何理解2PC與3PC的區別？
PAXOS演算法分為賄選階段（prepare->promise）+提議階段（propose->accept），
在具體的實作程序中，需要對整個選舉程序進行模擬，PAXOS演算法模型中，所有節點都是對等的（選舉與賄選都可以），具體實作的程序中，為了解決“活鎖”的問題，引入了“總統/領導”的概念（主從模式），
方法一： 2PC，即二階段模擬方式，存在問題：
1. 二階段的 prepare 和 commit 中，prepare 到 commit 的程序，需要鎖定資源，同步阻塞導致性能下降，
2. 主節點宕機掛掉，在選舉出新的主節點之前，所有從節點阻塞，
3. commit 階段，網路延遲、丟包導致從節點事務狀態分歧（區域分成功提交），導致整個分布式系統出現資料不一致現象，
由于二階段提交存在著諸如同步阻塞、協調者宕機后阻塞、腦裂等缺陷等問題，所以研究者們在二階段提交的基礎上做了改進，提出了三階段提交，
方法二： 3PC，即三階段模擬方式，
與二階段相比，三階段：
1. 引入超時機制：同時在協調者和參與者中都引入超時機制，
2. 在第一階段和第二階段中插入一個準備階段：保證了在最后提交階段之前各參與節點的狀態是一致的，即三階段提交就有 CanCommit（無鎖狀態）、PreCommit（無鎖狀態）、DoCommit 三個階段，
存在問題：
1. 三階段的超級機制，解決了阻塞問題，
2. CanCommit的預先鋪墊 過渡到 PreCommit 的預備階段，相當于讓我們有理由相信 DoCommit 成功提交的幾率很大，但是由于網路原因導致的資料不一致問題依然存在，
Reference
- https://www.jianshu.com/p/8bcef0ca676c（拜占庭將軍問題快速理解）
- https://baike.baidu.com/item/%E6%8B%9C%E5%8D%A0%E5%BA%AD%E5%B0%86%E5%86%9B%E9%97%AE%E9%A2%98/265656?fr=aladdin（拜占庭將軍問題）
- https://baike.baidu.com/item/%E4%B8%AD%E6%9C%AC%E8%81%AA/5740822?fr=aladdin（中本聰）
- https://www.jianshu.com/p/8bcef0ca676c（拜占庭將軍問題快速理解）
- https://juejin.cn/post/6844904114443436039（面試官：能聊聊Paxos演算法和ZAB協議嗎）
- https://www.jianshu.com/p/30a18e4ef16e（2pc和3pc的詳解與對比）
- https://blog.csdn.net/qq_41946557/article/details/102770531（分布式系統之Paxos選舉協議）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/304121.html
標籤：區塊鏈