Achieving Global Synchrony in a Distributed System with Free-Running Local Clocks
Achieving Global Synchrony in a Distributed System with Free-Running Local Clocks
Files
Publication or External Link
Date
2006-11-27
Authors
TRINH, MICHAEL
Advisor
AGRAWALA, ASHOK
Citation
DRUM DOI
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.