Efficient at-most-once messages based on synchronized clocks

Abstract

This paper describes a new at-most-once message passing protocol that provides guaranteed detection of duplicate messages even when the receiver has no state stored for the sender. It also discusses how to use at-most-once messages to implement higher-level primitives such as at-once-remote procedure calls and sequenced bytestream protocols. Our performance measurements indicate that at-most-once RPCs can provide at the same cost as less desirable forms of RPCs that do not guarantee at-most-once execution. Our method is based on the assumption that clocks throughout the system are loosely synchronized. Modern clock synchronization protocols provide good bounds on clock skew with high probability; our method depends on the bound for performance but not for correctness.