拜占庭將軍問題,是由萊斯利·蘭波特在其同名論文中提出的分散式對等網路通訊容錯問題。
在分散式計算中,不同的計算機透過通訊交換資訊達成共識而按照同一套協作策略行動。但有時候,系統中的成員計算機可能出錯而傳送錯誤的資訊,用於傳遞資訊的通訊網路也可能導致資訊損壞,使得網路中不同的成員關於全體協作的策略得出不同結論,從而破壞系統一致性。拜占庭將軍問題被認為是容錯性問題中最難的問題型別之一。
其論文中的描述是這樣的:一組拜占庭將軍分別各率領一支軍隊共同圍困一座城市。為了簡化問題,將各支軍隊的行動策略限定為進攻或撤離兩種。因為部分軍隊進攻部分軍隊撤離可能會造成災難性後果,因此各位將軍必須透過投票來達成一致策略,即所有軍隊一起進攻或所有軍隊一起撤離。因為各位將軍分處城市不同方向,他們只能透過信使互相聯絡。在投票過程中每位將軍都將自己投票給進攻還是撤退的資訊透過信使分別通知其他所有將軍,這樣一來每位將軍根據自己的投票和其他所有將軍送來的資訊就可以知道共同的投票結果而決定行動策略。
系統的問題在於,將軍中可能出現叛徒,他們不僅可能向較為糟糕的策略投票,還可能選擇性地傳送投票資訊。假設有9位將軍投票,其中1名叛徒。8名忠誠的將軍中出現了4人投進攻,4人投撤離的情況。這時候叛徒可能故意給4名投進攻的將領送信表示投票進攻,而給4名投撤離的將領送信表示投撤離。這樣一來在4名投進攻的將領看來,投票結果是5人投進攻,從而發起進攻;而在4名投撤離的將軍看來則是5人投撤離。這樣各支軍隊的一致協同就遭到了破壞。
由於將軍之間需要透過信使通訊,叛變將軍可能透過偽造信件來以其他將軍的身份傳送假投票。而即使在保證所有將軍忠誠的情況下,也不能排除信使被敵人截殺,甚至被敵人間諜替換等情況。因此很難透過保證人員可靠性及通訊可靠性來解決問題。
假始那些忠誠(或是沒有出錯)的將軍仍然能透過多數決定來決定他們的戰略,便稱達到了拜占庭容錯。在此,票都會有一個預設值,若訊息(票)沒有被收到,則使用此預設值來投票。
上述的故事對映到計算機系統裡,將軍便成了計算機,而信差就是通訊系統。雖然上述的問題涉及了電子化的決策支援與資訊保安,卻沒辦法單純的用密碼學與數字簽名來解決。因為不正常的電壓仍可能影響整個加密過程,這不是密碼學與數字簽名演算法在解決的問題。因此計算機就有可能將錯誤的結果提交去,亦可能導致錯誤的決策。
拜占庭將軍問題,是由萊斯利·蘭波特在其同名論文中提出的分散式對等網路通訊容錯問題。
在分散式計算中,不同的計算機透過通訊交換資訊達成共識而按照同一套協作策略行動。但有時候,系統中的成員計算機可能出錯而傳送錯誤的資訊,用於傳遞資訊的通訊網路也可能導致資訊損壞,使得網路中不同的成員關於全體協作的策略得出不同結論,從而破壞系統一致性。拜占庭將軍問題被認為是容錯性問題中最難的問題型別之一。
其論文中的描述是這樣的:一組拜占庭將軍分別各率領一支軍隊共同圍困一座城市。為了簡化問題,將各支軍隊的行動策略限定為進攻或撤離兩種。因為部分軍隊進攻部分軍隊撤離可能會造成災難性後果,因此各位將軍必須透過投票來達成一致策略,即所有軍隊一起進攻或所有軍隊一起撤離。因為各位將軍分處城市不同方向,他們只能透過信使互相聯絡。在投票過程中每位將軍都將自己投票給進攻還是撤退的資訊透過信使分別通知其他所有將軍,這樣一來每位將軍根據自己的投票和其他所有將軍送來的資訊就可以知道共同的投票結果而決定行動策略。
系統的問題在於,將軍中可能出現叛徒,他們不僅可能向較為糟糕的策略投票,還可能選擇性地傳送投票資訊。假設有9位將軍投票,其中1名叛徒。8名忠誠的將軍中出現了4人投進攻,4人投撤離的情況。這時候叛徒可能故意給4名投進攻的將領送信表示投票進攻,而給4名投撤離的將領送信表示投撤離。這樣一來在4名投進攻的將領看來,投票結果是5人投進攻,從而發起進攻;而在4名投撤離的將軍看來則是5人投撤離。這樣各支軍隊的一致協同就遭到了破壞。
由於將軍之間需要透過信使通訊,叛變將軍可能透過偽造信件來以其他將軍的身份傳送假投票。而即使在保證所有將軍忠誠的情況下,也不能排除信使被敵人截殺,甚至被敵人間諜替換等情況。因此很難透過保證人員可靠性及通訊可靠性來解決問題。
假始那些忠誠(或是沒有出錯)的將軍仍然能透過多數決定來決定他們的戰略,便稱達到了拜占庭容錯。在此,票都會有一個預設值,若訊息(票)沒有被收到,則使用此預設值來投票。
上述的故事對映到計算機系統裡,將軍便成了計算機,而信差就是通訊系統。雖然上述的問題涉及了電子化的決策支援與資訊保安,卻沒辦法單純的用密碼學與數字簽名來解決。因為不正常的電壓仍可能影響整個加密過程,這不是密碼學與數字簽名演算法在解決的問題。因此計算機就有可能將錯誤的結果提交去,亦可能導致錯誤的決策。