Paxos和Raft对节点的前提假设是不作恶,只是偶尔可能不响应而已。而真实情况是节点可能会作恶(伪造消息),在这样的场景下,如何在众多节点中达成一致性问题,这是拜占庭将军问题所要讨论的。
拜占庭将军问题,通过比喻的方式来描述分布式一致性中一类最难的问题:
假设将军总数3,叛徒将军数1.
提案人不是叛徒,提案人发送一个提案,叛徒收到后,回复不同的命令,对于第三个将军就收到两个相反的消息,也无法判断出谁是叛徒,系统无法达成一致。
提案人是叛徒,发送两个相反的提案给另外两个,另外两个收到两个相反的消息,无法判断究竟谁是叛徒,系统无法达成一致。
假设将军总数4,叛徒将军数1. 提案人不是叛徒,提案人发送一个提案,叛徒同样作恶,但受到的消息结果,能很容易就找出哪个节点是叛徒。从而快速达成共识。
提案人是叛徒,发送不同的提案给不同的节点,但其他三个节点之间进行通信后,他们自己也能达成一个共识。
Leslie Lamport证明,当叛徒不超过1/3时,存在有效的算法,不论叛徒如何折腾,忠诚的将军们总能达成共识。当叛徒超过三分之一时,则无法保证一定能达成一致性。 所以在前几期讲PBFT的时候说道,假设节点总数为N,f为拜占庭错误节点,N满足:N=3f 1。 也是为了满足这一特性。 共识算法的核心就是解决拜占庭将军问题(分布式网络一致性问题)。 所以在PAXO改进了以后,raft不能解决拜占庭将军问题,结合PBFT,设计一种基于PBFT的raft,解决拜占庭容错还能容纳故障节点。这是一个很好方向。欢迎猛戳讨论呀~ 参考: https://www.jianshu.com/p/8bcef0ca676c