0
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ Have you seen any formal description of the problem? This should clear out all difficulties. $\endgroup$ Dec 9, 2020 at 7:18
  • $\begingroup$ What I'm trying to do here is to have an accessible summary so others don't have to wade through abstract academic drivel which doesn't address most of the above points in a clear way, at least the accounts I've found. $\endgroup$
    – bumble
    Dec 9, 2020 at 13:28
  • $\begingroup$ Regarding your example: B doesn't know that A knows that B got his ack. So for all B knows, A might think B didn't get his ack, and thus A might not attack. Meaning B will not attack. And this goes on forever. $\endgroup$
    – Tassle
    Dec 9, 2020 at 17:15
  • $\begingroup$ That's what I tried to explain: A might think B didn't get his last ack, but A knows B got the ack before, which is sufficient for a general.Thus a better illustration for the problem wouldn't allow for this. $\endgroup$
    – bumble
    Dec 9, 2020 at 17:59
  • 2
    $\begingroup$ Sorry but your explanations about the weaknesses of the descriptions seem... vague. $\endgroup$
    – user16034
    Nov 4, 2022 at 11:56

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 Nth message.
    • T2) The other general receives the Nth 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.