Moving redundancy of tolerant elements

Redundancy is one of the primary ways of improving dependability. In particular, structural redundancy is used. In such cases fail-safe operation of elements, devices and systems can be ensured. Fail-safety can enable mitigation of both faults and failures. The paper examines the matter of increasing dependability by means of the so-called sliding redundancy that ensures the health of systems of n elements with m redundant elements that can replace any of the main elements. It is proposed to improve sliding redundancy through recovery of elements out of a number of failed elements that have retained some functionality (basis). For example, the basis of the logical (Boolean) function in terms of Post’s theorem is available if such function is not a zero-preserving function, not a one-preserving function, not a self-dual function, not a line function, not a monotone function. Previously, the author proposed the so-called functionally complete tolerant logical functions (FCTF) that do not only possess functional completeness but retain it under the specified failure model. Then even a failed element remains functionally complete, yet with reduced capabilities, e.g. becomes a 2OR-NOT, though the FCTF can be implemented with an element 2AND-2OR-NOT. In this case the recovery of the original function requires several 2OR-NOT elements. However, the diagnostics of such elements and their reconfiguration in case of failure are problematic. This approach can be interpreted with logic recovery of programmable logic devices (PLD) that is based on the so-called Look Up Tables (LUT) that are memory devices based on 16:1 multiplexers. The circuit is a transmitting transistor tree. If they fail, the healthy half of LUT can be used. By means of reconfiguration using standard PLD facilities that contain local and global connections matrix, such “semi-LUTs” can be transformed into LUTs whose functions are equivalent to initial ones. That equals to an increase of the number of redundant elements. Sliding redundancy with recovery of elements out of several failed ones that retained the basis can be used in critical system applications when repair or replacement of elements is impossible. The article proposes a formula that takes such recovery into consideration, analyzes the special features of such redundancy and evaluates the advantages for dependability.

1. GOST 27.002-89. Industrial product dependability. General concepts. Terms and definitions. Moscow: Izdatelstvo standartov; 1990.

2. Shubinsky IB. Nadiozhnye otkazoustoychivye informatsionnye systemy. Metodi sinteza [Dependable failsafe information systems. Synthesis methods]. Ulianovsk: Oblastnaya tipografia Pechatny dvor; 2016.

3. Vasiliev NP, Shubinsky IB. Analiticheskaya otsenka veroiatnosti ouspeshnoy adaptatsii k otkazam modulnykh vychislitelnykh sistem s mnogourovnevoy aktivnoy zashchitoy [Analytical evaluation of the probability of successful adaptation to failures of modular computer systems with multilevel active protection]. Izvestia vysshykh ouchebnykh zavedeniy. Priborostroenie [Journal of higher educational establishments. Instrument engineering]. 1994; 37: 3 – 4. Russian.

4. Tyurin SF. Problema sokhranenia funktsionalnoy polnoty boulevykh funktsiy pri “otkazakh” argumentov [The problem of maintaining the functional completeness of Boolean functions in case of argument “failure”]. Avtomatika i telemekhanika [Automation and remote control]. 1999; 9: 176 – 186. Russian.

5. Strogonov А, Tsybin S. Programmiruemaia kommutatsia PLIS: vzgliad iznutri [Software switching of FPGA: a look from the inside]. Available from: http://www.kit-e.ru/articles/plis/2010_11_56.php (accessed 16.10.2016).

6. Tyurin SF, Gromov OA. A residual basis search algorithm of fault-tolerant programmable logic integrated circuits. Russian Electrical Engineering. 2013; 84 (11): 647 – 651. DOI: 10.3103/S1068371213110163

7. Tyurin SF, Grekov AV. Functionally Complete Tolerant Elements. International Journal of Applied Engineering Research. 2015; 10 (14): 34433 – 34442.

8. Parfentiy AN, Khakhanov VI, Litvinova EI. Modeli infrastruktury servisnogo obsluzhivania tsifrovykh sistem na kristallakh [Models of infrastructure of digital systems on a chip maintenance service]. ASU i pribory avtomatiki [ACS and automatic devices]. 2007; 138: 83 – 99. Russian.

9. Carmichael C. Triple Module Redundancy Design Techniques for Virtex FPGAs. Available from: https://www.xilinx.com/support/documentation/application_notes/xapp197.pdf (accessed 07.12.2016).