【二期一团Day03-田康】拜占庭将军问题详解

fzj5127

图来自于新生大学周兵老师，再一次感谢周兵老师。

有一个问题，那就是10支军队中可能有叛军。拜占庭将军问题有解的情况在于，若叛徒数为m，当且仅当将军总数n>=3m+1时才有解。10支军队，叛徒最多只能有3个，否则这个问题无解。

1: 叛徒数为m，当且仅当将军总数n>=3m+1时才有解。

3: 所有将军将按照收到的1或0最多的个数执行进指令。比如，收到1比0多则进攻，收到0比1多则不动。因为会收到奇数的信息，所以不存在收到1和0同样次数的情况。

当有1个叛徒时，如果是忠将A发出1给B,C,D时，B是叛徒，B发送0给C,D，但是因为C,D最后收到的1都是2次，而0是1次，因此C,D最后都会进攻，A会进攻，因此会有A,C,D进攻，叛徒B会不动。

如果叛将是A,那么将A向B,C,D发出0时。则A,B,C,D都不动，注意，拜占庭将军问题并不要求必须进攻打胜，而是要求能够在进攻的时候打下城池，如果都不动，已方没有损失，所以算达成了不动的共实。拜占庭将军问题的本质是所有将军达成进攻或者不动的共识，而不是只管进攻。

如果叛将是A,那么将A向B发出1时，A向C,D发送0时。注意，这里因为B会收到C,D的0,因此,B收到2次0，1次1，因此B也会不动，C,D也会不动。因此，第二种情况，A,B,C,D依然是不动。

如果叛将是A,那么将A向B,D发出1时，A向C发送0时。这时如下图所示：

file:///Users/bebold/Desktop/Screen%20Shot%202017-09-27%20at%204.30.26%20PM.png?lastModify=1506502489

有心的读者可以自己去推导。

通过三个要求.

2: 所有将军派信使对其它所有将军发出动作的信息，进攻命令=1, 按兵不动=0.

这种共识机制可以有效的确保进攻的军队能够要么不动，要么一举攻下敌人的城池。

同时，你也应该发现这一问题解决的多么精精妙了！

周兵老师在新大的课讲得真心非常好，在新生大学app上可以听，欢迎来听。