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

Jed at Webstart donnelley1 at webstart.com
Thu Feb 2 20:27:13 EST 2006


At 04:51 PM 2/2/2006, David Hopwood wrote:
>...
>It seems to me that the significance of this result is often 
>overstated, though.

In what sense?  Perhaps if I've been misstating it's significance during this
thread then I can be corrected and tone down the discussion.

>The purpose of using an unreliable channel (or a less reliable one), 
>is usually
>that such channels are less expensive, and so using them reduces the average
>cost of some kind of transaction.

I'm not sure how the cost factors apply.  Are you suggesting that since
networks are pretty reliable these days, the coordination can simply be:

boss:  Send the "GO" or "NO GO" and then act accordingly at the
appropriate time and

lieutenant:  Wait for the "GO" or "NO GO" and then act accordingly.

If the boss is confident that any message will get through then this
is safe.  It leaves the boss vulnerable to the loss of the message, but
if that won't happen, then no problem.  The way the problem is stated
of course there is concern about the vulnerability of the messengers
to attack, possibly even the surrounding of one location or the other.

>The result doesn't preclude the existence of protocols in which the outcome
>is either that two parties agree on an outcome, or (with low probability) that
>one party thinks that the protocol completed successfully and the other party
>*knows* that it hasn't.

To me it seems that any time somebody says something like "either that
the two parties agree on the outcome..." people stop at that point and think
that it's possible to get agreement on the outcome.  You can make a decision
such as the boss above just deciding to act after sending the one message,
even though he doesn't know that it got there.  If the lieutenant receives
the message then is that what you mean by "agreement"?  They agree
but they don't know they have agreement?  Knowing that they have
agreement ("coordination") is of course the essence of this problem.

As I've said, the last one to send a message can't know that it was
received and is necessarily in an ambiguous situation. I'd be interested
to hear the protocol that you refer to above where "either that two parties
agree on an outcome, or (with low probability) that one party thinks that
the protocol completed successfully and the other party *knows* that it
hasn't."  How can either party *know* that the protocol hasn't completed
successfully - even if you know something about probabilities of
messengers getting through.

I'm not sure what model you're using when you discuss probability.
If I can control the network (e.g. the situation typically of concern with the
gangsters/generals problem) then I believe I can choose to partition the
network at such a time as to insure that there is no coordination.  That
is, that the wrong action will be taken - given that I know the algorithms
used by both ends ahead of time.  There are no probabilities involved
in that case.

Perhaps you're discussing a case like Sandro referred to?:

At 04:23 PM 2/2/2006, Sandro Magi wrote:
>I think Ben's point is that you can *practically* achieve your goal 
>(eg. robbing the bank) the majority of the time (the "expected 
>value"), but as the proof demonstrates, you can't guarantee a 100% 
>success rate. Thus, "practically" in this case means "statistically".
>
>In other words, if you know 1 out of every 5 of your runners gets 
>nabbed by the cops, you have a high chance of success if you send 
>out more than one and assume at least one got through. This assumes 
>they can each take separate routes though such that the probability 
>of one being nabbed is independent of the others.

In that case you may as well just send out your multiple runners (depending
on how much you can afford) and not deal with acks.  You won't know that
one got through, but statistically you can figure the probability that one
will.  No need for any acks - they don't help.  Transmit and pray.

I think you see the essential difficulty of the coordination problem if you
try to use acks - e.g. in a case like the above.  In that case you can send
out multiple runners and acks for each that gets through.  In that case it
just becomes transmit (acks) and pray on the part of the receiver.  If you're
the receiver in that case you probably want to send as many acks as you
can afford if any message comes through from the boss.  In that case it
is the lieutenant that is vulnerable and just hopes that at least one of his
acks gets through.

If the cops/enemy have either location surrounded and can let through only
what they wish (either initial messages or acks),  then if they know 
the algorithm
they can control the result.  In the case of a TCP-like algorithm they let
out all the messengers but block all the acks.   The lieutenant acts but the
boss doesn't.

Using probabilities even for packet losses has always seems pretty
questionable to me.  In my experience they either almost all get through
or they almost all fail to get through (e.g. congestion, partitioning, etc.).
Losing a packet here and there has always seemed me to be the exception
rather than the rule.  I can easily imagine, however, that others have had
different experiences.

>Suppose, then, that the parties delay acting on the outcome for some time T.
>This gives the party that knows that the protocol did not complete 
>successfully,
>time T in which to attempt to communicate this, over channels that may be more
>reliable or have different failure modes to the original channel.

You can delay the last message, but you can't avoid it.  TCP retries 
and timeouts
act much like the above, but still there is that last packet.

Fortunately most of our communication isn't of the "coordination problem"
sort and most of our messages are delivered.  Like this message.  It 
doesn't really
matter so much if it gets delivered to others on the list or not - 
fortunately ;-)

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



More information about the cap-talk mailing list