Gradient Clock SynchronizationRui Fan & Nancy LynchIntroduction In the classical distributed clock synchronization problem, a set of
nodes communicate over a reliable network with bounded message delay.
Each node is equipped with a hardware clock with bounded drift, that is,
a timer running at roughly the rate of real time. Each node continuously
computes logical clock values based on its hardware clock, and on messages
exchanged with other nodes. The goal is to synchronize the nodes' logical
clocks as closely as possible. To rule out trivial algorithms, the logical
clocks must satisfy some validity conditions, for example, that they remain
close to real time. Classical distributed clock synchronization is a global
optimization problem, where the goal is to minimize the clock skew between
any pair of nodes in the entire network. However, many important types
of networks studied today, such as ad-hoc or sensor networks, exhibit
a high degree of locality: nearby nodes in the network need to coordinate
their actions more closely than faraway nodes. In such networks, it is
useful to study a more local measure of clock synchronization. To do so,
we introduce the gradient clock synchronization (GCS) problem.
Intuitively, gradient clock synchronization requires that nodes be better
synchronized the closer they are to each other. More precisely, we define
the distance To see that GCS is an interesting property, consider the TDMA medium access control protocol for broadcasting in a radio network. Neighboring nodes in the network synchronize their clocks, then agree to non-overlapping time schedules to perform their radio broadcasts. Because only messages from nearby nodes can collide, only nearby nodes need to maintain tight clock synchronization. On the other hand, a lower bound on the tightness of clock synchronization between neighbors imposes a lower bound on the granularity of the broadcast schedule. Thus, the efficiency of TDMA is directly related to upper and lower bounds for gradient clock synchronization. Progress In a network consisting of two nodes which are distance d apart,
the nodes can easily synchronize their clocks to O(d). When there
are more nodes, can we ensure that all pairs of nodes have clock skew
which is linear in their distance? We proved the answer is no
[1], and that in any network of diameter D (that is, there
exist two nodes in the network which are distance D apart), some
pair of nodes which are only O(1) distance apart have clock skew
Future WorkOur lower bound differs from many previous distributed computing lower bounds in that it considers an online problem with continuously arriving inputs (in this case, the input are the hardware clock values corrupted by drift), instead of a problem in which all the input is given at the beginning. We think that online inputs accurately model many distributed computing tasks, and that our lower bound techniques can extend to such problems. Similarly, we think that techniques used in our gradient clock synchronization algorithm, which rely only on local information and control, may be adapted to solve a variety of online network problems. References:[1] Rui Fan, Nancy Lynch. Gradient Clock Synchronization. In Proceedings of the Twenty-Third Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing , pp. 320--327, St. John's, Newfoundland, Canada,July, 2004. [2] Rui Fan, Indraneel Chakraborty, Nancy Lynch. Clock Synchronization for Wireless Networks. In OPODIS 2004: 8th International Conference on Principles of Distributed Systems , Grenoble, France, December 2004. |
||
|