USING ADAPTIVE TIMEOUTS TO ACHIEVE AT-MOST-ONCE MESSAGE DELIVERY

We extend the at-most-once message delivery algorithm of Liskov, Shrir a, and Wroclawski to adapt dynamically to changes in message transmiss ion time and degree of clock synchronization. The performance of their algorithm depends on its being supplied with a good estimate of the m aximum message lifetime - the sum of the message delivery time and the difference in processor clock values between sender and recipient. We present two algorithms that are suitable for use in a system where th e message lifetime is unknown or may change, Our extensions allow the automatic and continuous determination of a suitable value for the max imum lifetime. We prove that whenever the actual message lifetime is b ounded, then our adaptive algorithms converge to an accurate estimate of its true value. Our two algorithms differ in the behavior they requ ire from the network and achieve different performance levels. Our for mal statement of convergence is expressed in terms of the number of me ssages received, rather than time elapsed, We show that this formulati on is necessary by proving that no method for estimating the lifetime can achieve convergence in a bounded amount of time.