Jennifer Lundelius and Nancy Lynch

The problem of synchronizing clocks of processes in a fully connected network is considered. It is proved that, even if the clocks all run at the same rate as real time and there are no failures, an uncertainty of epsilon in the message delivery time makes it impossible to synchronize the clocks of n processes any more closely than epsilon*(1 - 1/n). A simple algorithm is given that achieves this bound.