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 worst-case 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. Awerbuch, B. 1985. Complexity of network synchronization. J. ACM 32, 4, 804--823.
2. Biaz, S., and Lundelius Welch, J. 2001. Closed form bounds for clock synchronization under simple uncertainty assumptions. Inf. Proc. Lett. 80, 3, 151--157.
3. Elson, J., Girod, L., and Estrin, D. 2002. Fine-grained network time synchronization using reference broadcasts. ACM SIGOPS Ope. Syst. Rev. 36, 147--163.
4. Fan, R., and Lynch, N. 2004. Gradient clock synchronization. In Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM, New York, 320--327.
5. Függer, M., Schmid, U., Fuchs, G., and Kempf, G. 2006. Fault-tolerant distributed clock generation in VLSI systems-on-Chip. In Proceedings of the 6th European Dependable Computing Conference (EDCC-6). 87--96.
6. Ganeriwal, S., Kumar, R., and Srivastava, M. B. 2003. Timing-sync protocol for sensor networks. In Proceedings of the 1st ACM Conference on Embedded Networked Sensor Systems (SenSys). ACM, New York, 138--149.
7. Korte, B., Rautenbach, D., and Vygen, J. 2007. BonnTools: Mathematical innovation for layout and timing closure of systems on a chip. Proc. IEEE 95, 3, 555--572.
8. Kuhn, F., Locher, T., and Oshman, R. 2009. Gradient clock synchronization in dynamic networks. In Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM, New York, 270--279.
9. Lenzen, C., Locher, T., and Wattenhofer, R. 2008. Clock synchronization with bounded global and local skew. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 500--510.
10. Lenzen, C., Locher, T., and Wattenhofer, R. 2009a. Tight bounds for clock synchronization. In Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM, New York, 46--55.
11. Lenzen, C., Sommer, P., and Wattenhofer, R. 2009b. Optimal clock synchronization in networks. In Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems (SenSys). ACM, New York.
12. Locher, T. 2009. Foundations of aggregation and synchronization in distributed systems. Ph.D. dissertation, ETH Zurich.
13. Locher, T., and Wattenhofer, R. 2006. Oblivious gradient clock synchronization. In Proceedings of the 20th International Symposium on Distributed Computing (DISC). 520--533.
14. Lundelius Welch, J., and Lynch, N. 1984. An upper and lower bound for clock synchronization. Inf. Cont. 62, 2/3, 190--204.
15. Maróti, M., Kusy, B., Simon, G., and Lédeczi, Á. 2004. The flooding time synchronization protocol. In Proceedings of the 2nd ACM Conference on Embedded Networked Sensor Systems (SenSys). ACM, New York, 39--49.
16. Meier, L., and Thiele, L. 2005. Brief announcement: Gradient clock synchronization in sensor networks. In Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM, New York, 238.
17. Mills, D. 1991. Internet time synchronization: The network time protocol. IEEE Trans. Commu. 39, 1482--1493.
18. Moses, Y., and Bloom, B. 1994. Knowledge, timed precedence and clocks. In Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM, New York, 294--303.
19. Ostrovsky, R., and Patt-Shamir, B. 1999. Optimal and efficient clock synchronization under drifting clocks. In Proceedings of the 18th Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM, New York, 400--414.
20. PalChaudhuri, S., Saha, A. K., and Johnson, D. B. 2004. Adaptive clock synchronization in sensor networks. In Proceedings of the 3rd ACM/IEEE International Symposium on Information Processing in Sensor Networks (IPSN). ACM, New York, 340--348.
21. Patt-Shamir, B., and Rajsbaum, S. 1994. A theory of clock synchronization. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC). ACM, New York, 810--819.
22. Sommer, P., and Wattenhofer, R. 2009. Gradient clock synchronization in wireless sensor networks. In Proceedings of the 8th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN). ACM, New York, 37--48.
23. Srikanth, T. K., and Toueg, S. 1987. Optimal clock synchronization. J. ACM 34, 3, 626--645.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles

• Theory of computation

  • Randomness, geometry and discrete structures