ИССЛЕДОВАНИЕ СТРУКТУРНЫХ ХАРАКТЕРИСТИК РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ НА ОСНОВЕ ГРАФОВ С МНОЖЕСТВЕННЫМИ РАЗНОТИПНЫМИ СВЯЗЯМИ
Аннотация
В статье рассмотрены вопросы построения отказоустойчивых вычислительных
систем, в части структуры и резервирования. При проектировании распределенных вычис-
лительных систем (ВС) возникает необходимость учета большого количества факторов,
влияющих на производительность, надежность и отказоустойчивость. Для распределен-
ных ВС к таким факторам относятся, в том числе структурные характеристики. В ра-
боте представлены графики зависимости вероятности безотказной работы ПУ распреде-
ленной вычислительной системы от характеристик ее структуры. Применение перспек-
тивных способов резервирования, таких как резервирование производительности, сущест-
венно повышает сложность задачи проектирования структуры. При резервировании про-
изводительности взамен ввода в систему специальных резервных узлов предполагается
использование избыточных вычислительных ресурсов внутри задействованных процессор-
ных узлов (ПУ). В случае отказа узла его задачи перераспределяются на свободный резерв
работоспособных узлов. Для реализации такого способа резервирования системы требует-
ся организация многопрограммного режима работы, когда на каждом узле могут одно-
временно выполняться несколько задач. Необходимость обеспечения мультипрограммного
режима работы приводит к увеличению количества конфигураций системы, подлежащих
анализу на этапе проектирования и в случае реконфигурации при отказе. Для снижения
трудоемкости анализа отдельно взятой конфигурации предложен подход на основе графов
с множественными и разнотипными связями. Использование моделей на основе таких гра-
фов позволяет представить структуру вычислительной системы с учетом мультипро-
граммной обработки информации и при этом существенно сократить время вычисления
базовых характеристик за счет применения связей в виде вектора, позволяющих объеди-
нить несколько разнотипных связей.
Литература
computing systems: textbook]. 2nd ed., reprint. and add. Moscow: Izd-vo MGTU im.
N.E. Baumana, 2008, 520 p.
2. Zhang Y., Jiang J. Bibliographical review on reconfigurable fault-tolerant control systems,
Annual Reviews in Control, 2008, Vol. 32 (2), pp. 229-252.
3. Kalyaev I., Melnik E., Korovin I., Klimenko A. and Schaefer G. A Fog-computing Based Method of
Information and Control System Reliability Enhancement, 7th International Conference on Informatics,
Electronics and Vision & 7th International Symposium in Computational Medical and
Health Technology. Piscataway Piscataway, New Jersey: IEEE, 2008, pp. 582-587.
4. Akkaya M. Fault tolerance Mechanisms in Distributed Systems, Int. J. Communications, Network
and System Sciences, 2015, Vol. 8, pp. 478-482.
5. Kuznetsov A.A., Kishkan V.V. Issledovanie grafov Keli konechnykh dvuporozhdennykh
bernsaydovykh grupp perioda sem' [The Cayley graphs of finite two-generator burnside groups
of exponent 7], Sibirskiy zhurnal nauki i tekhnologiy [Siberian Journal of Science and Technology],
2018, Vol. 19, No. 2, pp. 217-222. Doi: 10.31772/2587-6066-2018-19-2-217-222.
6. Parkhomenko P.P. Shaped lattice graphs as models of the multiprocessor computer systems,
Automation and Remote Control, 2005, Vol. 66, pp. 492-502.
7. Boccalettia S. Bianconic G., Criadod R., del Geniof C.I., Gómez-Gardeñesi J., Romanced M.,
Sendiña-Nadalj I., Wangk Z., Zaninm M. The structure and dynamics of multilayer networks,
Preprint submitted to Physics Reports July 16, 2014, 157 p.
8. Contractor N.S. Monge P.R., Leonardi P.M. Multidimensional networks and the dynamics of
sociomateriality: bringing technology inside the network, International Journal of Communication,
2011, No. 5, pp. 682-720.
9. Muntyan E.R. Realizatsiya nechetkoy modeli vzaimodeystviya ob"ektov slozhnykh
tekhnicheskikh sistem na osnove grafov [Realization of fuzzy model of objects interaction inside
a complex technical systems based on graphs], Programmnye produkty i sistemy [Software
& Systems], 2019, Vol. 32, No. 3, pp. 411-418. Doi:10.15827/0236-235X.127.411-418.
10. Muntyan E.R. Predstavlenie znaniy v graf-modelyakh slozhnykh tekhnicheskikh sistem [Representation
of knowledge in graph models of complex technical systems], Informatizatsiya i
svyaz' [Informatization and communication], 2020, No. 3, pp. 12-16. Doi: 10.34219/2078-
8320-2020-11-3-12-16.
11. Muntyan E.R. Trekhurovnevaya model' predstavleniya znaniy na osnove grafov [Three-level
model of knowledge representation based on graphs], Izvestiya YuFU. Tekhnicheskie nauki
[Izvestiya SFedU. Engineering Sciences], 2019, No. 5, pp. 145-157. Doi: 10.23683/2311-
3103-2019-5-145–157.
12. Averkin A.N., Batyrshin I.Z. i dr. Nechetkie mnozhestva v modelyakh upravleniya
iskusstvennogo intellekta [Fuzzy sets in artificial intelligence control models], ed. by
D.A. Pospelova. Moscow: Nauka, 1986.
13. Sampes M. Caylay graphs as interconnection networks: A case study, Proc. of the Inter. Conf.
Parsells’96. Berlin: Akademie-Verlag. 1996, pp. 97-106.
14. Dmitriev Yu.K. Analiz samodiagnostiruyushchikhsya svoystv struktur raspredelennykh zhivuchikh
vychislitel'nykh sistem [Analysis of self-diagnosing properties of structures of distributed tenacious
computing systems], Avtometriya [Auto-measurement], 1996, No. 5, pp. 71-84.
15. Vorob'ev V.A., Kornev V.V. Nekotorye voprosy teorii struktur odnorodnykh vychisli-tel'nykh
sistem Vychislitel'nye sistemy [Some questions of the theory of structures of homogeneous
computing systems], Voprosy teorii i postroeniya VS [Questions of the theory and construction
of CS]. Novosibirsk. 1974, Issue 60, pp. 3-16.
16. Monakhov O.G., Monakhova E.A. Parallel'nye sistemy s raspredelennoy pamyat'yu: struktury i
organizatsiya vzaimodeystviy [Parallel Systems with Distributed Memory: Structures and Organization
of Interactions]. Novosibirsk: Izd-vo SO RAN, 2000, 242 p.
17. Ore O. Teoriya grafov [Theory of graphs]: transl. from engl. Moscow: Nauka, 1968, 352 p..
18. Klimenko A.B., Mel'nik Ya.E. Issledovanie vozmozhnosti primeneniya kontseptsii tumannykh
vychisleniy i tekhnologii raspredelennogo reestra pri postroenii informatsionnoupravlyayushchikh
sistem [Investigation of the possibility of applying the concept of fog computing
and distributed registry technology in the construction of information and control systems],
Izvestiya TulGU. Tekhnicheskie nauki [News of TulSU. Technical sciences], 2021,
No. 2, pp. 19-27.
19. Melnik E., Klimenko A., Klimenko V. A recovery technique for the fog-computing-based information
and control systems, Advances in Intelligent Systems and Computing, 2019, Vol. 860,
pp. 216-227.
20. Melnik E.V., Klimenko A.B. A workload distribution problem model and online constraint
forming technique for the control systems in the fog-computing environment, Journal of Physics:
Conference Series, 2019, Vol. 1333, pp. 042014. Doi: 10.1088/1742-6596/1333/4/042014.
21. Melen'tev V.A. Analiticheskiy podkhod k sintezu regulyarnykh grafov s zadannymi
znacheniyami poryadka, stepeni i obkhvata [Analytical approach to the synthesis of regular
graphs with given values of order, degree, and girth], Prikladnaya diskretnaya matematika
[Applied Discrete Mathematics], 2010, No. 2 (8), pp. 74-86.
22. Muntyan E.R., Melnik E.V. The graph-based analysis of structural delays in distributed
multiprogram systems of information processing, Journal of Physics: Conference Series, 2020,
Vol. 1661 (1). Doi: 10.1088/1742-6596/1661/1/012061.
23. Muntyan E.R. Programmnyy modul' dlya predstavleniya aktorov i otnosheniy mezhdu
aktorami na osnove grafov. Svid. o gos. reg. programmy dlya EVM № 2018665499, zareg.
05.12.2018 [Certificate of official registration of a computer program No. 2018665499,
“A software module for representing actors and relationships between actors based on graphs”,
registered 05.12.2018]. Moscow: Rospatent, 2018.
24. Muntyan E.R. Razrabotka i issledovanie modeley grafov i gipergrafov s uchetom
mnozhestvennykh i raznotipnykh svyazey: avtoref. dis. … kand. tekhn. nauk [Development
and research of models of graphs and hypergraphs taking into account multiple and different
types of edges: cand. of eng. sc. diss.] (05.13.17). Taganrog: YuFU, 2020, 20 p.
25. Kolodenkova A.E. and Muntyan E.R. Researches of interaction of actors with use fuzzy
hypergraph and cognitive modeling, Papers in English 14th International scientific-techical
conference on actual problems of electronics instrument engineering: IEEE, 2018, Vol. 8,
pp. 127-131. Doi: 10.1109/APEIE.2018.8545550.
