PROBABILISTIC CLOCK SYNCHRONIZATION IN LARGE DISTRIBUTED SYSTEMS

Clock synchronization within a distributed system is a problem that ha s been studied extensively in recent years. Of the many solutions prop osed thus far, probabilistic synchronization algorithms provide arguab ly the best compromise between tightness of synchronization and overhe ad imposed on the system. The main drawbacks of probabilistic algorith ms are the requirement of a master/slave organization of clocks, and t he relatively high number of synchronization messages that must be sen t. These two drawbacks can make them unsuitable for use in large distr ibuted systems. In this brief contribution, we propose a synchronizati on algorithm that does not use master/slave clocks and reduces the num ber of synchronization messages needed. The nodes of the system are di vided into a number of overlapping groups. Within a group, each node u ses one of two probabilistic techniques to estimate the values of othe r clocks in the group, and uses an interactive convergence algorithm o n the resulting estimates to adjust its local clock. Groups are select ed so that the maximum skew between any two group members is bounded.