Achieving Global Synchrony in a Distributed System with Free-Running Local Clocks

Abstract

In any distributed system, there is an intrinsic need to coordinate the events between the nodes. In such a system, even though each individual node only has access to its local clock, global coordination often has to be carried out the basis of time, called the global time, that is common to every nodes. One way to achieve this globally synchronous behavior is to synchronize all local clocks with an external time source such as a Cesium clock. Local time then becomes in effect global time. There are, however, several drawbacks to such clock synchronization method. Highly precise clocks are expensive and can add to the cost of the hardware node. Some approaches depend on network characteristics such as symmetric latency, broadcast medium, or bus structure. Many are also centralized in that they assume the existence of a master node, and this adds additional complexity in terms of redundancy or reconfiguration to handle failures. In this dissertation, we introduce a new method for achieving global synchrony without performing clock synchronization. In our approach, called the Cyclone Network Synchronization (CNS) scheme, the local clocks are free-running and are not modified in any way. CNS relies on the ability of each node to send data at a time of its choosing. Such data are sent at regular interval, with the next instance being determined based only on the local information available at the node. Once the scheme converges, the interval for all nodes becomes exactly the same, supporting a synchronous operation across the whole network. The scheme can be used in many synchronous cyclic networks, and does not require a broadcast medium or depend on a symmetric latency. CNS is a decentralized scheme, as all of the nodes execute the same set of instructions, and can tolerate most topology changes without the need to reconfigure. There is very little overhead since no explicit synchronization messages are sent. A high degree of accuracy can be achieved with the algorithm, and both clock drift as well as latency perturbation are tolerated. Furthermore, this accuracy is not a function of the clock drift rate.