Synchronizing Time Servers

When I joined DEC in 1985, they were the world leader in networking. Using their VMS operating system, I could type a simple copy command to a computer in California, specifying a file and machine name, to copy a file from a computer in Massachusetts. Even today, I can’t copy a file from Massachusetts to California nearly as easily with Unix or Windows.

The people responsible for DEC’s network systems were the Network and Communications group (NAC). Around 1987, NAC asked for my help in designing a network time service. I decided that there were two somewhat conflicting requirements for a time service: delivering the correct time, and keeping the clocks on different computers closely synchronized. This paper describes the algorithms I devised for doing both.

I withdrew the paper because Tim Mann observed that the properties I proved about the algorithms were weaker than the ones needed to make them interesting. The major problem is that the algorithms were designed to guarantee both a bound epsilon on the synchronization of each clock with a source of correct time and an independent bound delta on the synchronization between any two clocks that could be made much smaller than epsilon. Mann observed that the bound I proved on delta was not the strong one independent of epsilon that I had intended to prove. We believe that the algorithms do satisfy the necessary stronger properties, and Mann and I began rewriting the paper with the stronger results. But that paper is still only partly written and is unlikely ever to see the light of day.