research-article

Tight bounds for clock synchronization

Authors:

Christoph Lenzen,

Roger WattenhoferAuthors Info & Claims

PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing

Pages 46 - 55

https://doi.org/10.1145/1582716.1582730

Published: 10 August 2009 Publication History

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]

B. Awerbuch. Complexity of Network Synchronization. Journal of the ACM, 32(4):804--823, 1985.

Digital Library

[2]

S. Biaz and J. Lundelius Welch. Closed Form Bounds for Clock Synchronization Under Simple Uncertainty Assumptions. Information Processing Letters, 80(3):151--157, 2001.

Digital Library

[3]

J. Elson, L. Girod, and D. Estrin. Fine-Grained Network Time Synchronization Using Reference Broadcasts. ACM SIGOPS Operating Systems Review, 36:147--163, 2002.

Digital Library

[4]

R. Fan and N. Lynch. Gradient Clock Synchronization. In Proc. 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 320--327, 2004.

Digital Library

[5]

M. Fuegger, U. Schmid, G. Fuchs, and G. Kempf. Fault-Tolerant Distributed Clock Generation in VLSI Systems-on-Chip. In Proceedings of the Sixth European Dependable Computing Conference (EDCC-6), pages 87--96, 2006.

Digital Library

[6]

S. Ganeriwal, R. Kumar, and M. B. Srivastava. Timing-Sync Protocol for Sensor Networks. In Proc. 1st international Conference on Embedded Networked Sensor Systems, pages 138--149, 2003.

Digital Library

[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]

F. Kuhn, T. Locher, and R. Oshman. Gradient Clock Synchronization in Dynamic Networks. In Proc. 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2009.

Digital Library

[9]

C. Lenzen, T. Locher, and R. Wattenhofer. Clock Synchronization with Bounded Global and Local Skew. In Proc. 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 500--510, 2008.

Digital Library

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

Digital Library

[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]

M. Maroti, B. K. G. Simon, and A. Ledeczi. The Flooding Time Synchronization Protocol. In Proc. 2nd International Conference on Embedded Networked Sensor Systems, pages 39--49, 2004.

Digital Library

[16]

L. Meier and L. Thiele. Brief Announcement: Gradient Clock Synchronization in Sensor Networks. In Proc. 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), page 238, 2005.

Digital Library

[17]

D. Mills. Internet Time Synchronization: the Network Time Protocol. IEEE Transactions on Communications, 39:1482--1493, 1991.

[18]

Y. Moses and B. Bloom. Knowledge, Timed Precedence and Clocks. In Proc. 13th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 294--303, 1994.

Digital Library

[19]

R. Ostrovsky and B. Patt-Shamir. Optimal and Efficient Clock Synchronization under Drifting Clocks. In Proc. 18th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 400--414, 1999.

Digital Library

[20]

S. PalChaudhuri, A. K. Saha, and D. B. Johnson. Adaptive Clock Synchronization in Sensor Networks. In Proc. 3rd International Symposium on Information Processing in Sensor Networks, pages 340--348, 2004.

Digital Library

[21]

B. Patt-Shamir and S. Rajsbaum. A Theory of Clock Synchronization. In Proc. 26th Annual ACM Symposium on Theory of Computing (STOC), pages 810--819, 1994.

Digital Library

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

Digital Library

[23]

T. K. Srikanth and S. Toueg. Optimal Clock Synchronization. J. ACM, 34(3):626--645, 1987.

Digital Library

Cited By

Zhou BGuo FVuran M(2022)Timestamp-Free Clock Syntonization for IoT Using Carrier Frequency OffsetIEEE Transactions on Mobile Computing10.1109/TMC.2020.300913221:2(712-727)Online publication date: 1-Feb-2022
https://doi.org/10.1109/TMC.2020.3009132
Upadhyay DDubey ASanthi Thilagam P(2018)Time synchronization problem of wireless sensor network using maximum probability theoryInternational Journal of System Assurance Engineering and Management10.1007/s13198-018-0698-99:2(517-524)Online publication date: 18-Jan-2018
https://doi.org/10.1007/s13198-018-0698-9
Upadhyay DDubey A(2017)Statistical tool for clock offset selection in time synchronization protocols of Wireless Sensor Network2017 7th International Conference on Cloud Computing, Data Science & Engineering - Confluence10.1109/CONFLUENCE.2017.7943182(397-401)Online publication date: Jan-2017
https://doi.org/10.1109/CONFLUENCE.2017.7943182
Show More Cited By

