Engineering Journal: Science and InnovationELECTRONIC SCIENCE AND ENGINEERING PUBLICATION
Certificate of Registration Media number Эл #ФС77-53688 of 17 April 2013. ISSN 2308-6033. DOI 10.18698/2308-6033
  • Русский
  • Английский
Article

Clock synchronization in distributed multicomputer systems. Part II

Published: 18.05.2021

Authors: Asharina I.V.

Published in issue: #5(113)/2021

DOI: 10.18698/2308-6033-2021-5-2081

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 second part deals with synchronization in systems with Byzantine faults, and this is a complex task due to the characteristic features of the fault model. The synchronization process in multi-cluster and multi-complex systems is associated with the multitasking of such systems, which makes the synchronization process even more relevant and multi-criteria. The paper considers the modern technologies providing the synchronization process in systems of critical use.


References
[1] Asharina I.V. Inzhenerny zhurnal: nauka i innovatsii — Engineering Journal: Science and Innovation, 2021, iss. 4. DOI: 10.18698/2308-6033-2021-4-2074
[2] Lamport L., Melliar-Smith P.M. Synchronizing clocks in the presence of faults. J. Assoc. Comput. Mach., 1985, vol. 32 (1), рр. 52–78.
[3] Shin Kang G., Ramanathan P. Clock synchronization of a large multiprocessor system in the presence of malicious faults. IEEE Transactions on Computers, 1987, vol. C-36, no. 1, рр. 2–12.
[4] Dolev D., Halpern J.Y., Strong R. On the possibility and impossibility of achieving clock synchronization. Proceedings of the 16th Annual ACM STOC. April 30 — May 2, 1984, Washington D.C., USA. New York, ACM, 1984, pp. 504–511.
[5] Lundelius-Welch 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
[6] Halpern J., Simons B., Strong R. An efficient fault-tolerant algorithm for clock synchronization. Proceedings of the 3rd annual ACM symposium on Principles of distributed computing, August 27–29, 1984, Vancouver, B.C., Canada. New York, Association for Computing Machinery, 1984, pp. 75–88. DOI: 10.1145/800222.806738
[7] Mahaney S., Schneider F. Inexact agreement: Accuracy, precision and graceful degradation. Proceedings of 4th International Symposium 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
[8] Drummond R. Impact of communication networks on fault-tolerant distributed computing. Ph.D. dissertation thesis. Ithaca, N.Y., Department of Computer Science, Cornell University, 1986, 95 p.
[9] Marzullo K. Maintaining the time in a distributed system. An example of a loosely-coupled distributed service. Ph.D. dissertation. Stanford, California, Department of Electrical Engineering, Stanford University, 1984, 128 p.
[10] Srikanth Т.K., Toueg S. Optimal clock synchronization. Journal of the Association for Computing Machinery, 1987, vol. 34, no. 3, pp. 626–645.
[11] Diffie W., Hellman M. New directions in cryptography. IEEE Trans. Inf. Theory IT, 1976, no. 22, pp. 644–654.
[12] Srikanth Т.K., Toueg S. Simulating authenticated broadcasts to derive simple fault- tolerant algorithms. Tech. Rep. 84-623, Dept. of Computer Science, Cornell Univ., Ithaca, N.Y., July 1984. (Also to appear in Distributed Computing, Springer-Verlag, New York.).
[13] Lobanov A.V. Programmirovanie — Programming and Computer Software, 1997, no. 2, pp. 76–80.
[14] Paulitsch M., Steiner W. Fault-tolerant clock synchronization for embedded distributed multi-cluster systems. Conference: Real-Time Systems, Proceedings. 15th Euromicro Conference, August 2003. Technische Universität Wien, Vienna, Austria. DOI: 10.1109/EMRTS.2003.1212750
[15] Phillips A. Functional decomposition in a vehicle control system. American Control Conference, Anchorage, AK, May 8–10, 2002. Anchorage, AK, USA, IEEE, vol. 5, pp. 3713–3718. DOI: 10.1109/ACC.2002.1024505
[16] Kopetz H., Bauer G. The time-triggered architecture. Proceedings of the IEEE, 2003, vol. 91, iss. 1, pp. 112–126. DOI: 10.1109/JPROC.2002.805821
[17] Kopetz H., Ochsenreiter W. Clock synchronization in distributed real-time computer systems. IEEE Transactions on Computers, 1987, C-36, no. 8, pp. 933–940.
[18] Srikanth Т.K., Toueg S. Optimal clock synchronization. Journal of the Association for Computing Machinery, 1987, vol. 34, no. 3, pp. 626–645.
[19] Verissimo P., Casimiro A., Rodrigues L. Cesium spray: a precise and accurate global time service for large scale systems. Journal of Real-Time Systems, 1997, vol. 12, no. 3, pp. 243–294. DOI: 10.1023/A:1007949113722
[20] Pfluegl M., Blough D. A new and improved algorithm for fault-tolerant clock synchronization. Journal of Parallel and Distributed Computing, 1995, vol. 27, pp. 1–14.
[21] Dolev D., Halpern J., Simons B., Strong R. Dynamic fault-tolerant clock synchronization. Journal of the Association for Computing Machinery, 1995, vol. 42, no. 1, pp. 143–185.
[22] Fetzer C., Cristian F. Integrating external and internal clock synchronization. Journal of Real-Time Systems, 1997, vol. 12, no. 2, pp. 123–172.
[23] Schmid U., Schossmaier K. Interval-based clock synchronization. Real-Time Systems, 1997, vol. 12, pp. 173–228.
[24] De Azevedo M., Blough D. Fault-tolerant clock synchronization of large multicomputers via multistep interactive convergence. Proceedings of 16th International Conference on Distributed Computing Systems, Hong Kong, China, May 27–30, 1996. New York, IEEE, 1996, pp. 249–257. DOI: 10.1109/ICDCS.1996.507923
[25] Kopetz H., Krüger A., Millinger D., Schedl A. A synchronization strategy for a time-triggered multicluster real-time system. Proceedings of the 14th Symposium on Reliable Distributed Systems, September 13–15, 1995, Bad Neuenahr, Germany. IEEE Computer Society Press, 1995, pp. 154–161. DOI: 10.1109/RELDIS.1995.526223
[26] 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.
[27] Sun K., Ning P., Wang C. Fault-tolerant cluster-wise clock synchronization for wireless sensor networks. IEEE Transactions on Dependable and Secure Computing, 2005, vol. 2, iss. 3, рр. 177–189. DOI: 10.1109/TDSC.2005.36
[28] Romer K., Blum P., Meier L. Time synchronization and calibration in wireless sensor networks. Wireless Sensor Networks, Ivan Stojmenovic, ed. Hoboken, NJ, Wiley-Interscience, 2005, pp.199–237.
[29] Stetsyura G.G. Avtomatika i telemekhanika — Automation and Remote Control, 2012, no. 5, pp. 111–124.
[30] Promyslov V.G., Semenkov K.V., Timofeev M.Yu. Problemy sinkhronizatsii vremeni v raspredelennykh avtomatizirovannykh sistemakh upravleniya tekhnologicheskimi protsessami [Time synchronization problems in distributed automated process control systems]. Available at: https://mlsd2020.ipu.ru/proceedings/1431-1437.pdf
[31] Mills D.L. Internet time synchronization: the network time protocol. IEEE Transactions on Computers, 1991, vol. 39, no. 10, pp. 1482–1493.
[32] Mills D., Martin J., Burbank J., Kasch W. Network time protocol version 4: protocol and algorithms specification, RFC5905 (Standard). Internet Engineering Task Force (IETF), Technical report, 2010, pp. 68–88. Available at: https://tools.ietf.org/html/rfc5905 (accessed March 15, 2017).
[33] Beliakov M.O., Borisov D.A., Seleznev A.A. Voprosy radioelektroniki — Issues of radio electronics, 2017, no. 12, pp. 36–43.
[34] Kryuchkov I.V., Filatov A.A. Inzhenerny zhurnal: nauka i innovatsii — Engineering Journal: Science and Innovation, 2012, iss. 8, pp. 45–52. DOI: 10.18698/2308-6033-2012-8-316
[35] Lobanov A.V., Sirenko V.G. Obrazovatelnye resursy i tekhnologii (Educational resources and technologies), 2014, no. 2 (5), pp. 115–121.
[36] Lamport L. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 1978, vol. 21, no. 7, pp. 558–565.
[37] Lamport L., Shostak R., Pease M. The byzantine generals problem. ACM Transactions on Programming Languages and Systems, 1982, vol. 4, no. 3, pp. 382–401.
[38] Lamport L. The implementation of reliable distributed multiprocess systems. Computer Network, 1978, vol. 2, pp. 95–114.
[39] Lamport L. Using time instead of timeout for fault-tolerant distributed systems. ACM Transactions on Programming Languages and Systems, 1984, vol. 6, no. 2, pp. 254–280. DOI: 10.1145/2993.2994
[40] Liskov B. Practical uses of synchronized clocks in distributed systems. Distributed Computing, Periodicals Distributed Computing, 1993, vol. 6, no. 4, pp. 211–219. DOI: 10.1007/BF02242709
[41] Lobanov A.V. Avtomatika i telemekhanika — Automation and Remote Control, 2009, no. 2, pp. 171–189.
[42] Asharina I.V., Lobanov A.V., Mischenko I.G. Avtomatika i telemekhanika — Automation and Remote Control, 2003, no. 5, pp. 190–198.