3
$\begingroup$

Let consider a general version of Two Generals' Problem, when there are $n$ generals located on the arbitrary graph and they should agree on exactly the same value whether to attack or not to attack.

It's well known that Two Generals' Problem represents a version of the Consensus Problem with unlimited number of the stopping failures, I think this is the only reason why Two Generals' Problem and Generals' Problem (with $n$ generals) don't have solution.

There is a proof of lacking solution for Two Generals' Problem (can be found in the textbook of Lynch).

The following is the exercise from the textbook of Lynch, that I have not solved so far.

Show that a solution to the (deterministic) coordinated attack problem (Generals' Problem) for any nontrivial connected graph implies a solution for the simple graph consisting of two processes connected by one edge. (Therefore, this problem is unsolvable in any nontrivial graph.)

Apparently, there is a reduction from an edge case to graph. But how to show it mathematically rigorous?

Addendum:

Can I say something like this? When we are given the primary problem of Two Generals and they initial values $a_i$ (inclination whether to attack or not), we in arbitrarily add more dummy generals with the only requirement if $a_1=a_0=a$ for primary problem set all dummy's general input to $a$, otherwise set arbitrary input value $b \in \{0,1\}$. Find the solution on the graph, the solution on the graph is the solution for the primary problem.

$\endgroup$
  • $\begingroup$ You need a reduction from the single edge to an arbitrary graph. I'd assume you cannot choose the arbitrary graph, otherwise it would be trivial. Do all of your $n$ generals have to attack? Or can they agree on sending any set of armies? $\endgroup$ – frafl Jun 7 '13 at 14:04
  • $\begingroup$ @frafl, as a result, all $n$ generals should decide to attack or all $n$ generals should decide not to attack. $\endgroup$ – com Jun 7 '13 at 17:57
1
$\begingroup$

The easiest way to do the reduction is to decompose your graph into two pieces $G_1,G_2$ arbitrarily, let one general "play" $G_1$, and the other one $G_2$. Details left for you.

$\endgroup$

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.