In all these papers the message transmission times (called, for short, delays) are assumed to be deterministic, and the performance of algorithms is measured by the worst case with respect to delays. The following negative result is due to Lynch and Lundelius (1985). Even for a completely connected network with k processors, k 1 2, and with delays taking away values between L and H, no algorithm can synchronize the clocks better than 6 2 (H -L)(k -1)/k, no matter how many messages are sent. Since (H -L)/2 5 6 5 H -L, it is impossible to synchronize the clocks if H -L is large.
In this paper we study the clock synchronization problem with random delays. Our work is motivated by the concluding section of the paper by Halpem et al. (1985) which states, "In practice, of course, message transmission times are best viewed as being randomly chosen from a probability distribution. . . . Finding the best strategy for processors to follow to achieve optimal precision as a function of the probability distribution on message delivery time remains a completely open problem."
As in (Halpern et al., 1985; Lynch and Lundelius, 1983, we view a network as an indirect strongly connected graph with nodes representing processors, and edges representing communication links. Each processor Pi has a local nondrifting clock Di running at the rate of real time. Thus,