Byzantine Generals Problem / Byzantine Fault Tolerance
- 拜占庭將軍問題也就是分布式網(wǎng)絡(luò)一致性問題（Distributed Consensus）
- 拜占庭容錯(cuò)是萊斯利·蘭伯特(Leslie Lamport)用來描述分布式系統(tǒng)一致性問題時(shí)，在論文中抽象出的著名的例子
- 萊斯利·蘭伯特是美國計(jì)算機(jī)科學(xué)家，是2013年圖靈獎(jiǎng)得主
- 拜占庭將軍的故事大意：
1.拜占庭（古希臘城市弧蝇，現(xiàn)今土耳其伊斯坦布爾，舊名叫做君士坦丁堡）卸亮。拜占庭帝國，即東羅馬帝國。
2.拜占庭帝國想進(jìn)攻一個(gè)強(qiáng)大的大人，派10支軍隊(duì)包圍敵人魄健。敵人雖不比拜占庭帝國強(qiáng)大，但是足以抵御5支拜占庭帝國軍隊(duì)同時(shí)進(jìn)攻烘挫。這10支軍隊(duì)分開包圍诀艰，任何一支單獨(dú)進(jìn)攻都毫無勝算柬甥，至少需要6支軍隊(duì)同時(shí)襲擊才能得勝饮六。
3.拜占庭帝國的這10支軍隊(duì)分散在敵國四周，依靠通信兵起碼相互通信來協(xié)商進(jìn)攻或者撤退苛蒲。各支軍隊(duì)行動(dòng)策略限定為進(jìn)攻或撤退2種卤橄。
4.問題在于：
a.沒有叛徒情況下，一個(gè)將軍提出進(jìn)攻提議臂外，其他將軍同事發(fā)出了不同進(jìn)攻提議窟扑。出于時(shí)間差異，不同將軍收到并認(rèn)可的提議就是不同的漏健；
b.將軍中可能出現(xiàn)判斷嚎货；
c.拜占庭將軍問題不考慮通信兵是否被截獲或無法傳遞信息等問題，也就是認(rèn)為消息傳遞的信道絕無問題蔫浆。蘭伯特已經(jīng)證明了在消息可能丟失的不可靠通信上殖属，通過消息傳遞方式達(dá)成一致性是不可能的。所以在研究拜占庭將軍問題時(shí)瓦盛，已假定信道沒有問題洗显。
- 分布式計(jì)算中外潜，不同計(jì)算機(jī)通過通訊交換信息達(dá)成共識(shí)，從而按照同一套協(xié)作策略來行動(dòng)挠唆。但是有時(shí)候系統(tǒng)中成員計(jì)算機(jī)可能出錯(cuò)而發(fā)出錯(cuò)誤信息处窥，使得網(wǎng)絡(luò)中不同的成員關(guān)于全體協(xié)作的策略得出不同的結(jié)論，從而就破壞了系統(tǒng)的一致性玄组。
- 拜占庭將軍問題被認(rèn)為是容錯(cuò)性問題中最難的問題類型之一滔驾。共識(shí)算法的核心就是解決拜占庭將軍問題。
- 解決分布式系統(tǒng)一致性問題主要是蘭伯特提出的Paxos算法俄讹。但是該算法僅僅適用于中心化的分布式系統(tǒng)嵌灰，這樣的系統(tǒng)中沒有不誠實(shí)節(jié)點(diǎn)。
- 1999年颅悉，有人提出了PBFT算法（Practical Byzantine Fault Tolerance, 實(shí)用的拜占庭容錯(cuò)算法）沽瞭。
1.叛徒等于或大于三分之一，拜占庭問題無解剩瓶；
2.當(dāng)叛徒數(shù)量不到三分之一驹溃，那么忠誠將軍就至少有三分之二，此時(shí)拜占庭問題有解延曙，仍然可以達(dá)到容錯(cuò)豌鹤。
- 比特幣系統(tǒng)通過POW共識(shí)機(jī)制巧妙地解決了拜占庭容錯(cuò)問題。
1.POW增加發(fā)送信息的成本枝缔，降低了節(jié)點(diǎn)發(fā)送消息的速度布疙，保證一段時(shí)間內(nèi)只有一個(gè)節(jié)點(diǎn)廣播消息，同時(shí)在廣播上附上簽名愿卸。這樣就解決了因?yàn)闀r(shí)間差而導(dǎo)致消息傳遞不一致的問題灵临；
2.對(duì)于將軍做叛徒的問題，比特幣系統(tǒng)的解決方案就是趴荸，讓比特幣網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)沒有動(dòng)機(jī)和動(dòng)力做叛徒儒溉。
a.POW工作量證明機(jī)制提高了做叛徒（發(fā)布虛假區(qū)塊）的成本，在工作量證明下发钝，只有第一個(gè)完成證明的節(jié)點(diǎn)才能廣播區(qū)塊顿涣，競爭難度非常大，需要很高算例酝豪，如果不成功其算力就白白的耗費(fèi)了（算力是需要成本的）涛碑，如果有這樣的算力作為誠實(shí)的節(jié)點(diǎn)，可以獲得很大的收益（這就是礦工所作的工作）孵淘，這也實(shí)際就不會(huì)有做叛徒的動(dòng)機(jī)蒲障，整個(gè)系統(tǒng)也因此而更穩(wěn)定。
b.對(duì)于51%攻擊問題，那更是提高了做叛徒的成本晌涕。擁有這么大的算力的滋捶，自然就是希望依賴比特幣系統(tǒng)而盈利的，當(dāng)然更不會(huì)造假而損壞自身利益余黎。
c.當(dāng)然很多人批評(píng)POW工作量證明機(jī)制造成巨大的電力浪費(fèi)重窟，促使人們?nèi)ヌ剿餍碌慕鉀Q一致性（共識(shí)）問題的機(jī)制：權(quán)益證明機(jī)制（POS : proof of Stake）是一個(gè)代表。在拜占庭將軍問題的角度來看惧财，它同樣提高了做叛徒的成本巡扇，因?yàn)橘~戶需要首先持有大量余額才能有更多的幾率廣播區(qū)塊。如果已經(jīng)擁有這么大的利益垮衷，當(dāng)然更不會(huì)造假而損壞自身利益了厅翔。
