3
$\begingroup$

apologies if this is in wrong place (very new to CS). I know there must be some flaw in my reasoning here, but I can't quite see it. Here's how I've stated the problem.


There are two generals, A and B. Messages start from A with a request M and B replies with an agreement N. Thereafter, the generals must exchange acknowledgements An and Bn of message reception. That is, after receiving N, A will send A1; upon receiving A1, B will send B1; and so on.

M reads:

Attack at time X. Once I receive your reply, we will begin exchanging the acknowledgments An and Bn. As soon as we both know that you have received A1, and we both know that I have received B1, we will consider the plan finalized and proceed.

  • M goes through. N is sent, agreeing to M.

  • A1 is sent, acknowledging M and N. B1 is sent, acknowledging M, N and A1.

  • A2 is sent, acknowledging M, N, A1 and B1. B2 is sent, acknowledging M, N, A1, B1, and A2.

  • So on for An and Bn

By the time Bn is sent, B knows the following: I've told A that I received A1 n times, and I know he heard me n-1 times. So he knows I received A1. At this same time, A knows the following: I've told B that I received B1 n-1 times, and I know he heard me n-2 times. So he knows I received B1. Recall that the boundary conditions for the attack were: As soon as we both know that you have received A1, and we both know that I have received B1, we will consider the plan finalized and proceed.

If we set n = 3, these conditions seem to be met. If we set n arbitrarily higher than that, it works.


As I understand it, the point of the Two Generals problem is that is that neither party is willing to proceed while the chance of the other proceeding is less than 100%. I also know that classically, each additional message increases the chance of a general proceeding asymptotically towards 100%. But if we set boundary conditions such as these, and then add some layers of redundant messages, there is some shared knowledge between the two generals, and the possibility that either one will not attack falls to 0? Have we not established that both generals know that the attack criteria have been met with 100% certainty?

I know this problem's unsolvable, so I must've made a mistake somewhere. I just can't see it.

$\endgroup$
4
  • $\begingroup$ You can make messages M and N common knowledge before the two generals go their own way. The first message can be simply yes from A to B whereupon General B must reply with yes. Take into account that there is an ε>0 chance for any message not to get through. $\endgroup$
    – Pål GD
    Apr 21 '20 at 14:23
  • $\begingroup$ Yes, with more rounds of messages that are successful, both generals will know that the attack criteria have been met with 100% certainty. However, there is always a time where one general should, according to the protocol, decide to attack without being sure of the other general's action. If all messages are lost after that time, you can see the problem. $\endgroup$
    – John L.
    Apr 22 '20 at 0:23
  • $\begingroup$ My confusion here was that if we reach a situation where A knows attack criteria have been met, and he knows that B also knows that, and he knows that B knows he knows that, he could say "I'm going to attack as per the criteria, and I'm expecting B to attack as per the criteria, and I know B knows I'm expecting him to do that. So he'll do it." B could similarly say "A has met the criteria and will attack, and he knows I've met the criteria so he expects me to attack. So I'll attack". Specifically, A knows that B cannot think of any reason why A should not attack at this point. $\endgroup$ Apr 22 '20 at 1:23
  • $\begingroup$ @GreyIsHerRaiment That situation, when both of them are sure the other side will attack, is, I agree, pretty satisfying. Indeed, it CAN happen. However, that does not mean your protocol works in all cases. Because of the nature of time, there must be a point of time when A and B first reaches that situation. Here is the critical question for you. Has one of them decided to attack before that point of time? If yes, what will happen in a parallel world where all later messages are lost? If no, which event caused both generals to decide at the same time to attack? $\endgroup$
    – John L.
    Apr 27 '20 at 23:58
2
$\begingroup$

Realize first that if General $X$ doesn't receive message $X_k$, then General $X$ must assume that General $Y$ didn't receive message $Y_{k-1}$.


Suppose that General $B$ does not receive the final message $B_n$. An important question is: Why is that?

In General $B$s mind, General $A$ didn't necessarily receive $A_{n-1}$. And that would be bad.

Suppose in this hypothetical scenario that $B$ believes that $A$ didn't receive $A_{n-1}$. That could be due to $B$ not receiving $B_{n-2}$. But why didn't $B$ in this scenario receive $B_{n-2}$. Well, possibly because $A$ didn't receive $A_{n-3}$.

That means that if $B$ doesn't receive $B_n$, $B$ must assume that $A$ assumes that $B$ assumes that $A$ didn't receive $A_{n-3}$ ... ad infinitum.

The problem here is that after $A$ and $B$ split, there is no more new common knowledge. A nice way of modeling this situation is with the use of possible worlds.

$\endgroup$
8
  • $\begingroup$ So I wonder here: let's follow the logic down. B does not receive B_n and assumes A didn't receive A_n-1. And yes, a reason that A hasn't received A_n-1 is because B never received B_n-2. Except - B knows that isn't possible right? B knows exactly which messages he has received, which includes B_n-2. Nor should A have any reason to believe B never received B_n-2, because B sent A_n-1 to A, which he may only have done if he received B_n-2. Where's the catch? I should note of course that this is assuming A_n-1 actually went through, regardless of what B thinks. $\endgroup$ Apr 21 '20 at 13:12
  • $\begingroup$ What is the requirement for both attacking? That they receive n messages or that they receive n-1 messages? $\endgroup$
    – Pål GD
    Apr 21 '20 at 14:19
  • $\begingroup$ Well, in the solution I proposed, it would only be one message each (M and N) as well as common knowledge that those two messages have been received (A1 and B1). See the attacking criteria I mentioned in my post. I think that if you ask A the following questions: 1) Do you know that B has received your A1? and 2) Does B know that you know this?, and similarly ask B: 1) Do you know that A has received your B1? and 2) Does A know that you know this?, and if the anwer to all four questions is "yes", then that should meet the attacking criteria they agreed to in M and N, yes? $\endgroup$ Apr 21 '20 at 14:29
  • $\begingroup$ But you cannot achieve common knowledge over a faulty line, that's the problem. Look at the Wikipedia article on the subject that I linked to. $\endgroup$
    – Pål GD
    Apr 21 '20 at 14:33
  • $\begingroup$ So, suppose that the deal is that if (and only if) M, N, A1, and B1 are received, the attack goes through. Now, suppose that B1 is never received by A. In that case, General B will attack, but General A will not. $\endgroup$
    – Pål GD
    Apr 21 '20 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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