Vitaliy Romankevich; Kostiantyn Morozov; Alexei Romankevich; Petro Malezhyk; Lefteris Zacharioudakis

A Generalized Method for Constructing Graph-Logical Models of Non-Basic Fault-Tolerant Multiprocessor Systems via Model Combination

PDF (1694KB), PP.254-269

Views: 0 Downloads: 0

Author(s)

Vitaliy Romankevich ¹ Kostiantyn Morozov ^1,* Alexei Romankevich ¹ Petro Malezhyk ¹ Lefteris Zacharioudakis ¹

1. Department of System Programming and Specialized Computer Systems. National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, 37, Peremogy Ave. Kyiv, 03056, Ukraine

* Corresponding author.

DOI: https://doi.org/10.5815/ijem.2026.03.15

Received: 28 Aug. 2025 / Revised: 25 Feb. 2026 / Accepted: 28 Mar. 2026 / Published: 8 Jun. 2026

Index Terms

GL-models, fault-tolerant multiprocessor systems, non-basic systems, reliability evaluation, failure behavior, equivalent transformations

Abstract

The paper proposes a generalized method for constructing graph-logical models of the failure behavior of fault-tolerant multiprocessor systems. Such models are used for evaluating system reliability by means of statistical experiments based on simulation of failure behavior. The method is applicable to non-basic systems whose failure behavior cannot be characterized solely by the number of failed components and therefore requires more flexible modeling approaches. The proposed method is based on combining auxiliary models corresponding to different operating conditions of the system into a single model that correctly represents the overall failure behavior. In contrast to existing approaches, it imposes no restrictions on the graph structures of the auxiliary models and does not depend on the specific procedures used for their construction. The key idea of the approach is to integrate such models under a set of mutually exclusive logical conditions, each of which determines the applicability of a particular auxiliary model for a given system state. A set of model transformations is introduced, and it is shown that these transformations preserve model equivalence, that is, correspondence to the same failure behavior of the system. It is demonstrated that these transformations are sufficient to transform auxiliary models to graphs with identical structures, which is a necessary condition for their combination within the proposed framework. Several illustrative examples of the application of the method are provided. The correctness of the constructed models is validated through analysis of representative system states and through exhaustive evaluation over all possible states. The results for the considered example indicate that the proposed method can construct models that accurately represent system failure behavior while yielding more compact graph structures compared to the existing approach. At the same time, comparable logical complexity is maintained. The evaluation is limited to a representative example and exhaustive analysis of system states, and further validation on a broader class of systems remains a direction for future work.

Cite This Paper

Vitaliy Romankevich, Kostiantyn Morozov, Alexei Romankevich, Petro Malezhyk, Lefteris Zacharioudakis, "A Generalized Method for Constructing Graph-Logical Models of Non-Basic Fault-Tolerant Multiprocessor Systems via Model Combination", International Journal of Engineering and Manufacturing (IJEM), Vol.16, No.3, pp.254-269, 2026. DOI:10.5815/ijem.2026.03.15

Reference

