GL-models for analyzing multiprocessor systems tolerant to one and two failures

Abstract

The work is devoted to the problem of constructing GL-models of behavior in the fault flow of non-basic fault-tolerant multiprocessor systems. We consider systems that are fault-tolerant to any one failure, and under a certain condition – to any two failures of their processors. It is assumed that this condition is satisfied by a Boolean expression that depends on the states of the system's processors. To build models of such systems, we use the previously proposed method based on combining the expressions of the edge functions of auxiliary basic GL-models corresponding to 1- and 2-fault-tolerant systems. Two alternative ways of constructing auxiliary K(2, n) models are considered. It is shown that the obtained GL-models are based on the same cyclic graphs and differ only in the expressions of their edge functions. The complexity of the expressions of the edge functions of the obtained models is analyzed for the cases of using auxiliary GL-models of each type. The formulas for estimating the complexity of these expressions (the number of elementary logical operations) depending on the number of processors in the system, in particular, for cases when this number is a power of two, are obtained. Also, for the case of using one of the auxiliary models, the possibility of further simplification of the expressions of some of the edge functions is revealed. It is determined in which cases, namely, for what number of system processors, it is advisable to use auxiliary models of one or another type. Experiments confirm that the GL-models constructed in the above way adequately reflect the behavior of the system. Examples are given that demonstrate the application of the considered method of constructing non-basic GL-models and confirm the correctness of estimation the complexity of expressions of their edge functions when using auxiliary models of various types. It has also been shown that further simplification of the expressions for the edge functions in GL-models under construction is possible, particularly by reordering the edges in auxiliary models. However, this possibility has not been investigated in the general case within this article.