# Coordinated Attack Problem On The Arbitrary Graph

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?

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.
• 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? – frafl Jun 7 '13 at 14:04
• @frafl, as a result, all $n$ generals should decide to attack or all $n$ generals should decide not to attack. – com Jun 7 '13 at 17:57
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.