On the computational complexity of cascade GL-models for fault-tolerant multiprocessor systems

Скорочена інформація про документ
dc.contributor.authorRomankevich, Vitaliy A.
dc.contributor.authorMorozov, Kostiantyn V.
dc.contributor.authorRomankevich, Alexei M.
dc.contributor.authorNikishyn, Yehor O.
dc.date.accessioned2026-05-14T12:19:23Z
dc.date.available2026-05-14T12:19:23Z
dc.date.issued2025
dc.description.abstractThe article addresses the problem of evaluating the computational complexity of basic cascade GL-models used for modeling the behavior of fault-tolerant multiprocessor systems in the flow of failures. The purpose of this work is to reduce the complexity of such models by optimal selection of their parameters. It has been demonstrated that a single system usually corresponds to an entire family of cascade GL-models, differing in cascade depth and parameters, with each having its own computational complexity. To simplify the process of modeling the system behavior under a flow of failures, it is advisable to choose the cascade GL-model configuration with the lowest complexity. However, additional constraints on the model, such as cascade depth limitations, must also be considered. This work applies an empirical-analytical research method. An analysis of computational complexity for cascade GLmodels was conducted using specially developed software, which automated model construction for various combinations of parameters. Subsequently, a comparative analysis of the complexity of their edge function expressions was performed to identify dependencies on parameter values. Experimental studies were carried out for fault-tolerant multiprocessor systems with varying numbers of processors and different maximum allowable failure multiplicities (but not exceeding half of the total number of processors in the system). It was shown that cascade GL-models typically have significantly lower computational complexity compared to standard basic GL-models, especially for systems with a small maximum number of allowed failures. However, in cases where the allowed number of failures equals or exceeds half of the processor count, standard models may become less complex. Based on the conducted analysis, practical recommendations for selecting the parameters of cascade GL-models were formulated for the first time. In particular, the lowest complexity is achieved when the fault tolerance coefficient of the auxiliary model is minimized at each cascade level; however, this leads to a maximal cascade depth. If cascade depth is limited, the lowest complexity is achieved by evenly or nearly evenly distributing the fault-tolerance coefficients among auxiliary models. If an even distribution is impossible, it is advisable to place higher-value coefficients at deeper cascade levels. Experimental results demonstrate that the application of the proposed recommendations can significantly reduce the overall complexity of edge function expressions in the cascade GL-model compared to the basic GL-model, with the effectiveness of the approach increasing as the system size grows.
dc.description.abstractotherРоботу присвячено проблемі оцінки обчислювальної складності базових каскадних GL-моделей поведінки відмовостійких багатопроцесорних систем у потоці відмов. Метою роботи є зменшення складності таких моделей шляхом вибору їх параметрів. Показано, що одній системі зазвичай може відповідати ціле сімейство каскадних GL-моделей, які відрізняються глибиною та параметрами каскаду, причому кожна з них має власну обчислювальну складність. З метою спрощення процесу моделювання поведінки системи у потоці відмов доцільно обирати таку конфігурацію каскадної GLмоделі, яка має найменшу складність. Водночас необхідно враховувати можливі додаткові обмеження на модель (наприклад, обмеження на глибину каскаду). У роботі застосовано емпірико-аналітичний метод дослідження. Здійснено аналіз обчислювальної складності каскадних GL-моделей: за допомогою спеціально розробленого програмного забезпечення проведено автоматизовану побудову моделей для різних комбінацій параметрів, після чого виконано порівняння складності виразів їхніх реберних функцій з метою виявлення залежностей від значень параметрів. Експериментальні дослідження проведено для відмовостійких багатопроцесорних систем із різною кількістю процесорів і різною максимально допустимою кратністю відмов (але не більшою за половину загальної кількості процесорів у системі). Показано, що каскадні GL-моделі зазвичай мають суттєво нижчу обчислювальну складність порівняно зі звичайними базовими GL-моделями, особливо для систем із невеликою максимально допустимою кратністю відмов. Водночас у випадках, коли ця кратність дорівнює або перевищує половину кількості процесорів, звичайні моделі можуть виявитися менш складними. На основі проведеного аналізу вперше сформульовано практичні рекомендації щодо вибору параметрів каскадної GL-моделі. Зокрема, найменшої складності вдається досягти, коли на кожному рівні каскаду коефіцієнт відмовостійкості допоміжної моделі є мінімальним можливим, проте в цьому випадку глибина каскаду стає максимальною. Якщо ж глибина каскаду обмежена, найменша складність досягається за умов рівномірного або близького до рівномірного розподілу коефіцієнтів відмовостійкості допоміжних моделей (якщо рівномірного розподілу досягти неможливо, доцільно розміщувати коефіцієнти з більшими значеннями на останніх рівнях каскаду). Результати проведених експериментів демонструють, що застосування запропонованих рекомендацій дозволяє суттєво знизити загальну складність виразів реберних функцій каскадної GL-моделі порівняно з базовою GL-моделлю, причому ефективність підходу зростає зі збільшенням розмірів системи.
dc.format.pagerangeP. 245-258
dc.identifier.citationOn the computational complexity of cascade GL-models for fault-tolerant multiprocessor systems [Electronic resource] / Vitaliy A. Romankevich, Kostiantyn V. Morozov, Alexei M. Romankevich, Yehor O. Nikishyn // Herald of advanced information technology. — 2025. — Vol. 8, № 2. — P. 245-258. — Bibliogr.: 45 ref. — Title from screen.
dc.identifier.doihttps://doi.org/10.15276/hait.08.2025.16
dc.identifier.orcid0000-0003-4696-5935
dc.identifier.orcid0000-0003-0978-6292
dc.identifier.orcid0000-0001-5634-8469
dc.identifier.orcid0009-0008-9772-0261
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/80865
dc.language.isoen
dc.publisherOdesa Polytechnic National University, Institute of Computer Systems
dc.publisher.placeOdesa
dc.relation.ispartofHerald of advanced information technology, 2025, Vol. 8, № 2
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subjectCascade GL-models
dc.subjectfault-tolerant multiprocessor systems
dc.subjectcomputational complexity
dc.subjectbasic systems
dc.subjectparameters adjustment
dc.subjectreliability assessment
dc.subjectкаскадні GL-моделі
dc.subjectвідмовостійкі багатопроцесорні системи
dc.subjectобчислювальна складність
dc.subjectбазові системи
dc.subjectвибір параметрів
dc.subjectоцінка надійності
dc.subject.udc004.05
dc.titleOn the computational complexity of cascade GL-models for fault-tolerant multiprocessor systems
dc.title.alternativeПро обчислювальну складність каскадних GL-моделей відмовостійких багатопроцесорних систем
dc.typeArticle

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
8_Romankevich_On_the_computational_complexity.pdf
Розмір:
1.24 MB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
8.98 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Статті (СПСКС)