Introduction

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 between nodes i and j to be the uncertainty in the message delay between i and j. Let denote the logical clock value of node i at time t . Then GCS requires that, for all nodes i, j and at all times t , the clocks satisfy , where f is some nondecreasing function. The goal is to minimize f .

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 . This implies that clock synchronization is not a local property, and that the clock skew between a particular pair of nodes depends on the entire network they reside in. This means that a protocol like TDMA must use coarser broadcast granularity as the network grows later, even if the degree of each node remains constant. On the positive side, we exhibit an algorithm in which all O(1) distance nodes have clock skew, and another algorithm in which such nodes have O(1) skew most of the time [2]. These algorithms significantly improvement most existing clock sychronization algorithms, which contain executions in which O(1) distance nodes can have O(D) skew.

Future Work

Our 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.