[cap-talk] impossibility of solving the "coordinated attack problem" ("generals problem")

Jed at Webstart donnelley1 at webstart.com
Thu Feb 2 17:14:53 EST 2006


At 04:04 AM 2/2/2006, Ben Laurie  wrote:
>Jed at Webstart wrote:
> > There is a simple proof that: no fixed length protocol exists: Let P be
> > the shortest such protocol. Suppose
> > the last messenger in P gets lost. Then either this messenger is useless
> > or one of the generals doesn't
> > get a needed message. By the minimality of P, the last message is not
> > useless so one of the general
> > doesn't march if the last message is lost. This contradiction proves
> > that no such protocol P exists.
>
>Amusingly, this is the root of my issue with the bogosity of the proof
>previously cited. That version doesn't include the words "fixed length".
>Adding them would cure my objection (which is, in essence, that assuming
>the B reacts the same whether they receive the last packet or not is bogus).
>
>Of course, almost no fixed length protocols to do anything useful exist,
>IMO, so the value of this proof is eluding me.

Nope.  I don't think you're getting it.  The term "fixed length" is
pretty meaningless in the above.  What it really means is
that it is NEVER possible to come to agreement, to do the
"coordination" and to have both entities agree.  I think perhaps
an algorithmic approach is the best way to clarify the fundamental
problem.  You really have to put yourself in the position of the
boss or the lieutenant.  Let's try laying out possible algorithms:

The boss can use the algorithm:
      a.  Make a decision.
      b.  Send the messenger.
      c.  Execute the decision.

and the lieutenant can use the algorithm:
      a.  Wait for the messenger
      b.  If/when the messenger arrives, execute the decision.

I think we should be able to agree that the above leaves the
boss vulnerable.  If the messenger doesn't make it, he goes
to jail (failure).  With the above the lieutenant is safe, at least
from jail.  His only vulnerability is to not executing the plan
when he should have.

Now put in the first ack:

The boss uses the algorithm:
      a.  Make a decision.
      b.  Send the messenger.
      c.  Wait for the ack.
      d.  If the ack arrives, execute the decision.

In that case the lieutenant uses:
      a.  Wait for the messenger
      b.  If/when the messenger arrives:
      c.  Send the ack messenger and execute the decision.

Are we agreed that in the second case it is the lieutenant
that is vulnerable?  Just as vulnerable as the boss was with
the first approach?  Perhaps it is the role of lieutenants to
take the fall and one should prefer this approach, but I hope
we are clear that, whether the messages get through or
not there is no "coordination".  The lieutenant just sends off
his "ack" messenger and hopes that he gets through.  If
he doesn't get through the lieutenant goes to jail.  There is
no coordination.

Now add one more ack:

The boss uses the algorithm:
      a.  Make a decision.
      b.  Send the messenger.
      c.  Wait for the ack.
      d.  If the ack arrives, send the ack for the ack and execute 
the decision.

In that case the lieutenant uses:
      a.  Wait for the messenger
      b.  If/when the messenger arrives:
      c.  Send the ack messenger
      d.  Wait for the ack to the ack.
      e.  If the ack to the ack arrives, execute the decision.

In that case it is again the boss who is vulnerable.  Do you
see that if the ack to the ack doesn't arrive, the lieutenant
will not execute the decision and the boss goes to jail?  In all
these cases with N messages, the first N-1 are really of
no consequence if they get through.  The only message
of consequence is the last.

Are we clear?  It really sounded to me like you weren't understanding
Ben.  However, I suppose it could be a terminology problem.  Let
me know.  I'll respond to some of the individual pieces of your
message, but I believe the essence is above.

>...
> > 5.  The boss can send an ack for the ack  to assure the lieutenant
> > but ...
>
>There's only a "but" if it doesn't arrive. If it arrives, then everyone
>is happy.

No, they aren't.  The boss only sends the ack (actually an ack ack)
if the lieutenant's ack DOES arrive.  However, when that first
ack from the lieutenant arrives (assuming it successfully does),
the Boss knows that the lieutenant got the "GO" message and
he knows that he successfully received the ack.  However, he
knows that the lieutenant does NOT know whether or not he
received that ack.  Please see the algorithms above.

>If people are prepared to continue sending messages
>indefinitely then they will either end up agreeing or sending messages
>forever.

No.  They will never get an agreement no matter how many messages
they send.  It will always be the case that the last one to send a
message will not know whether or not it arrived.  Since that last
one can only safely act if he knows that his message did arrive,
the coordination cannot be accomplished.

I really don't think you're understanding the essence of the
problem here Ben.  Try to put yourself into the position of
the two gangsters or generals.  Remember that the plan will
only work if you both execute it at the agreed upon time.
You have to ask yourself what scheme (algorithm) you
will use to come to agreement to execute the plan.  If
you believe such an algorithm is possible, please describe
it in your reply.

>This is the point of the proof - you can't _guarantee_ an
>agreement, but in practice you will often get one.

No, you will never get one.  You can guarantee (prove as
above) that you will never get an agreement.  One side or
the other will just have to act without knowing whether their
messenger got through, knowing full well that if that messenger
didn't get through then they will be acting alone and assured of
failure.  That's the basic problem.  Get it?


> > ...
> > The lieutenant could say, "Did you hear me Boss?  I got it, we're
> > GO!".  If he doesn't hear back from the Boss, what does he do?
>
>And here we hit the bogosity again: if the telephone _doesn't_ go dead,
>and the boss says "roger that", then we're done, everyone knows its go,
>and no-one goes to jail.

Nope.  See above.  Whether the telephone goes dead or not, one
side or the other must act without knowing they have coordination.

> > Even without the telephone going dead the ambiguity is always
> > present.  The Boss can hear the acknowledgement and say,
> > "Yeah, I heard you.  We agree that we're GO.  Do you hear
> > me?", etc.  In real human communication the conversation
> > would terminate quickly with both the Boss and the lieutenant
> > satisfied that they've coordinated the heist, but have they?
> > Who spoke last?  The one who spoke last doesn't know for
> > sure that the heist is on.
>
>Again, not so. If the appropriate bad things happen, they may not know.
>But if all goes well they do know.

No.  That's exactly the point of this proof.  They never know.  They
have to act without knowing and take a chance that their last
message arrived.  If it didn't arrive, they will fail (go to jail, lose
the battle...).

>I'll stop banging on it now.

Sadly I think some more banging is needed.

Try the algorithmic approach above to see if that helps.

--Jed http://www.webstart.com/jed/ 



More information about the cap-talk mailing list