Efficient synchronization of clocks in a distributed system

A probabilistic clock synchronization algorithm is proposed 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