關於拜占庭將軍問題，一個簡易的非正式描述如下：

拜占庭帝國想要進攻一個強大的敵人，為此派出了10支軍隊去包圍這個敵人。

這個敵人雖不比拜占庭帝國，但也足以抵禦5支常規拜占庭軍隊的同時襲擊。

基於一些原因，這10支軍隊不能集合在一起單點突破，必須在分開的包圍狀態下同時攻擊。

他們任一支軍隊單獨進攻都毫無勝算，除非有至少6支軍隊同時襲擊才能攻下敵國。

他們分散在敵國的四周，依靠通訊兵相互通訊來協商進攻意向及進攻時間。

困擾這些將軍的問題是，他們不確定他們中是否有叛徒，叛徒可能擅自變更進攻意向或者進攻時間。

在這種狀態下，拜占庭將軍們能否找到一種分散式的協議來讓他們能夠遠端協商，從而贏取戰鬥 。

這就是著名的拜占庭將軍問題。

應該明確的是，拜占庭將軍問題中並不去考慮通訊兵是否會被截獲或無法傳達資訊等問題，即訊息傳遞的通道絕無問。

Lamport已經證明了在訊息可能丟失的不可靠通道上試通過訊息傳遞的方式達到一致性是不可能的。

所以，在研究拜占庭將軍問題的時候，已經假定了通道是沒有問題的，並在這個前提下，去做一致性和容錯性相關研究

11位拜占庭將軍去打仗, 他們各自有權力觀測敵情並作出判斷, 進攻或撤退, 那麼怎麼讓他們只用傳令兵達成一致呢?

一種很符合直覺的方法就是投票,

每位將軍作出決定後都將結果"廣播"給其餘所有將軍, 這樣所有將軍都能獲得同樣的11份(包括自己)結果, 取多數, 即可得到全軍都同意的行為.

但如果這11位將軍中有間諜呢? 假設有9位忠誠的將軍, 5位判斷進攻, 4位判斷撤退, 還有2個間諜惡意判斷撤退, 雖然結果是錯誤的撤退, 但這種情況完全是允許的. 因為這11位將軍依然保持著狀態一致性.

暫時從戰爭故事中抽離出來, 分散式資料庫最糟糕的問題絕對不是寫入或者讀取失敗, 而是狀態不同步, 還感知不到. 這個的後果就是correctness不能保證, 那程式就沒有任何意義了.

2個間諜怎麼破壞狀態一致性呢? 他們跟5位判斷進攻的將軍說, 我們支援進攻, 那麼這5位將軍統計發現7位支援進攻, 4位支援撤退, 將發動進攻. 又跟4位撤退的將軍說, 我們支援撤退, 一統計, 5票進攻, 6票撤退, 立馬撤退. 這場戰爭必輸無疑了.

避免這種狀態不同步的問題, 我稱之為"廣義拜占庭將軍問題".

解決廣義拜占庭問題, 必須滿足兩個條件:

對任意忠誠的將軍來說, 他們看到的其餘將軍的決定必須是一樣的, 不允許出現前文那種, 5位將軍統計結果是7攻4撤, 另外4位將軍是5攻6撤.所有忠誠將軍的決定對於其餘所有忠誠將軍都是一樣的. 比如, V(1)表示1號將軍的決定. 那麼其餘所有忠誠將軍的統計表上, V(1)一定是一樣的. 如果這點不能保證, 說明間諜已經可以直接顛覆指揮系統了, 系統怎樣都是無效的, 哪怕達成了一致.

上面的條件等價於如何讓一個將軍(可以是間諜)對所有接收者的指令保持一致? 這個我叫"狹義拜占庭將軍問題".

口頭版對傳令兵的要求僅有,

大多數的節點不可能像拜占庭將軍一樣有主觀惡意, 除非節點已經感染了病毒, 能避免伺服器宕機這類的錯誤就可以了.命令的來源一定可以判斷在現實環境是不可能達到的, 這要求節點之間採用網絡卡直接連線而不是用交換機.

因為有可能是叛徒! 他會給不同的不同的指令.

所以, 悲催的忠臣必須問所有別的將軍, "你們收到的觀測結果是啥?"來取校驗, 同時又必須告訴所有別的將軍, "我收到的觀測結果是啥?".

但該死的是, 忠臣A在告訴別的將軍來自觀測結果的時候, 別的將軍會懷疑忠臣A是不是叛徒. 別的將軍判斷忠臣A是忠臣的唯一的辦法是詢問別的忠臣A通知的忠臣, "忠臣A告訴你都發了啥?"

每次遞迴都做悲觀預期即是個叛徒, 那麼就達成了

感覺這是說不明白了=_=, 看例子也不容易懂, 從傳統動態規劃狀態轉移的角度理解是最容易的.