Two Generals' Problem Definition

Question

I've read various descriptions of the TGP, most of which seem vague or conflicting on the precise constraints of the problem. Specifically:

• is it always or sometimes impossible to reach consensus
• finite/infinite messages required
• given unreliable communication, is actual message loss important or not.

As another point, the depiction of the problem seems inadequate, as there's no need for the generals to always require acknowledgement for their last message if they regard previous ones:

0 A ----time info--> B

1 A <---AckForA0---- B

2 A ----AckforB0---> B

3 A <---AckforA1---- B

1... A knows B received his time info and is ok with it but might not attack if he doesn't receive confirmation for his ack.

2... B knows A received his ack because he responded.

3... A knows B got his ack because he responded

Can anyone give a better example which illustrates this specific need to rely on acks of the respective last messages.

Answer 1

Whenever you think you have solved the two general problems, there is only 1 thing you need to do to find why your solution is wrong.

Take every step s_1...s_n of your algorithm and treat it as the final step before a permanent network failure. Does a general end up dead if any step s_i is the final step before total network failure? Then you haven't solved it.

A knows B got the ack before, which is sufficient for a general.

So if I understand correctly in your scenario, B upon receiving AckforB0 is now fully confident to charge into battle? Then let's say he gets it and then a permanent network failure happens. B sends messengers to A but none go through and A never becomes confident enough to ride into battle. So B goes into battle alone and dies.

If you try to argue that A should be confident enough to go to into battle at this step because he already received AckForA0 then all you've done is shifted the problem backwards. Now if A gets AckForA0 and a permanent network failure occurs then A will ride out to their death alone.

Answer 2

A lot of misunderstanding is caused by explaining the problem as an ongoing process. It's a lot easier to understand if one simply considers the possible states that the generals can be in.

Assume the generals have agreed that they will attack if they get at least N messages.

• B) Before both generals have received N messages, both know that they should not attack.
• A) After both generals have received N messages, both generals know that they should attack.
• T) Between those two states is a time interval during which:
  • T1) One general receives the N^th message.
  • T2) The other general receives the N^th message.

The problem is that T1 and T2 are independent.

Between T1 and T2 the generals are in a state where:

• One general knows that he should attack.
• One general knows that he should not attack.

If all communication is cut off within this period, everyone dies.