[1]Yalcinkaya, E., Maffei, A., & Onori, M. (2017). Application of Attribute Based Access Control Model for Industrial Control Systems. International Journal of Computer Network and Information Security, 2, 12-21. DOI: 10.5815/ijcnis.2017.02.02.
[2]Labane, C., Mekkaoui, M., Zemalache, M. K., & Meddahi, Y. (2024). Model Predictive Control for Nonlinear Inverted Pendulum Mobile Robot with Disturbance. International Journal of Computer Network and Information Security, 16(4), 1919-1929.
[3]Gokhale, S., Dalvi, A., & Siddavatam, I. (2020). Industrial Control Systems Honeypot: a Formal Analysis of Conpot. International Journal of Computer Network and Information Security, 6, 44-56. DOI: 10.5815/ijcnis.2020.06.04.
[4]Nazarova, O. S., Osadchyy, V. V., & Rudim, B. Y. (2023). Computer Simulation of the Microprocessor Liquid Level Automatic Control System. Applied Aspects of Information Technology, 6(2), 163-174. DOI: 10.15276/aait.06.2023.12.
[5]Khilenko, V. V., Denysiuk, S. P., Bielokha, H. S., Stepanov, O. V., & Kang, L.-W. (2026). Optimizing the Control of a Transactive Energy System with Periodically Changing Architecture Based on Internet of Energy. Herald of Advanced Information Technology, 9(1), 85-99. DOI: 10.15276/hait.09.2026.07.
[6]Kotov, D. O. (2022). A Generalized Model of an Adaptive Information-Control System of a Car with Multi-Sensor Channels of Information Interaction. Applied Aspects of Information Technology, 5(1), 25-34. DOI: 10.15276/aait.05.2022.2.
[7]Khudov, H., Kivshar, O., Khizhnyak, I., Taran, I., & Solomonenko, Y. (2026). Method for Predicting the Flight Path of Long-Range Unmanned Aerial Systems Based on the Elite Ants Algorithm. Advanced Information Systems, 10(2), 52-59. DOI: 10.20998/2522-9052.2026.2.06.
[8]Barabash, O., & Kyrianov, A. (2023). Development of Control Laws of Unmanned Aerial Vehicles for Performing Group Flight at the Straight-Line Horizontal Flight Stage. Advanced Information Systems, 7(4), 13-20. DOI: 10.20998/2522-9052.2023.4.02.
[9]Nair, P. P., Sarkar, A., & Biswas, S. (2021). Fault-Tolerant Real-Time Fair Scheduling on Multiprocessor Systems with Cold-Standby. IEEE Transactions on Dependable and Secure Computing, 18(4), 1718-1732. DOI: 10.1109/TDSC.2019.2934098.
[10]Pathan, R. M. (2017). Real-time scheduling algorithm for safety-critical systems on faulty multicore environments. Real-Time Systems, 53(1), 45-81. DOI: 10.1007/s11241-016-9258-z.
[11]Drozd, O. V., Rucinski, A., Zashcholkin, K. V., Drozd, M. O., & Sulima, Y. Y. (2021). Improving FPGA Components of Critical Systems Based on Natural Version Redundancy. Applied Aspects of Information Technology, 4(2), 168-177. DOI: 10.15276/aait.02.2021.4.
[12]Ibrahimov, B., Hasanov, A., & Hashimov, E. (2024). Research and Analysis of Efficiency Indicators of Critical Infrastructures in the Communication System. Advanced Information Systems, 8(2), 58-64. DOI: 10.20998/2522-9052.2024.2.07.
[13]Mohlabeng, M., & Vallabhapurapu, S. (2025). Securing Critical Infrastructure: Design, Incidents, and Protection Strategies Railway Cable. International Journal of Computer Network and Information Security, 17(2), 383-399.
[14]Shavarskyi, M. A., & Kryvechuk, Y. P. (2026). Anomaly Detection on Time Series Data for Autonomous Robot Operation. Herald of Advanced Information Technology, 9(1), 46-59. DOI: 10.15276/hait.09.2026.04.
[15]Arfat, Y., & Eassa, F. E. (2016). A Survey on Fault Tolerant Multi Agent System. International Journal of Information Technology and Computer Science, 9, 39-48. DOI: 10.5815/ijitcs.2016.09.06.
[16]Belarbi, M. (2015). Formal and Informal Modeling of Fault Tolerant Noc Architectures. International Journal of Intelligent Systems and Applications, 12, 32-42. DOI: 10.5815/ijisa.2015.12.03.
[17]Abbaspour, A., Mokhtari, S., Sargolzaei, A., & Yen, K. K. (2020). A Survey on Active Fault-Tolerant Control Systems. Electronics, 9(9), 1513. DOI: 10.3390/electronics9091513.
[18]Al-Allaf, A. F., & Farej, Z. K. (2023). Simulation-Based Fault-Tolerant Multiprocessors System. Telkomnika (Telecommunication Computing Electronics and Control), 21(2), 354-363. DOI: 10.12928/TELKOMNIKA.v21i2.24253.
[19]Chen, L., Feng, H., & Wu, J. (2025). A Path-Based Topology-Agnostic Fault Diagnosis Strategy for Multiprocessor Systems. IEEE Transactions on Computers, 74(6), 1886-1896. DOI: 10.1109/TC.2025.3543701.
[20]Rahdari, D., Rahmani, A. M., Aboutaleby, N., & Karambasti, A. S. (2015). A Distributed Fault Tolerance Global Coordinator Election Algorithm in Unreliable High Traffic Distributed Systems. International Journal of Information Technology and Computer Science, 7(3), 1-11. DOI: 10.5815/ijitcs.2015.03.01.
[21]Nazemi, E., Talebi, T., & Elyasi, H. (2015). Self-Healing Mechanism for Reliable Architecture with Focus on Failure Detection. International Journal of Intelligent Engineering and Electronic Business, 3, 32-38. DOI: 10.5815/ijieeb.2015.03.05.
[22]Arasteh, B. (2017). Enhancing Software Reliability against Soft-Error using Minimum Redundancy on Critical Data. International Journal of Computer Network and Information Security, 9(5), 21-30. DOI: 10.5815/ijcnis.2017.05.03.
[23]Sinha, B., Singh, A. K., & Saini, P. (2019). A Failure Detector for Crash Recovery Systems in Cloud. International Journal of Information Technology and Computer Science, 7, 9-16. DOI: 10.5815/ijitcs.2019.07.02.
[24]Raskin, L., Ivanchikhin, Y., Sukhomlyn, L., Sviatkin, I., & Korsun, R. (2022). Evaluation Model of the Recovery Processes of Non-Markovian Systems, Considering the Elements Unreliability Under Arbitrary Distribution Laws. Advanced Information Systems, 6(3), 28–35. DOI: 10.20998/2522-9052.2022.3.04.
[25]Huang, Y., Lin, L., Xu, L., & Hsieh, S.-Y. (2024). Probabilistic Reliability via Subsystem Structures of Arrangement Graph Networks. IEEE Transactions on Reliability, 73(1), 279-289. DOI: 10.1109/TR.2023.3301629.
[26]Myrnenko, M. D., & Shevel, V. V. (2025). Technological Platforms, Tools, and Standardization in the Unified Information Space for Automated Unmanned Aerial Vehicle Design. Applied Aspects of Information Technology, 8(3), 316-333. DOI: 10.15276/aait.08.2025.21.
[27]Wang, X., Li, S., Liu, F., & Fan, X. (2012). Reliability Analysis of Combat Architecture Model Based on Complex Network. International Journal of Engineering and Manufacturing, 2(2), 15-22. DOI: 10.5815/ijem.2012.02.03.
[28]Thomas, M., & Babak, B. (2017). Reliability Evaluation Metrics for Internet of Things Car Tracking System: a Review. International Journal of Information Technology and Computer Science, 9(2), 1-10. DOI: 10.5815/ijitcs.2017.02.01.
[29]Liu, X., Fan, W., He, J., Han, Z., & Chi, C.-H. (2025). Reliability Assessment of Multiprocessor System Based on Exchanged Crossed Cube Networks. Concurrency and Computation: Practice and Experience, 37(2), e8325. DOI: 10.1002/cpe.8325.
[30]Krasnobayev, V., Koshman, S., Nikolsky, S., & Kovalchuk, D. (2022). Mathematical Model of Computer System Reliability in Residual Classes. Advanced Information Systems, 6(4), 19–24. DOI: 10.20998/2522-9052.2022.4.03.
[31]Kuo, W., & Zuo, M. J. (2002). Optimal Reliability Modeling: Principles and Applications. Hoboken, NJ: John Wiley & Sons.
[32]Ahmed, W., & Wu, Y. W. (2013). A survey on reliability in distributed systems. Journal of Computer and System Sciences, 79(8), 1243-1255. DOI: 10.1016/j.jcss.2013.02.006.
[33]Wason, R., Soni, A. K., & Rafiq, M. Q. (2015). Estimating Software Reliability by Monitoring Software Execution through Opcode. International Journal of Information Technology and Computer Science, 7(9), 23-30. DOI: 10.5815/ijitcs.2015.09.04.
[34]Raskin, L., Sviatkin, I., Ivanchikhin, Y., & Korsun, R. (2022). Semi-Markov Reliability Models. Advanced Information Systems, 6(1), 70–74. DOI: 10.20998/2522-9052.2022.1.12.
[35]Kaswan, K. S., Choudhary, S., & Sharma, K. (2015). Software Reliability Modeling using Soft Computing Techniques: Critical Review. International Journal of Information Technology and Computer Science, 7(9), 90-101. DOI: 10.5815/ijitcs.2015.07.10.
[36]Kumari, P., & Jain, N. (2024). Evaluating the Impact of Scheduling Algorithms on Performance and Reliability in Delay-Tolerant Networks. International Journal of Computer Network and Information Security, 16(4), 1019-1025.
[37]Suo, B., Cheng, Y. S., Zeng, C., & Li, J. (2012). Calculation of Failure Probability of Series and Parallel Systems for Imprecise Probability. International Journal of Engineering and Manufacturing, 2(2), 79-85. DOI: 10.5815/ijem.2012.02.12.
[38]Jianu, M., Daus, L., Dragoi, V. F., & Beiu, V. (2023). Reliability Polynomials of Consecutive-k-out-of-n:F Systems Have Unbounded Roots. Networks, 82(3), 222-228. DOI: 10.1002/net.22168.
[39]Triantafyllou, I. (2020). m-Consecutive-k-out-of-n: F Structures with a Single Change Point. Mathematics, 8(12), 2203. DOI: 10.3390/math8122203.
[40]Gökdere, G., Gürcan, M., & Kılıç, M. (2016). A New Method for Computing the Reliability of Consecutive k-out-of-n:F Systems. Open Physics, 14(1), 166-170. DOI: 10.1515/phys-2016-0015.
[41]Yin, J., Balakrishnan, N., & Cui, L. (2022). Efficient Reliability Computation of Consecutive-k-out-of-n:F Systems with Shared Components. Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability, 224, 108549. DOI: 10.1177/1748006X221130540.
[42]Yin, J., & Cui, L. (2021). Reliability for Consecutive-k-out-of-n:F Systems with Shared Components Between Adjacent Subsystems. Reliability Engineering & System Safety, 210, 107532. DOI: 10.1016/j.ress.2021.107532.
[43]Chopra, G., & Ram, M. (2022). Linear Consecutive-k-out-of-n:G System Reliability Analysis. Journal of Reliability and Statistical Studies, 15(2), 669-692. DOI: 10.13052/jrss0974-8024.15211.
[44]Yi, H., Cui, L., & Gao, H. (2020). Reliabilities of Some Multistate Consecutive-k Systems. IEEE Transactions on Reliability, 69(2), 414-429. DOI: 10.1109/TR.2019.2897726.
[45]Eryilmaz, S., & Kan, C. (2011). Dynamic Reliability Evaluation of Consecutive-k-within-m-out-of-n:F System. Communications in Statistics: Simulation and Computation, 40(1), 58-71. DOI: 10.1080/03610918.2010.530366.
[46]Torrado, N. (2015). Tail Behaviour of Consecutive 2-within-m-out-of-n Systems with Nonidentical Components. Applied Mathematical Modelling, 39(15), 4586-4592. DOI: 10.1016/j.apm.2014.12.042.
[47]Amirian, Y., Khodadadi, A., & Chatrabgoun, O. (2020). Exact Reliability for a Consecutive Circular k-out-of-r-from-n:F System with Equal and Unequal Component Probabilities. International Journal of Reliability, Quality and Safety Engineering, 27(1), 2050003. DOI: 10.1142/S0218539320500035.
[48]Nashwan, I. (2021). Reliability and Failure Probability Functions of the m-Consecutive-k-out-of-n:F Linear and Circular Systems. Baghdad Science Journal, 18(2), 430. DOI: 10.21123/bsj.2021.18.2.0430.
[49]Triantafyllou, I. S. (2023). Combined m-Consecutive-k-out-of-n:F and Consecutive kc-out-of-n:F Structures with Cold Standby Redundancy. Mathematics, 11(12), 1-13. DOI: 10.3390/math11122597.
[50]Triantafyllou, I., & Koutras, M. (2014). Reliability Properties of (n, f, k) Systems. IEEE Transactions on Reliability, 63(1), 357-366. DOI: 10.1109/TR.2014.2299495.
[51]Cui, L., Lin, C., & Du, S. (2015). m-Consecutive-k,l-out-of-n Systems. IEEE Transactions on Reliability, 64(1), 386-393. DOI: 10.1109/TR.2014.2337091.
[52]He, S., Wang, C., Wu, Z., & Guan, Q. (2026). Reliability Analysis for Linear Multi-State (n, f, k) and <n, f, k> Systems. Reliability Engineering and System Safety, 272, 112245. DOI: 10.1016/j.ress.2026.112245.
[53]Lee, W. S., Grosh, D. L., Tillman, F. A., & Lie, C. H. (1985). Fault Tree Analysis, Methods and Applications: a Review. IEEE Transactions on Reliability, 34(3), 194-203. DOI: 10.1109/TR.1985.5222114.
[54]Romankevich, A., Feseniuk, A., Maidaniuk, I., & Romankevich, V. (2019). Fault-Tolerant Multiprocessor Systems Reliability Estimation using Statistical Experiments with GL-Models. Advances in Intelligent Systems and Computing, 754, 186-193. DOI: 10.1007/978-3-319-91008-6_19.
[55]Romankevich, A. M., Morozov, K. V., & Romankevich, V. A. (2022). On Determining the State of the Processors of a Multiprocessor System During its Testing. CEUR Workshop Proceedings, 3156, 1-12.
[56]Romankevich, A. M., Morozov, K. V., & Romankevich, V. A. (2022). Generalization of the Formal Method for Determining the State of Processors of a Multiprocessor System under Testing. Lecture Notes in Data Engineering and Communications Technologies, 134, 363-375. DOI: 10.1007/978-3-031-04812-8_31.
[57]Romankevich, V. A., Morozov, K. V., Shuryha, O. V., Romankevich, A. M., & Zacharioudakis, L. (2025). Enhancement of the Formal Method of Determining Processor States of a Multiprocessor System under Testing. Lecture Notes in Data Engineering and Communications Technologies, 242, 142-155. DOI: 10.1007/978-3-031-84228-3_12.
[58]Romankevich, A., Morozov, K., Romankevich, V., Halytskyi, D., & Zacharioudakis, E. (2023). Improved GL-Model of Behavior of Complex Multiprocessor Systems in Failure Flow. Lecture Notes in Data Engineering and Communications Technologies, 181, 236-245. DOI: 10.1007/978-3-031-36118-0_21.
[59]Romankevich, V. A., Morozov, K. V., Romankevich, A. M., Morozova, A. V., & Zacharioudakis, L. (2024). On the Modification of GL-Models by Adding Edges to a Cyclic Graph. Herald of Advanced Information Technology, 7(2), 185-198. DOI: 10.15276/hait.07.2024.13.
[60]Romankevich, V. A., Morozov, K. V., Romankevich, A. M., Morozova, A. V., & Zacharioudakis, L. (2024). On the Method of Building of Non-Basic GL-Models which are Formed on Combination of Edge Functions of Basic Models. Applied Aspects of Information Technology, 7(2), 175-188. DOI: 10.15276/aait.07.2024.13.
[61]Romankevich, V. A., Morozov, K. V., Romankevich, A. M., Halytsky, D. V., & Zacharioudakis, L. (2026). A Method for Constructing Non-Basic GL-Models by Combining Models with Arbitrary Graph Structures. Herald of Advanced Information Technology, 9(1), 30-45. DOI: 10.15276/hait.09.2026.03.
[62]Romankevich, V. A., Yermolenko, I. A., Morozov, K. V., & Romankevich, A. M. (2024). Graph-Logical Models for (n, f, k) and Consecutive-k-out-of-n Systems. Herald of Advanced Information Technology, 7(3), 296-308. DOI: 10.15276/hait.07.2024.21.
[63]Romankevich, V. A., Morozov, K. V., Romankevich, A. M., Halytsky, D. V., & Zhurba, A. V. (2025). GL-Models for Analyzing Multiprocessor Systems Tolerant to One and Two Failures. Applied Aspects of Information Technology, 8(1), 113-128. DOI: 10.15276/aait.08.2025.9.
[64]Zajicek, J., & Kamenicky, J. (2015). K-out-of-N Systems: Design, Operation and Preventive Maintenance. Safety and Reliability of Complex Engineered Systems – Proceedings of the 25th European Safety and Reliability Conference, ESREL 2015, 2323-2327. DOI: 10.1201/b19094-304.
[65]Wu, B., Tan, Z., & Che, A. (2026). Resilience Analysis of k-out-of-n Systems. Naval Research Logistics, 73(3), 352-369. DOI: 10.1002/nav.70017.
[66]Dembińska, A., & Nikolov, N. I. (2026). Reliability Properties of k-out-of-n Systems with Several Cold Standby Units. Journal of Computational and Applied Mathematics, 477, 117203. DOI: 10.1016/j.cam.2025.117203.
[67]Mannai, N., & Jarray, M. (2026). Optimal Design of k-out-of-n:G System under Load Redistribution and Stochastic Mission Duration. Reliability Engineering and System Safety, 269, 112029. DOI: 10.1016/j.ress.2025.112029.
[68]Wang, X., Zhao, X., Zhao, X., Chen, X., & Ning, R. (2024). Reliability Assessment for a Generalized k-out-of-n: F System under a Mixed Shock Model with Multiple Sources. Computers and Industrial Engineering, 196, 110459. DOI: 10.1016/j.cie.2024.110459.

International Journal of Engineering and Manufacturing (IJEM)