Clock synchronization in distributed multicomputer systems. Part I
Published: 27.04.2021
Authors: Asharina I.V.
Published in issue: #4(112)/2021
DOI: 10.18698/2308-6033-2021-4-2074
Category: Aviation and Rocket-Space Engineering | Chapter: Innovation Technologies of Aerospace Engineering
The study substantiates the necessity of clock synchronization in distributed multicomputer systems. The basic definitions related to the concept of clock synchronization are given, and methods of clock synchronization are classified. Increasing the lifecycle of failure- and fault-tolerant distributed multicomputer systems for critical application is one of the most urgent problems at the current level of technology development. This is especially true for unattended distributed multicomputer systems for space applications. The development of such systems should begin with the construction of models of faults and self-controlled degradation, ensuring, firstly, their failure and fault tolerance and, secondly, maximum survivability, which is possible only if there are means of clock synchronization in such systems. All activities associated with ensuring the synchronization of any distributed multicomputer systems begin with the concept of synchronization of on-board functions, which is based on the generation of on-board time and includes the synchronization of on-board software and equipment that requires time synchronization or information about the course of time. The main elements of this concept are the processor clock module, the onboard software clock, the atomic navigation clock.
The first part of the work gives basic definitions, and considers methods and algorithms related to the clock synchronization process. The second part is devoted to synchronization in systems with Byzantine faults and in multi-cluster and multi-complex, i.e. multitask, systems. The modern technologies providing the synchronization process in such systems are considered.
References
[1] Dolev D., Dwork C., Stockmeyer L. On the minimal synchronics needed for distributed consensus. Proc. 24th Symp. on Foundationcs of Computer Science. IEEE, Tucson, USA, 1983, pp. 393–402.
[2] Lobanov A.V., Sirenko V.G. Obrazovatelnye resursy i tekhnologii (Educational resources and technologies), 2014, no. 2 (5), pp. 115–121.
[3] Eickhoff J. On-board computers, onboard software and satellite operations: An Introduction. Springer, 2016, 300 p. [In Russ.: Eickhoff J. Bortovye komp’iutery, programmnoe obespechenie i poletnye operatsii. Vvedenie. Moscow, Tekhnosfera Publ., 2018, 344 p.].
[4] Lamport L. Time, clocks, and the ordering of events in a distributed system, Comm. ACM, July 1978, vol. 21 (7), pp. 558–565.
[5] Anceaume Em., Puaut I. A taxonomy of clock synchronization algorithms. Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Research Report 1103, 1997. Available at: http://citeseer.ist.psu.edu/anceaume97taxonomy.html
[6] Cristian F., Aghili H., Strong R., Dolev D. Atomic broadcsat: from simple message diffusion to byzantine agreement. Proc. 15th Int. Symp. on Fault-Tolerant Computing Systems, 1985.
[7] Lamport L., Shostak R., Pease M. The byzantine generals problem. ACM Trans. Progr. Lang. Syst., 1982, vol. 4, no. 3, pp. 382–401.
[8] Kovyazina D.R. Nauchno-tekhnicheskiy vestnik Sankt-Peterburgskogo gosudarstvennogo universiteta informatsionnykh tekhnologii, mekhaniki i optiki — Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2009, no. 2 (60), pp. 87–93.
[9] Slovar russkikh sinonimov [Dictionary of Russian synonyms]. Available at: https://dic.academic.ru/dic.nsf/dic_fwords/10911
[10] IEEE Std 1588TM-2008 (Revision of IEEE Std 1588-2002). IEEE Instrumen. Measur. Soc., 2008, 269 р.
[11] Eidson J.C. Measurement, Control and Communication Using. IEEE 1588, Springer, 2006, 283 р.
[12] Lamport L., Melliar-Smith P.M. Synchronizing clocks in the presence of faults. J. Assoc. Comput. Mach., January 1985, no. 32 (1), рр. 52–78.
[13] Lamport L. The implementation of reliable distributed multiprocess systems. Comput. Netw., 1978, no. 2, pp. 95–114.
[14] Lamport L. Using time instead of timeout for fault-tolerant distributed systems. ACM Trans. Prog. Lang. Syst, April 1984. https://doi.org/10.1145/2993.2994
[15] Dolev D., Halpern J.Y., Strong R. On the possibility and impossibility of achieving clock synchronization. Proc. 16th Annual ACM STOC (Washington D.C., Apr.). ACM, New York, 1984, pp. 504–511. (Also to appear in J. Comput. Syst. Sc.).
[16] Halpern J., Simons B., Strong R. An efficient fault-tolerant algorithm for clock synchronization. Proc. 3rd Annual ACM Symp. on Principles of Distributed Computing, August 27–29, 1984, Vancouver, B.C., Canada. Association for Computing Machinery, New York, 1984, pp. 75–88. DOI: 10.1145/800222.806738
[17] Dolev D., Halpern J.Y., Strong H.R. On the possibility and impossibility of achieving clock synchronization. Proc. 16th Annual ACM Symp. on Theory of Computing (Washington, D.C., Apr. 30 — May 2). ACM, New York, 1984, pp. 504–511.
[18] Ramanathan P., Shin K.G., Butler R.W. Fault-Tolerant Clock Synchronization in Distributed Systems. Computer, November 1990, no. 23 (10), рр. 33–42. DOI: 10.1109/2.58235
[19] Paulitsch M., Steiner W. Fault-Tolerant Clock Synchronization for Embedded Distributed Multi-Cluster Systems. Conference: Real-Time Systems, August 2003. Proc. 15th Euromicro Conf. Technische Universität Wien, Vienna, Austria. DOI: 10.1109/EMRTS.2003.1212750
[20] Ramanathan P., Kandlur D.D., Shin K.G. Hardware-Assisted Software Clock Synchronization for Homogeneous Distributed Systems. IEEETrans. Computers, Apr. 1990, vol. C-39, no. 4, pp. 514–524.
[21] Welch L.J., Lynch N. A new fault-tolerant algorithm for clock synchronization. Information and Computation, 1988, no. 77, pp. 1–36. DOI: 10.1016/0890-5401(88)90043-0
[22] Dolev D., Lynch N., Pinter S., Stark E., Weihl W. Reaching approximate agreement in the presence of faults. Proc. 3rd Annual IEEE Symp. on Distributed Software and Database Systems, October 26–29, 1983, Association for Computing Machinery, New York. New York, IEEE, 1983, pp. 145–154.
[23] Fetzer Ch., Cristian F. An Optimal Internal Clock Synchronization Algorithm. Conference: Computer Assurance. COMPASS ‘95. Systems Integrity, Software Safety and Process Security. Proceedings of the Tenth Annual Conference, 1995, рр. 187–196. DOI: 10.1109/CMPASS.1995.521898
[24] Schneider F. Understanding protocols for Byzantine clock synchronization. Technical Report, Dept of Computer Science, Cornel1 University, 1987, 859 p.
[25] Mills D.L. Internet time synchronization: the network time protocol. IEEE Truns. Communications, October 1991, no. 39 (10), pp. 1482–1493.
[26] Kopetz H., Ochsenreiter W. Clock synchronization in distributed real-time computer systems. IEEE Transactions on Computers, August 1987, C-36(8), pp. 933–940.
[27] Halpern J., Strong H., Simons B., Dolev D. Fault-tolerant clock synchronization. Proceedings of 3rd International Symposium on Principles of Distributed Computing, August 27–29, 1984, Vancouver, B.C., Canada. Association for Computing Machinery, New York, 1984, pp. 89–102. DOI: 10.1145/800222.
[28] Srikanth Т.K., Toueg S. Optimal clock synchronization. Journal of the ACM, July 1987, no. 34 (3), pp. 626–645.
[29] Verissimo P., Casimiro A., Rodrigues L. Cesiumspray: a precise and accu-rate global time service for large scale systems. Journal of Real-Time Systems, 1997, no. 12, pp. 243–294.
[30] Pfluegl M., Blough D. A new and improved algorithm for fault-tolerant clock synchronization. Journal of Parallel and Distributed Computing, 1995, no. 27, pp. 1–14.
[31] Gusella R., Zatti S. The accuracy of the clock synchronization achieved by TEMPO in Berkeley UNIX 4.3BSD. IEEE Transactions on Software Engineering, July 1989, no. 15 (7), pp. 847–853.
[32] Mahaney S., Schneider F. Inexact agreement: Accuracy, precision and graceful degradation. Proc. 4th Int. Symp. on Principles of Distributed Computing, August 5–7, 1985, Minaki, Ontario, Canada. New York, Association for Computing Machinery, 1985, pp. 237–249. DOI: 10.1145/323596.323618
[33] Fetzer C., Cristian F. Lower bounds for function based clock synchronization. Proc. 13th Int. Symp. on Principles of Distributed Computing, August 18–21, 1995, Ottowa, Ontario, Canada. New York, Association for Computing Machinery, 1995, pp. 137–143. DOI: 10.1145/224964.224980
[34] Fetzer C., Cristian F. Integrating external and internal clock synchronization. Journal of Real-Time Systems, 1997, no. 12 (2), pp. 123–172.
[35] Arvind K. Probabilistic clock synchronization in distributed systems. IEEE Transactions on Parallel and Distributed Systems, 1994, no. 5 (5), pp. 474–487.
[36] Cristian F. Probabilistic clock synchronization. Distributed Computing, 1989, vol. 3, pp. 146–158.
[37] Schneider F. A paradigm for reliable clock synchronization. Technical Report TR86-735. Computer Science Department. Cornell University, February 1986. Available at: https://hdl.handle.net/1813/6575 (accessed February 3, 2021).
[38] Simons B., Lundelius-Welch J., Lynch N. An overview of clock synchronization. In: Simons B., Spector A., eds. Fault-Tolerant Distributed Computing. Lecture Notes in Computer Science, 1990, vol. 448, pp. 84–96.
[39] Liskov B. Practical Uses of Synchronized Clocks in Distributed Systems. Distributed Computing. Periodicals Distributed Computing, vol. 6, no. 4, pp. 211–219. https://doi.org/10.1007/BF02242709