A method for constructing non-basic GL-models by combining models with arbitrary graph structures

Abstract

The paper proposes a method for constructing GL-models of failure behavior for a special class of non-basic fault-tolerant multiprocessor systems. The considered class includes systems whose failure behavior is determined by the fulfillment of one of several conditions that depend on combinations of processor states and are specified by the corresponding Boolean expressions. When any of these conditions is satisfied, the system failure behavior can be described by an individual auxiliary model constructed using known methods. The objective of this study is to develop a generalized method for constructing models of such non-basic systems by combining multiple auxiliary models of arbitrary types into a single model that correctly represents the system failure behavior. The proposed method is based on modifying the edge functions of the auxiliary models using the Boolean expressions of the corresponding conditions, after which the modified models are combined by merging arbitrarily selected vertices of their graphs. It is shown that the resulting model reproduces the behavior of the corresponding auxiliary model under each condition and thus correctly describes the failure behavior of the original system. The scientific novelty of this work lies in the proposed approach to combining auxiliary models of a general form, which imposes no constraints on the structure of their graphs and, unlike existing approaches, does not require these models to be based on cycle graphs. This makes it possible to construct models for a wide class of non-basic fault-tolerant multiprocessor systems with complex operability conditions. A comparative analysis of the complexity of edge-function expressions in models constructed using the proposed method and those obtained by existing approaches is carried out on a set of representative examples, revealing a significant reduction in the complexity of such expressions. The case of parallel evaluation of edge-function values is considered separately, and a reduction in the maximum expression complexity is demonstrated, which is important for decreasing computation time. The practical significance of the work lies in the applicability of the proposed method to constructing models of complex non-basic fault-tolerant multiprocessor systems, as well as in reducing the complexity of analyzing their failure behavior. The presented examples and experimental results confirm the correctness of the constructed models and demonstrate the possibility of further simplification by eliminating edges with identically unit edge functions. The proposed approach can be used in the analysis and design of critical control systems, as well as in automated reliability assessment of non-basic fault-tolerant multiprocessor systems with a large number of components.