Gradient clock synchronization in dynamic networks

ABSTRACT

Over the last years, large-scale decentralized computer networks such as peer-to-peer and mobile ad hoc networks have become increasingly prevalent. The topologies of many of these networks are often highly dynamic. This is especially true for ad hoc networks formed by mobile wireless devices.

In this paper, we study the fundamental problem of clock synchronization in dynamic networks. We show that there is an inherent trade-off between the skew S guaranteed along sufficiently old links and the time needed to guarantee a small skew along new links. For any sufficiently large initial skew on a new link, there are executions in which the time required to reduce the skew on the link to O(S) is at least Ω(n/S).

We show that this bound is tight for moderately small values of S. Assuming a fixed set of $n$ nodes and an arbitrary pattern of edge insertions and removals, a weak dynamic connectivity requirement suffices to prove the following results. We present an algorithm that always maintains a skew of O(n) between any two nodes in the network. For a parameter S=Ω(√Án), where Á is the maximum hardware clock drift, it is further guaranteed that if a communication link between two nodes u, v persists in the network for Θ(n/S) time, the clock skew between u and v is reduced to no more than O(S).

REFERENCES

• 1: H. Attiya, D. Hay, and J. Welch. Optimal clock synchronization under energy constraints in wireless ad-hoc networks. In Proc. of 9th Int. Conf. on Principles of Distributed Systems (OPODIS), pages 221--234, 2005.
• 2: Hagit Attiya , Amir Herzberg , Sergio Rajsbaum, Optimal Clock Synchronization Under Different Delay Assumptions, SIAM Journal on Computing, v.25 n.2, p.369-389, February 1996 [doi>10.1137/S0097539794266328]
• 3: Saâd Biaz , Jennifer L. Welch, Closed form bounds for clock synchronization under simple uncertainty assumptions, Information Processing Letters, v.80 n.3, p.151-157, November 15, 2001 [doi>10.1016/S0020-0190(01)00151-X]
• 4: Danny Dolev , Joseph Y. Halpern , Barbara Simons , Ray Strong, Dynamic fault-tolerant clock synchronization, Journal of the ACM (JACM), v.42 n.1, p.143-185, Jan. 1995 [doi>10.1145/200836.200870]
• 5: Danny Dolev , Joseph Y Halpern , Raymond H Strong, On the possibility and impossibility of achieving clock synchronization, Journal of Computer and System Sciences, v.32 n.2, p.230-250, April 1986 [doi>10.1016/0022-0000(86)90028-0]
• 6: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844143]
• 7: R. Fan, I. Chakraborty, and N. Lynch. Clock synchronization for wireless networks. In Proc of 8th Int. Conf. on Principles of Distributed Systems (OPODIS), pages 400--414, 2004.
• 8: Rui Fan , Nancy Lynch, Gradient clock synchronization, Distributed Computing, v.18 n.4, p.255-266, March 2006 [doi>10.1007/s00446-005-0135-6]
• 9: Dilsun K. Kaynar , Nancy Lynch , Roberto Segala , Frits Vaandrager, The Theory of Timed I/O Automata (Synthesis Lectures in Computer Science), Morgan & Claypool Publishers, 2006
• 10: F. Kuhn and R. Oshman. Gradient clock synchronization using reference broadcasts. arXiv:0905.3454v1, 2009. http://arxiv.org/abs/0905.3454v1.
• 11: Leslie Lamport , P. M. Melliar-Smith, Synchronizing clocks in the presence of faults, Journal of the ACM (JACM), v.32 n.1, p.52-78, Jan. 1985 [doi>10.1145/2455.2457]
• 12: Christoph Lenzen , Thomas Locher , Roger Wattenhofer, Clock Synchronization with Bounded Global and Local Skew, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.509-518, October 25-28, 2008 [doi>10.1109/FOCS.2008.10]
• 13: Christoph Lenzen , Thomas Locher , Roger Wattenhofer, Tight bounds for clock synchronization, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada [doi>10.1145/1582716.1582730]
• 14: T. Locher and R. Wattenhofer. Oblivious gradient clock synchronization. In Proc. of 20th Int. Symp. on Distributed Computing (DISC), pages 520--533, 2006.
• 15: J. Lundelius and N. Lynch. An upper and lower bound for clock synchronization. Information and Control, 62(2/3):190--204, 1984.
• 16: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 17: Keith Marzullo , Susan Owicki, Maintaining the time in a distributed system, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.295-305, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806730]
• 18: Rafail Ostrovsky , Boaz Patt-Shamir, Optimal and efficient clock synchronization under drifting clocks, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.3-12, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301316]
• 19: Boaz Patt-Shamir , Sergio Rajsbaum, A theory of clock synchronization (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.810-819, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195466]
• 20: T. K. Srikanth , Sam Toueg, Optimal clock synchronization, Journal of the ACM (JACM), v.34 n.3, p.626-645, July 1987 [doi>10.1145/28869.28876]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms; Network problems

General Terms:
Algorithms, Theory

Keywords:
clock synchronization, distributed algorithms, dynamic networks