A group-invariant approach to the synthesis of fault-tolerant systems (Q1377941)

A \(k\)-fault-tolerant system is understood as a system possessing the property to function regularly during a given time without loss of its functions and without lowering its efficiency when faults arise in the working of its components. It is utilized a connected graph model of the system so that the vertexes of the graph correspond to resources of the system and the edges -- to the channels between resources. It is assumed that only the vertices of the graph are subject to faults and the edges do not change, but the failed vertices are able to transmit the information. Assume that the system is given by a graph \(G_0\). One has to find such minimal redundant \(k\)-fault-tolerant graph \(G_r\) and \(G_0\subset G_r\), \(k\geq 1\), that in the case when any their \(k\) vertices fail, there will exist an isomorphic embedding of \(G_0\) into \(G_r\) The graph \(G_r\) has minimal redundancy with respect to the original graph \(G_0\) if: (i) \(G_0\subset G_r\), (ii) \(G_r\) has \(k\) span vertices for \(k\)-fault-tolerance, and (iii) no edge of the graph \(G_r\) can be removed without violating the condition of forming \(G_0\) when any \(k\) vertexes of \(G_r\) fail. There were find the necessary and sufficient conditions under which an \(m\)-vertex structure \(G_r\) became \(k\)-fault-tolerant with minimal redundancy equal to 1. It is given the method by which one can obtain all such \(G_r\).