拜占庭將軍問題確保系統正常為什麼需要2k+1個正常節點？
如果系統中有n個故障節點，系統要想正確運行，必須至少要有2n+1個正常節點。
請問為什麼正常節點要是2n+1, 而不是n+1？如果按照取 majority 而得到一致性結果，正常節點只需要 n+1 個不就可以了？
2n+1能夠保證總的節點個數是奇數，這樣在出現故障的情況下要麼正常節點數大於等的n+1，要麼故障節點數大於等於n+1。如果正常節點數大於等於n+1，那麼集群能夠提供正常服務，否則為異常；一致性協議則通過這種方式來判斷投票結果。而直接用n+1，則可能是奇數也可能是偶數，如果是偶數，正常和異常各佔一半節點時，則無法做出判斷。
一年後的深夜。。。我竟然複習到了自己在知乎上的提問，(期末真是有種藥丸的感覺)
對於這個邊界的理解，我覺得設想一種忠誠將軍間發生通信故障（只是兩組節點之間不能通信，但每一組內部仍然可以通信，即腦裂）為例子就很好理解了
拜占庭將軍說不清楚，咱們可以換成中國將軍（為了起名字方便）：
－－－ 我是悲劇的分割線－－－
假設有9個將軍（3n的情況），3個是秦檜的秦家軍（我知道秦檜手裡沒什麼兵，給他安排將軍只是為了講故事方便），6個忠誠將軍，其中3個是岳飛的岳家軍，另外3個是韓世忠的韓家軍，可是有一天外敵來襲，岳家軍與韓家軍之間突然不能通信（網路發生腦裂），他們都只能與秦家軍的3個將軍溝通。
這時，對於岳家軍和韓家軍來說，他們互相不知道死活，而眼前能夠通信的將軍只剩下6個（2n）。如果岳家軍不懷疑秦檜的忠誠（不考慮拜占庭容錯），直接與秦家軍投票後，那麼岳秦兩家可能最終決定北上（岳家節點在資料庫里記入北上 6票），而同時韓家軍與秦家軍投票決定南下（秦家軍是壞人，所以會兩邊投票，導致韓家節點會在資料庫里計入南下6票）。那麼最終有一天通信恢復了，他們趕緊告訴對方說我這裡有一個6票（2n票）的決議，可是對方也有一個6票的決議，而這兩個決議是互相衝突的。於是他們發現他們被坑了，但又都無法直接用票數說服對方，不知如何是好。
所以在這種情況下，無論岳家軍和韓家軍都不能在只有6個將軍的情況下通過投票來決定軍隊進軍方向。（3個叛徒時，2n=6票是不夠的）
－－－ 我是喜劇的分割線－－－
可是如果有10個將軍（3n+1），情況就好多了。假設岳家軍多了1個將軍，那麼他們直接與秦家奸賊們達成一致即可，因為他們總會使得自己的票數達到7票（2n+1），而此時韓家軍無論怎麼跟秦軍溝通都只能達到6票（2n）。所以這時候，韓家軍不能與秦軍達成的協議，只能原地堅守待命。最終有一天韓家軍和岳家軍重新成功通信，韓家軍發現岳家軍所有的決議票數都比自己多，那麼為了大局著想，韓家軍必須立刻遵從岳家軍的所有現有決議，即遵從票數多的決議。
最終他們怒斬秦檜，大破金軍，直搗黃龍，恢復中華～～
－－－我是思考題－－－
但是注意，如果這時候韓家軍也增加1個將軍，達到了11個（總節點數為3n+2，但是故障節點為n+1），會發生什麼情況？（能否容忍n個惡意節點）
這時一旦岳韓兩軍通信故障，岳家軍就又不能直接與秦家軍投票達成統一了，因為他們投票後將得到7票(2n+1)，而秦家軍可能與韓家軍為不同的結論投票，也得到7票(2n+1)，最終使得成功通信後，這些協議將無法達成一致
所以，這個推論值得注意：如果系統中有n+1個故障節點，那麼2n+1個正常節點將不足以容忍其中出現n個叛徒的拜占庭錯誤。
實際上這個問題也可以描述為：對於一個 3n-1 個節點的系統中，如果有n個故障節點，n個正常節點，無法容忍 n－1個叛徒。
這與樓主的題目並不衝突，只是有時候會混亂，所以單獨提出。比較需要注意的是
1 這個答案中的所有討論都有個前提：消息都是口頭消息，沒有簽名，無法判斷消息原始來源（口頭消息）。否則應該可以通過演算法達到更高容錯比例2 發消息的人本身可能是叛徒節點也就是向接收者發送不同的命令。這時的系統容錯目標退化為節點的最終結論必須保持一致，而不需要判斷到底哪個才是「正確」的命令。
第一點的意思是說，岳將軍是可以信任秦檜將軍的投票的，但不能相信他們替韓世忠投的票。
－－－所以說－－－
解決「拜占庭問題」的核心思路是：尋找一種演算法或平衡點，使得即便網路中發生腦裂，當前的投票團體中任意節點都可以獲得一種信心，相信根據當前團體數量得到的所有投票結果，不會在其他團體回歸時被推翻。（好繞啊，我覺得我又說不明白了，但是我不想繼續寫了）
下面這篇文章給出了數學證明拜占庭將軍問題，口頭演算法詳解。n=7,m=2的時候的投票過程。有關n=3m+1的證明。
其實是確保惡意進程小於1/3，n個惡意進程，那麼總節點數至少需要3n+1才可以進行經典的paxos演算法運算，只要稍微變種一下就行。（此時quorum數是2n+1,也就是總數的2/3強而不是傳統的1/2強。任意兩個quorum之間至少有n+1個公共成員，而惡意進程最多n個，因此必有至少一個合法進程）
Lamport那篇byzsimple論文寫的非常清楚了。說點對拜占庭問題自己的一點理解，它並不限制proposer的善惡，而是限制acceptor最多有不超過1/3的惡意進程。由於proposer不可信，因此基礎paxos的accept rpc就不能讓它發起了。而是轉化為通過讓acceptor內部投票決定(acceptor之間需要廣播promise以確定可行性)。
另一個問題：最開始對於進程崩潰和進程惡意有點暈，這樣思考就明白了：崩潰和惡意是兩個正交的維度，毫無關係。比如說有10個進程，那麼最多3個惡意進程，同時也容忍3個好的進程掛掉。在這種情況下有7個進程，雖然有3個壞人，仍然構成quorum.也就是說，拜占庭paxos允許有小於1/3的壞人，同時允許小於1/3的進程崩潰（但其實只要有一個好的進程崩潰，liveness就無法滿足）。
剛剛看完一遍論文，第二遍閱讀中，如有不當理解再來修正。
上述不少答案並沒有搞清楚多數派（這名詞是啥，我還是沒想到）和一致性問題的區別。
"多數派決定"和拜占庭問題是兩個不太一樣的問題，多數派的決定是說在決議大於一半以上的時候的選擇，而拜占庭問題是一致性問題，說的是在存在錯誤節點或者叛徒的情況下，正常節點在某種方案下能達到一致，具體可以看Leslie Lamport的論文《Reaching agreement in the presence of Faults》。
有一部分的理論可以簡單的這麼理解，在正常節點中，需要知道另外正常節點的選擇（即忽視錯誤節點的狀態），如何才能忽視呢，假設正常節點是n個，錯誤節點是f個，那麼在發送過來的消息中n - f &> (n-f)/2 + f，即除去錯誤節點後，還是多數派，這樣才能達成一致，那麼可以求得n &> 3f， 文中給出了完備證明，即有n &>= 3f+1的一致性方案，同時證明了n＝3f的時候是無解的。
PS: Leslie Lamport 分散式大神，據說他的《Time, clocks, and the ordering of events in a distributed system》是計算機史上引用數量最多的論文。 灰常崇拜！！
根據題主提供的答案，總共3f+1個節點中：允許有f個不回應的節點（即正常節點因為離線或者網速等原因無法響應）同時允許有f個惡意節點，故意發送誤導信息
只要剩下的f+1個節點正常通信即可完成多數決。
推薦閱讀：
※ETH CS Master（全獎） vs UPenn CIS PhD，如何選擇？
※TiDB和CockroachDB同為Spanner/F1的開源實現，有哪些重大差異？
※分散式資料庫中為什麼要使用 Vector Clock？
※區塊鏈的原理是什麼？