patternMinor
Two Generals problem - what if we set boundary conditions, and then layer redundant messages once they've been met?
Viewed 0 times
onceproblemlayergeneralsmetwhatbeenredundanttwoboundary
Problem
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 ge
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 ge
Solution
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.
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.
Context
StackExchange Computer Science Q#124461, answer score: 2
Revisions (0)
No revisions yet.