A clock synchronization problem with random delays (Q1121019)

The clock synchronization problem is the problem to find an algorithm which shifts the clocks so that the error, i.e., the largest difference between any two shifted clocks, is possibly small. To synchronize the clocks, processors communicate by sending local clocks readings. The time to transmit a message is considered to be a random variable with a known probability distribution. It is assumed that the delays are identically distributed on each communication link, and that the clocks do not drift. The following questions are examined: (1) For a network with k processors and a fixed number n, what is the minimal average error among all algorithms that use n messages? (2) What is the algorithm whose average error is minimal? For the case of two processors the n-th minimal error is derived and the optimal algorithm is described. For the general case of k processors, lower and upper bounds are determined for the n-th minimal error, and a near optimal algorithm is described. The algorithms are free of deadlocks, robust in a specific sense, and can be implemented so that all messages except k-1 are single bit messages. The algorithms are fully parallelizable.