An upper and lower bound for clock synchronization

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 ε in the message delivery time makes it impossible to synchronize the clocks of n processes any more closely than ε(1−1/n). A simple algorithm is given that achieves this bound