拜占庭将军问题_realpanda_的博客-爱代码爱编程
问题背景
1982年,图灵奖获得者兰波特提出的一个虚拟问题。
若有一个美丽的城堡,拜占庭帝国想进攻这个城堡,并且派出了很多支军队去进攻。由于通讯较为落后,各支军队在进攻前只能通过信使来互相交流信息。
城堡非常的坚固,假设足以抵挡2,3支军队的同时进攻。但若军队若同时进攻,城堡就会沦陷。
于是拜占庭帝国各支部队的将军们就想用投票的方式决定一个时间一起进攻。(举例:若同意明天日出时进攻的首脑人数超过半数,那明天日出时所有部队都要进攻,若没到半数,那就都不会在日出时进攻。)但这个方法有个问题,可能军队中会有胡说八道的叛徒,比如有7支部队(有一支部队的将军是叛徒)包围了这个城堡,3个忠诚的将军觉得日出时不应该进攻,应该撤退。另外3个忠诚的将军觉得日出时要进攻,此时叛徒的意见就十分重要!
叛徒假设叫张三,张三会让信使去告诉3个想进攻的将军他也投进攻票;让信使告诉另外3个想撤退的将军他投的撤退票。这样想进攻的将军自以为进攻的主意拿了4票,多余半数,因此他们会进攻;想撤退的将军觉得撤退的主意拿了4票,于是他们会准时撤退。
如此一场战斗就会有3支部队进攻,3支部队撤退,以失败告终。