Presents and analyzes a new probabilistic clock synchronization algorithm that can guarantee a much smaller bound on the clock skew than most existing algorithms. The algorithm is probabilistic in the sense that the bound on the clock skew that it guarantees has a probability of invalidity associated with it. However, the probability of invalidity may be made extremely small by transmitting a sufficient number of synchronization messages. It is shown that an upper bound on the probability of invalidity decreases exponentially with the number of synchronization messages transmitted. A closed-form expression that relates the probability of invalidity to the clock skew and the number of synchronization messages is also derived.>

Presented is an averaging probabilistic clock-synchronization algorithm that is based on the redundant transmission of multiple synchronization messages. The algorithm can guarantee a much lower upper bound on the deviation between clocks than can most existing algorithms. The algorithm is probabilistic in the sense that the upper bound on the deviation that it guarantees has an associated probability of invalidity. The probability of invalidity, i.e. the probability that the deviation exceeds the guaranteed maximum deviation, may be made extremely small by sufficiently increasing the number of messages transmitted. It is proved that an upper bound on the probability of invalidity decreases exponentially with the number of messages, i.e. the probability of invalidity itself decreases exponentially or better.>