Re: Guaranteed duplicate elimination vs. upper bound on delays

[Dan Weinreb <dlw@exceloncorp.com>]

   Date: Wed, 15 Aug 2001 10:04:30 -0400
   From: christopher ferris <chris.ferris@east.sun.com>

   Marty,

   persistDuration and time-to-live are orthogonal. A persistDuration
   may need to exceed time-to-live to address messages that are received
   after some delay related to their delivery. 

   persistDuration is a function of the receiver, not the sender.

Maybe orthogonal but not unrelated, in the scheme we're suggesting.
It's fine for persistDuration to be greater than time-to-life;
less-than is the problem.

A receiver is free to garbage collect a message ID once it has held
the message ID in persistent storage for any amount of time greater
than persistDuration.

It seems to me that this means that if a message can languish in the
network for longer than persistDuration, the receiver might violate
its promise to be OnceAndOnlyOnce.  The scenario is: the From Party
MSH, operaing in reliable OnceAndOnlyOnce mode, sends a message at
time T1.  The message falls into a hole (the head-crashing
store-and-forward mailer that I mentioned in earlier mail).  The From
Party MSH eventually sends the message again at time T2.  The To Party
MSH receives the message at time T3 and stores its message ID
persistently.  At time T4, it garbage collects that message ID.  At
time T5, the mailer gets fixes and transmits the original message, and
when the To Party MSH it fails to perform duplicate-elimination,
breaking its OnceAndOnlyOnce guarantee.

T2 > T1 + retransmission interval
T3 > T2 
T4 > T3 + persistDuration
T5 > T4
T6 > T5 

We're suggesting that one way to deal with these waylaid messages is
to use a time-to-live field, and make sure that the value of the
time-to-live is less than the sum of the retransmission interval and
persistDuration, so that when the waylaid message finally arrives, it
will be ignored.

-- Dan