Index Terms

Tight bounds for clock synchronization

Recommendations

Tight bounds for clock synchronization

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 ...
Gradient clock synchronization
PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing

We introduce the distributed gradient clock synchronization problem. As in traditional distributed clock synchronization, we consider a network of nodes equipped with hardware clocks with bounded drift. Nodes compute logical clock values based on their ...
Gradient clock synchronization

We introduce the distributed gradient clock synchronization problem. As in traditional distributed clock synchronization, we consider a network of nodes equipped with hardware clocks with bounded drift. Nodes compute logical clock values based on their ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing

August 2009

356 pages

ISBN:9781605583969

DOI:10.1145/1582716

General Chair:
Srikanta Tirthapura
Iowa State University, USA
,
Program Chair:
Lorenzo Alvisi
The University of Texas at Austin, USA

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 August 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '09

Sponsor:

PODC '09: ACM Symposium on Principles of Distributed Computing

August 10 - 12, 2009

AB, Calgary, Canada

Acceptance Rates

PODC '09 Paper Acceptance Rate 27 of 110 submissions, 25%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
370
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhou BGuo FVuran M(2022)Timestamp-Free Clock Syntonization for IoT Using Carrier Frequency OffsetIEEE Transactions on Mobile Computing10.1109/TMC.2020.300913221:2(712-727)Online publication date: 1-Feb-2022
https://doi.org/10.1109/TMC.2020.3009132
Upadhyay DDubey ASanthi Thilagam P(2018)Time synchronization problem of wireless sensor network using maximum probability theoryInternational Journal of System Assurance Engineering and Management10.1007/s13198-018-0698-99:2(517-524)Online publication date: 18-Jan-2018
https://doi.org/10.1007/s13198-018-0698-9
Upadhyay DDubey A(2017)Statistical tool for clock offset selection in time synchronization protocols of Wireless Sensor Network2017 7th International Conference on Cloud Computing, Data Science & Engineering - Confluence10.1109/CONFLUENCE.2017.7943182(397-401)Online publication date: Jan-2017
https://doi.org/10.1109/CONFLUENCE.2017.7943182
Layadi SIlie JKitouni ISaidouni D(2015)Relative Timed Model for Coordinated Multi Agent SystemsComputer Science and Its Applications10.1007/978-3-319-19578-0_2(15-27)Online publication date: 2015
https://doi.org/10.1007/978-3-319-19578-0_2
Yildirim KGurcan O(2014)Efficient Time Synchronization in a Wireless Sensor Network by Adaptive Value TrackingIEEE Transactions on Wireless Communications10.1109/TWC.2014.231616813:7(3650-3664)Online publication date: Jul-2014
https://doi.org/10.1109/TWC.2014.2316168
Yildirim K(2014)Efficient and Discrete Gradient SynchronizationIEEE Communications Letters10.1109/LCOMM.2014.234678718:11(1903-1906)Online publication date: Nov-2014
https://doi.org/10.1109/LCOMM.2014.2346787
Kuhn FOshman R(2011)Dynamic networksACM SIGACT News10.1145/1959045.195906442:1(82-96)Online publication date: 21-Mar-2011
https://dl.acm.org/doi/10.1145/1959045.1959064
Hoepman JLarsson ASchiller ETsigas P(2011)Secure and self-stabilizing clock synchronization in sensor networksTheoretical Computer Science10.1016/j.tcs.2010.04.012412:40(5631-5647)Online publication date: 1-Sep-2011
https://dl.acm.org/doi/10.1016/j.tcs.2010.04.012
Huang XSingh ASmolka S(2011)Using integer clocks to verify clock-synchronization protocolsInnovations in Systems and Software Engineering10.1007/s11334-011-0152-57:2(119-130)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1007/s11334-011-0152-5
Lenzen CLocher TWattenhofer R(2010)Tight bounds for clock synchronizationJournal of the ACM10.1145/1667053.166705757:2(1-42)Online publication date: 8-Feb-2010
https://dl.acm.org/doi/10.1145/1667053.1667057
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten