Tight bounds for clock synchronization

ABSTRACT

We present a novel clock synchronization algorithm and prove tight upper and lower bounds on the worst-case clock skew that may occur between any two participants in any given distributed system. More importantly, the worst-case clock skew between neighboring nodes is (asymptotically) at most a factor of two larger than the best possible bound. While previous results solely focused on the dependency of the skew bounds on the network diameter, we prove that our techniques are optimal also with respect to the maximum clock drift, the uncertainty in message delays, and the imposed bounds on the clock rates. The presented results all hold in a general model where both the clock drifts and the message delays may vary arbitrarily within pre-specified bounds.

Furthermore, our algorithm exhibits a number of other highly desirable properties. First, the algorithm ensures that the clock values remain in an affine linear envelope of real time. A better bound on the accuracy with respect to real time cannot be achieved in the absence of an external timer. Second, the algorithm minimizes the number and size of messages that need to be exchanged in a given time period. Moreover, only a small number of bits must be stored locally for each neighbor. Finally, our algorithm can easily be adapted for a variety of other prominent synchronization models.

REFERENCES

• 1: Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
• 2: 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]
• 3: 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]
• 4: Rui Fan , Nancy Lynch, Gradient clock synchronization, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011815]
• 5: Matthias Fugger , Ulrich Schmid , Gottfried Fuchs , Gerald Kempf, Fault-Tolerant Distributed Clock Generation in VLSI Systems-on-Chip, Proceedings of the Sixth European Dependable Computing Conference, p.87-96, October 18-20, 2006 [doi>10.1109/EDCC.2006.11]
• 6: Saurabh Ganeriwal , Ram Kumar , Mani B. Srivastava, Timing-sync protocol for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958508]
• 7: B. Korte, D. Rautenbach, and J. Vygen. BonnTools: Mathematical Innovation for Layout and Timing Closure of Systems on a Chip. In Proceedings of the IEEE 95, pages 555--572, 2007.
• 8: Fabian Kuhn , Thomas Locher , Rotem Oshman, Gradient clock synchronization in dynamic networks, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada [doi>10.1145/1583991.1584059]
• 9: 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]
• 10: C. Lenzen, T. Locher, and R. Wattenhofer. Optimal Clock Synchronization with Bounded Rates. Technical Report 301, ETH Zurich, 2009. ftp.tik.ee.ethz.ch/ pub/publications/TIK-Report-301.pdf.
• 11: C. Lenzen, T. Locher, and R. Wattenhofer. Tight Lower Bounds for Clock Synchronization. Technical Report 299, ETH Zurich, 2009. ftp.tik.ee.ethz.ch/pub/publications/TIK-Report-299.pdf.
• 12: T. Locher. Foundations of Aggregation and Synchronization in Distributed Systems. PhD thesis, ETH Zurich, 2009.
• 13: T. Locher and R. Wattenhofer. Oblivious Gradient Clock Synchronization. In Proc. 20th International Symposium on Distributed Computing (DISC), pages 520--533, 2006.
• 14: J. Lundelius Welch and N. Lynch. An Upper and Lower Bound for Clock Synchronization. Information and Control, 62(2/3):190--204, 1984.
• 15: Miklós Maróti , Branislav Kusy , Gyula Simon , Ákos Lédeczi, The flooding time synchronization protocol, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031501]
• 16: Lennart Meier , Lothar Thiele, Brief announcement: gradient clock synchronization in sensor networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073858]
• 17: D. Mills. Internet Time Synchronization: the Network Time Protocol. IEEE Transactions on Communications, 39:1482--1493, 1991.
• 18: Yoram Moses , Ben Bloom, Knowledge, timed precedence and clocks (preliminary report), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.294-303, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198113]
• 19: 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]
• 20: Santashil PalChaudhuri , Amit Kumar Saha , David B. Johnson, Adaptive clock synchronization in sensor networks, Proceedings of the 3rd international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984672]
• 21: 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]
• 22: P. Sommer and R. Wattenhofer. Gradient Clock Synchronization in Wireless Sensor Networks. In Proc. 8th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN), San Francisco, USA, April 2009.
• 23: 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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional 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

General Terms:
Algorithms, Theory

Keywords:
clock synchronization, gradient property, optimal skew bounds