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

Abstract

The 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 GL-models 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.