两军问题
1. 问题描述
两军问题(Two Generals' Problem),也叫两军悖论(Two Generals Paradox)或协同进攻问题(Coordinated Attack Problem)。
摘自维基百科:
两支军队由不同将军领导,准备进攻一座坚固的城市。军队在城市附近的两个山谷扎营。由于有另一个山谷将两山隔开,两名将军只能透过派信使穿越山谷通信,但这山谷由城市护卫占领,有可能俘虏途径山谷传递消息的任何信使。
虽然两军已约定要同时进攻,但尚未约定进攻时间。要顺利攻击,两军必须同时进攻。如果同一时间仅一支军队进攻就会战败,因此两名将军须约定攻击时间,并确保对方知道自己同意了进攻计划。
军队位置示意图:军队甲(A1)与乙(A2)派遣信使互相通信,但信使可能被敌军(B)俘虏。
问题:如何在两名将军派出的任何信使都可能被俘虏的情况下,就进攻时间达成共识。