Синхронизация часов в распределенных многомашинных вычислительных системах. Часть I
Авторы: Ашарина И.В.
Опубликовано в выпуске: #4(112)/2021
DOI: 10.18698/2308-6033-2021-4-2074
Раздел: Авиационная и ракетно-космическая техника | Рубрика: Инновационные технологии в аэрокосмической деятельности
Обоснована необходимость синхронизации часов в распределенных многомашинных вычислительных системах. Приведены основные определения, связанные с понятием синхронизации часов. Классифицируются методы синхронизации часов. Увеличение сроков активного существования сбое- и отказоустойчивых распределенных многомашинных вычислительных систем ответственного применения является одной из наиболее актуальных задач при современном уровне развития техники. Особенно это касается необслуживаемых распределенных многомашинных вычислительных систем космического применения. Разработка таких систем должна начинаться с построения моделей неисправностей и самоуправляемой деградации, обеспечивающих, во-первых, сбое- и отказоустойчивость и, во-вторых, максимальную живучесть, что возможно лишь при наличии средств синхронизации часов в таких системах. Все действия, связанные с обеспечением синхронизации любых распределенных многомашинных вычислительных систем, начинаются с построения концепции синхронизации бортовых функций, которая основывается на генерации бортового времени и включает в себя синхронизацию бортового как программного обеспечения, так и оборудования, требующего синхронизации часов или информации о ходе времени. Основными элементами этой концепции являются модуль тактового генератора процессора, часы бортового программного обеспечения, атомные навигационные часы. В первой части работы приводятся основные определения, рассматриваются методы и алгоритмы, связанные с процессом синхронизации часов. Вторая часть посвящена синхронизации в системах с византийскими неисправностями и в многокластерных и многокомплексных (многозадачных) системах. Рассмотрены современные технологии, обеспечивающие процесс синхронизации в таких системах.
Литература
[1] Dolev D., Dwork C., Stockmeyer L. On the minimal synchronics needed for distributed consensus. Proceedings 24th Annual Symposium on Foundations of Computer Science. November 7–9, 1983, IEEE, Tucson, USA. IEEE, 1983, рр. 393–402.
[2] Лобанов А.В., Сиренко В.Г. Проблема отказоустойчивости в сетецентрических информационно-управляющих системах. Образовательные ресурсы и технологии, 2014, № 2 (5), с. 115–121.
[3] Эйкхофф Й. Бортовые компьютеры, программное обеспечение и полетные операции. Введение. Москва, Техносфера, 2018, 334 с.
[4] 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.
[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. URL: http://citeseer.ist.psu.edu/anceaume97taxonomy.html
[6] Cristian F., Aghili H., Strong R., Dolev D. Atomic broadcast: from simple message diffusion to byzantine agreement. Proceedings of 15th International Symposium on Fault-Tolerant Computing Systems. June 29, 1985, IEEE, Ann Arbor-USA. IEEE, 1985, pp. 200–206.
[7] 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.
[8] Ковязина Д.Р. Автоматическая калибровка и синхронизация времени во встраиваемых вычислительных системах. Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2009, № 2 (60), с. 87–93.
[9] Словарь русских синонимов. URL: https://dic.academic.ru/dic.nsf/dic_fwords/10911 (дата обращения 03.02.2021).
[10] IEEE Std 1588TM–2008. Revision of IEEE Std 1588–2002. IEEE Instrumentation and Measurement Society, 2008, 269 р.
[11] Eidson J.C. Measurement, control and communication using. IEEE 1588 (Advances in Industrial Control), Springer, 2006, 283 р.
[12] Lamport L., Melliar-Smith P.M. Synchronizing clocks in the presence of faults. Journal of the ACM, 1985, vol. 32, no. 1, рр. 52–78.
[13] Lamport L. The implementation of reliable distributed multiprocess systems. Computer Network, 1978, vol. 2, pp. 95–114.
[14] 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
[15] 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. ACM, New York, 1984, pp. 504–511.
[16] 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
[17] Dolev D., Halpern J.Y., Strong H.R. On the possibility and impossibility of achieving clock synchronizati on. Proceedings of 16th Annual ACM Symposium on Theory of Computing, April, 30 — May, 2, 1984, Washington, D.C. ACM, New York, 1984, pp. 504–511.
[18] Ramanathan P., Shin K.G., Butler R.W. Fault-tolerant clock synchronization in distributed systems. Computer, 1990, vol. 23, no. 10, рр. 33–42. DOI: 10.1109/2.58235
[19] Paulitsch M., Steiner W. Fault-tolerant clock synchronization for embedded distributed multi-cluster systems. Proceedings of 15th Euromicro Conference “Real-Time Systems”, July, 2–4, 2003, Porto, Portugal. New York, IEEE, 2003, pp. 249–256. DOI: 10.1109/EMRTS.2003.1212750
[20] Ramanathan P., Kandlur D.D., Shin K.G. Hardware-assisted software clock synchronization for homogeneous distributed systems, IEEE Transactions on Computers, 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, vol. 77, iss. 1, 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. Proceedings of the 3rd Annual IEEE Symposium 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 C., Cristian F. An optimal internal clock synchronization algorithm. Proceedings of the 10th Annual Conference “Computer Assurance. COMPASS — 95, Systems Integrity, Software Safety and Process Security, June 26–30, 1995, IEEE. New York, IEEE, 1995, рр. 187–196. DOI: 10.1109/CMPASS.1995.521898
[24] Schneider F. Understanding protocols for Byzantine clock synchronization. Technical Report, 1987, p. 859.
[25] Mills D.L. Internet time synchronization: the network time protocol. IEEE Transactions on Computers, 1991, vol. 39, no. 10, pp. 1482–1493.
[26] Kopetz H., Ochsenreiter W. Clock synchronization in distributed real-time computer systems. IEEE Transactions on Computers, 1987, C-36, no. 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.806739
[28] Srikanth Т.K., Toueg S. Optimal clock synchronization. Journal of the ACM, 1987, vol. 34, no. 3, pp. 626–645.
[29] Verissimo P., Casimiro A., and Rodrigues L. Cesiumspray: a precise and accurate global time service for large scale systems. Journal of Real-Time Systems, 1997, vol. 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, vol. 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, 1989, vol. 15, no. 7, pp. 847–853.
[32] 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
[33] Fetzer C., Cristian F. Lower bounds for function based clock synchronization. Proceedings of 13th International Symposium 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, vol. 12, no. 2, pp. 123–172.
[35] Arvind K. Probabilistic clock synchronization in distributed systems. IEEE Transactions on Parallel and Distributed Systems, 1994, vol. 5, no. 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. Ithaca, NY, Cornell University, 1986. URL: https://hdl.handle.net/1813/6575 (дата обращения 03.02.2021).
[38] Simons B., Lundelius-Welch J., Lynch N. An overview of clock synchronization. Asilomar Workshop on Fault-tolerant Distributed Computing Conference, 1990, vol. 448, pp. 84–96.
[39] Liskov B. Practical uses of synchronized clocks in distributed systems. Distributed Computing, Periodicals Distributed Computing, 1993, vol. 6, no. 4, pp. 211–219. https://doi.org/10.1007/BF02242709