Инженерный журнал: наука и инновацииЭЛЕКТРОННОЕ НАУЧНО-ТЕХНИЧЕСКОЕ ИЗДАНИЕ
свидетельство о регистрации СМИ Эл № ФС77-53688 от 17 апреля 2013 г. ISSN 2308-6033. DOI 10.18698/2308-6033
  • Русский
  • Английский
Статья

Синхронизация часов в распределенных многомашинных вычислительных системах. Часть II

Опубликовано: 18.05.2021

Авторы: Ашарина И.В.

Опубликовано в выпуске: #5(113)/2021

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

Раздел: Авиационная и ракетно-космическая техника | Рубрика: Инновационные технологии в аэрокосмической деятельности

Обоснована необходимость синхронизации часов в распределенных многомашинных вычислительных системах. Приведены основные определения, связанные с понятием синхронизации часов. Представлена классификация методов синхронизации часов. Рассмотрена одна из наиболее актуальных задач, которую необходимо решить при разработке сбое- и отказоустойчивых распределенных многомашинных вычислительных систем ответственного применения, особенно необслуживаемых, в частности космических, — увеличение сроков их активного существования. Вторая часть посвящена синхронизации в системах с византийскими неисправностями, что является сложной задачей, обусловленной особенностями модели неисправности. Процесс синхронизации в многокластерных и многокомплексных системах связан с многозадачностью таких систем, что делает процесс синхронизации еще более актуальным и многокритериальным. Рассмотрены современные технологии, обеспечивающие процесс синхронизации в системах ответственного применения.


Литература
[1] Ашарина И.В. Синхронизация часов в распределенных многомашинных вычислительных системах. Часть I. Инженерный журнал: наука и инновации, 2021, вып. 4. http://dx.doi.org/10.18698/2308-6033-2021-4-2074
[2] Lamport L., Melliar-Smith P.M. Synchronizing clocks in the presence of faults. Journal of the ACM, 1985, vol. 32, no. 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. Association for Computing Machinery, New York, 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. Technical Report. Ithaca, N.Y., Cornell University, Department of Computer Science, 1984, pp. 84–623.
[13] Лобанов А.В. Синхронизация и взаимное информационное согласование в распределенных вычислительных системах. Программирование, 1997, № 2, с. 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. Cesiumspray: 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] Ковязина Д.Р. Автоматическая калибровка и синхронизация времени во встраиваемых вычислительных системах. Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2009, № 2 (60), с. 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] Стецюра Г.Г. Синхронизация взаимодействия цифровых устройств с помощью центра ретрансляции сигналов. Автоматика и телемеханика, 2012, вып. 5, c. 111–124.
[30] Промыслов В.Г., Семенков К.В., Тимофеев М.Ю. Проблемы синхронизации времени в распределенных автоматизированных системах управления технологическими процессами. URL: https://mlsd2020.ipu.ru/proceedings/1431-1437.pdf (дата обращения 15.03.2020).
[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. URL: https://tools.ietf.org/html/rfc5905 (дата обращения 15.03.2017).
[33] Беляков М.О., Борисов Д.А., Селезнев А.А. Синхронизация времени внутри группировки ПВО с использованием проводных и радиоканалов связи. Вопросы радиоэлектроники, 2017, № 12, с. 36–43.
[34] Крючков И.В., Филатов А.А. Синхронизация подвижных модулей распределенных радиолокационных комплексов. Инженерный журнал: наука и инновации, 2012, вып. 8, с. 45–52. DOI: 10.18698/2308-6033-2012-8-316
[35] Лобанов А.В., Сиренко В.Г. Проблема отказоустойчивости в сетецентрических информационно-управляющих системах. Образовательные ресурсы и технологии, 2014, № 2 (5), с. 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] Лобанов А.В. Модели замкнутых многомашинных вычислительных систем со сбое- и отказоустойчивостью на основе репликации задач в условиях возникновения враждебных неисправностей. Автоматика и телемеханика, 2009, № 2, с. 171–189.
[42] Ашарина И.В., Лобанов А.В., Мищенко И.Г. Взаимное информационное согласование в неполносвязных многомашинных вычислительных системах. Автоматика и телемеханика, 2003, № 5, с. 190–198.