Computational experiment on constructing fault-tolerant graph implementations with up to 9 vertices

Abstract

In many applications, failure of a critical element of technical device or system where computers are used, outages or malfunctions can be expensive or even disastrous and can lead to progressive collapse. It is necessary to provide the ability to tolerate faults by detecting failures and isolate defect modules so that the rest of the system can operate correctly. That is, such a system should be fault-tolerant. To study the problem of complete fault tolerance in 1976 J.P. Hayes proposed a graph-based model. Later in 1993 and 1996 J.P. Hayes together with F. Harary proposed two models: for node fault tolerance (NFT) and for edge fault tolerance ( EFT). In this paper, we study only a model for element failures. The construction of a system resistant to the failure of k elements means the construction of a vertex k-extension for a graph corresponding to the system. Optimality requires that the number of additional elements (vertices) and the connections between them (edges) be as small as possible. The task of constructing minimal vertex k-extensions is computationally complex. This article will present the results of constructing graphs from vertices of small size to up to 9 vertices and minimal vertex 2-extensions for 7- and 8-vertex graphs. In addition, we present results on extensions of meshes and tori with up to 12 vertices.