Series-parallel composition of graph-logical models of fault-tolerant multiprocessor systems

Abstract

The paper addresses the construction of composite graph-logical models describing the failure behavior of fault-tolerant multiprocessor systems. Such models can be used to evaluate system reliability measures through statistical experiments. Directly constructing a model of a complex system from its operability conditions can be labor-intensive; therefore, the initial problem may be decomposed into simpler constituents whose models are subsequently combined. The aim of the study is to establish relationships between the states of constituent two-terminal graphs and the state of the resulting graph under series and parallel composition. Three mutually exclusive classes are introduced to describe the state of a two-terminal graph: full two-terminal connectivity, separated two-terminal connectivity, and two-terminal disconnection. These classes are proved to cover all possible states of a two-terminal graph. Necessary and sufficient conditions are established for the resulting graph to belong to each class under series and parallel composition of its constituents. The resulting relationships make it possible to determine the state of a composite model from the states of its constituents and the method of their composition without reanalyzing the internal structure of each graph. Elementary single-edge graph-logical models are considered, and their suitability as basic constituents for constructing models with more complex behavior is demonstrated. The results are illustrated by constructing a composite graph-logical model of a fault-tolerant multiprocessor system that executes a task in stages and has alternative conditions for using processor resources. The model is formed by series-parallel composition of elementary single-edge models whose edge functions represent the conditions for completing individual stages. Exhaustive enumeration of the possible state vectors confirmed that connectivity of the resulting graph conforms to the specified system operability conditions. Future research should develop a formal algorithm for selecting constituent models and their composition directly from a system description, and should investigate the use of previously constructed multi-edge models as constituents.