Inmersión a los algoritmos de sincronización de relojes en sistemas distribuidos

Gabriel  Gerónimo-Castillo; Everth Haydeé  Rocha-Trejo; Carlos  Vázquez-Cid de León

doi:10.59169/pentaciencias.v6i6.1267

Authors

Gabriel Gerónimo-Castillo Universidad Tecnológica de la Mixteca https://orcid.org/0009-0004-1619-5575
Everth Haydeé Rocha-Trejo Universidad Tecnológica de la Mixteca https://orcid.org/0000-0002-8474-0094
Carlos Vázquez-Cid de León Universidad Tecnológica de la Mixteca https://orcid.org/0000-0003-2067-0565

DOI:

https://doi.org/10.59169/pentaciencias.v6i6.1267

Keywords:

distributed systems; clock synchronization; algorithms, network time protocol; precision time protocol

Abstract

The objective of the research is to provide a deep understanding of the concepts and algorithms applied for clock synchronization among the nodes of a distributed system (DS). This article describes the main algorithms related to solving the problem of time discrepancy in the clocks of a loosely coupled distributed system. It starts from the logical synchronization proposed by Lamport, which establishes a theoretical basis for temporal coordination in distributed systems, to Mills' contributions implemented in the versions of the Network Time Protocol (NTP) currently used on the Internet and the Precision Time Protocol (PTP) standardized by the IEEE, which allows for greater synchronization precision. The methodology used includes a thorough review of the literature, analyzing both centralized and decentralized algorithms. The proposals by Gusella and Zatti, which introduce innovative approaches to clock synchronization, as well as the algorithm by Cristian Flaviu, known for its simplicity and effectiveness, are addressed. The results obtained show that each algorithm has specific advantages depending on the scenario and requirements of the distributed system in question.

Downloads

Download data is not yet available.

References

Baldoni, R., Mostefaoui, A., & Raynal, M. (1996). Causal delivery of messages with real-time data in unrealiable networks. Journal of Real-Time Systems, 10, 245-262.

Baldoni, R. & Raynal, M. (2002). Fundamentals of Distributed Computing: A Practical Tour of Vector Clock Systems. IEEE Distributed Systems Online, 3(2).

Birman, K., & Joseph, T. (1987). Reliable Communication in the Presence of Failures. ACM Transactions on Computer Systems, 5(1), 47-76.

Chandy, K. & Lamport, L. (1985). Distributed Snapshots: Determining Global States of Distributed Systems. ACM Transactions on Computer Systems, 3(1), 63-75.

Cristian, F. (1989). Probabilistic clock synchronization. Distributed Computing, 3(3), 146-158.

Dalwadi, N. & Padole, M. (2017). Comparative Study of Clock Synchronization Algorithms in Distributed Systems. Advances in Computational Sciences and Technology, 10(6), 1941-1952.

Dang, F., Sun, X., Liu, K., Xu, Y., & Liu, Y. (2023). A Survey on Clock Synchronization in the Industrial Internet. Journal of Computer Science and Technology, 38(1), 146-165, doi: 10.1007/ s11390-023-2908-4.

Fidge, C. (1988). Timestamp in Message Passing Systems that Preserves Partial Ordering. Proc. 11Th Australian Computing Science Communication, 10(1), 56-66.

Gusella, R. & Zatti, S. (1987). The Accuracy of the Clock Synchronization Achieved by TEMPO in Berkeley UNIX 4.3 BSD. Report No. UCB/CSD 87/33. Computer Science Division (EECS). University of California. Berkeley California.

IEEE Standar 1588-2002. (Noviembre 2002). IEEE Standard for a Precision Clock Synchronization Protocol for Networked Measurement and Control Systems. http://standards.ieee.org

IEEE Standar 1588-2008. (Julio 2008). IEEE Standar for a Precision Clock Synchronization Protocol for Networked Measurement and Control Systems. http://standards.ieee.org

IEEE Standar 1588-2019. (Noviembre 2019). IEEE Standard for a Precision Clock Synchronization Protocol for Networked Measurement and Control Systems. http://standards.ieee.org

IEEE/IEC 61588-2021. (Junio 2021). IEC/IEEE International Standar- Precision Clock Synchronization Protocol for NetWorked Measurement and Control Systems. http://standards.ieee.org

