Two Generals' Problem: Difference between revisions

Revision as of 17:30, 23 February 2020

Revision as of 00:13, 13 March 2020

Line 29:

Because this protocol is [[Deterministic_system|deterministic]], suppose there is a sequence of a fixed number of messages, one or more successfully delivered and one or more not. The assumption is that there should be a ''shared certainty for both generals to attack''.

Consider the last such message that was successfully delivered. If that last message had not been successfully delivered, then one general at least (presumably the receiver) would decide not to attack. {{Citation needed|reason=There is probably an error in the proof. In original reference or only here? See Talk page for details.|date=May 2017}} From the viewpoint of the sender of that last message, however, the sequence of messages sent and delivered is exactly the same as it would have been, had that message been delivered.

Since the protocol is deterministic, the general sending that last message will still decide to attack.

Line 40:

Since ''P'' is finite, it then follows that the protocol that terminates before sending any messages would solve the problem. But clearly it does not. Therefore a nondeterministic protocol which solves the problem cannot exist.

===Proof by symmetry===

Because the problem is devised in such a way that the defender cannot be distinguished with one of the attackers, for all theoretical purposes the defender acts as one of the attackers but inverts the message of the other attacker. Since no message can distinguish the defender from one of the attackers it is impossible to coordinate. This can be seen by simply removing one attacker and treating the problem as two players that must coordinate but in which one always can thwart any coordination (through error or intent). The only solution to the problem is to be able to distinguish the defender from the attacker which solves the problem trivially.

These problems show up in many games such as chess where one player can always make a move that prevents the other from achieving an end goal such as perpetual check and which external "rules" must be imposed to get around it.

==Engineering approaches==