[cap-talk] "coordinated attack"/generals and TCP

[Jed at Webstart]

At 04:32 AM 2/2/2006, Lorens Kockum wrote:
>On Thu, Feb 02, 2006 at 12:04:54PM +0000, Ben Laurie wrote:
> > Jed at Webstart wrote:
> > > There is a simple proof that: no fixed length protocol exists:
>...
> > Of course, almost no fixed length protocols to do anything useful exist,
> > IMO, so the value of this proof is eluding me.
>...
> > There's only a "but" if it doesn't arrive. If it arrives, then everyone
> > is happy.

No - as I explain in my other message.  I believe focusing on
the "fixed length" notion is a mistake.  All it means is that
coordination (confidence by both sides that both sides
know what will happen despite any possible loss of
messengers) is not possible.

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

No.  As explained again in my last message, they can
never agree.  They can only choose to act without
agreement (coordination).  The last one to send a
message is always vulnerable.  That is, the last one
to send a message doesn't know if it arrived.

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

Nope.

>TCP and higher-level protocols such as SMTP strike me as having
>tackled the "non fixed-length" problem with quite noteworthy
>success.

The designers of TCP (I was there) well understood that
there could be no coordinated assurance at the ends on
whether a message was delivered or not.  At some point
there must be a timeout and the last one to send a message
is left in an ambiguous situation.

TCP takes the basic approach:

Sender:
    a.  Send a packet with a sequence number.
    b.  Wait for an ack.
    c.  If the ack doesn't arrive within some time
         either:
         i.  If a long timeout has expired, give up or
         ii.  If the long timeout hasn't expired go back
              to #a and retry the packet.

Receiver:
     a.  When a packet is received, send an ack.
     b.   Remember state for ~ the long timeout period
           and throw away retries during that time.

The long timeouts are set up so that packets won't be
retried after the receiver throws away the sequence
number state (going by long memory on this,
corrections solicited).

Suppose the generals/gangsters used the above
algorithm.  The message (packet) was either GO
or NO GO.  One then has to ask how the two
sides decide whether or not to act.  It might seem
most reasonable to have the receiver act if a single
packet arrives (TCPs definition of success) and the
sender act if a single ack arrives (again TCP's definition
of success).

However, this leaves the receiver vulnerable and
uncoordinated just as in the one ack case in my
previous message.  The receiver doesn't know whether
or not their last ack was received.  The sender may
send many packets and get back no acks.  At some
point they have to give up (e.g. after the time decided
upon for the attack).  At that point the receiver,
who may have received one or more of the messages,
will act and fail.

In practice (these days, it wasn't always so), after the
initial handshake, there is generally one packet sent
and one ack.  However, neither side can be assured
of "coordination" and know that both sides agree on
what happened.  While the receiver may have received
some packet, the receiver can never know if the sender
knows it was received.

>Synchrone database clusters and filesystem journaling
>also come to mind.

If they need to do "coordination" they have the same problem.

>Why should the protocol be "fixed length"?

At some point all protocols must time out.  That is when they
become vulnerable.  Consider the case of either TCP or
the generals/gangsters if one packet/message is sent and
then the network is partitioned.  When the time comes
for the attack, does it go off or not?  Nobody can be assured
that it's "coordinated".  That's the point of the "paradox"/problem.

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