Efficient synchronization of clocks in a distributed system

The authors propose a probabilistic clock synchronization algorithm where processors in the system exchange time stamps and synchronize to a common clock value. Most of the previous algorithms for this problem have been based on a master-slave approach where all the slave processors synchronize to the clock value of a master. These algorithms are not distributed in nature and some of the assumptions made in these algorithms may become invalid if a large number of slaves try to synchronize with a master. The only distributed algorithm that is available was earlier proposed by A. Olson and K. G. Shin (1991). It is based on finding a cyclic path connecting the processors in the system and exchanging time stamp messages through this path. For the same level of synchronization accuracy, the proposed algorithm uses a much smaller number of messages than the algorithm of Olson and Shin.