Itkin, E., & Wool, A. (2020). A Security Analysis and Revised Security Extension for the Precision Time Protocol. IEEE Transactions on Dependable and Secure Computing, 17(1), 22-34, doi: 10.1109/TDSC.2017.2748583

Kumar, M. & Manjula, R. (2013). Performance Comparison of Physical Clock Synchronization Algorithms. International Journal of Engineering Sciences & Research, 2(3), 601-607.

Lamport, L. (1978). Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM, 21(7), 558-565.

Marzullo, K. & Owicki, S. (1983). Maintaining the Time in a Distributed System. Report No. 83-247. Computer Systems Laboratory. Departments of Electrical Engineering and Computer Science. Stanford University.

Mattern, F. (1988). Virtual Time and Global States of Distributed systems [Conference]. En Cosnard, Quinton, Raynal, & Robert (Eds). Proc. Workshop on Parallel and Distributed Algorithms, 215–226.

Mills, D. (1981). DCNET Internet Clock Service. DARPA Network Working Group Report RFC- 778. COMSAT Laboratories.

Mills, D. (1983). DCN Local-Network Protocols. DARPA Network Working Group Report RFC- 891. M/A-COM Linkabit.

Mills, D. (1985a). Network Time Protocol (NTP). DARPA Network Working Group Report RFC-958. M/A-COM Linkabit.

Mills, D. (1985b). Algorithms for Synchronizing Network Clocks. DARPA Network Working Group Report RFC-956. M/A-COM Linkabit.

Mills, D. (1985c). Experiments in Network Clocks Synchronization. DARPA Network Working Group Report RFC-957. M/A-COM Linkabit.

Mills, D. (1988). Network Time Protocol (Version 1) Specification and Implementation. DARPA Network Working Group Report RFC-1059. University of Delaware.

Mills, D. (1989a). Network Time Protocol (Version 2) Specification and Implementation. DARPA Network Working Group Report RFC-1119. University of Delaware.

Mills, D. (1989b). Measured Performance of the Network Time Protocol in the Internet System. DARPA Network Working Group Report RFC-1128. University of Delaware.

Mills, D. (1991). Internet Time Synchronization: The Network Time Protocol. IEEE Transactions on Commmunications, 39(10), 1482-1493. doi: 10.1109/26.103043

Mills, D. (1992). Network Time Protocol (Version 3) Specification, Implementation and Analysis. DARPA Network Working Group Report RFC-1305. University of Delaware.

Mills, D. (1996). Simple Network Time Protocol (SNTP) Version 4 for IPv4, IPv6 and OSI. DARPA Network Working Group Report RFC-2030. University of Delaware.

Mills, D. (2003). A Brief History of NTP time: Memoirs of an Internet timekeeper. Computer Communication Review, 33, 9-21.

Mills, D. (2010a). Network Time Protocol Version 4: Protocol and Algorithms Specification. Internet Engineering Task Force Report RFC-5905. University of Delaware.

Mills, D. (2010b). Network Time Protocol Version 4: Autokey Specification. Internet Engineering Task Force, RFC-5906. University of Delaware.

Pandey, P., Pratap, B. & Pandey, R. (2019). Analysis and Design of Precision Time Protocol System Based on IEEE1588 Standars. Proceedings of the Fourth International Conference on Communication and Electronics Systems. 1963-1967.

Peng, Y., Luo, Q., & Liu, Z. (2009). An automatic evaluation system for IEEE 1588 synchronization clock unit. Proceeding of the Ninth International Conference on Electronic Measurement and Instruments, 408-413.

Singhal, M. & Kshemkalyani, A. (1992). An efficient implementation of vector clocks. Information Processing Letters, 43(1), 47-52.

Watt, S., Achanta, S., Abubakari, H., & Sagen, E. (2014). Understanding and Applying Precision Time Protocol. Power and Energy Automation Conference. Schweitzer Engineering Laboratories, Inc.

Wu, J. & Peloquin, R. (2009). Synchronizing Device Clocks Using IEEE 1588 and Blackfin Embedded Processors. Analog Dialogue, 43(11), 1-5.

Zeba, I., Granados, J., Sun, Y., Latif, S., Gong, L., Zou, Z., & Zheng, L. (2020). IEEE 1588 for Clock Synchronization in Industrial IoT and Related Applications: A Review on Contributing Technologies, Protocols and Enhancement Methodologies. IEEE Access, 8, 155660-155678. doi: 10.1109/ACCESS.2020.3013669