USE OF DEDUCED ESARY-PROSCHAN ASSESSMENTS FOR EVALUATION OF SYSTEM DEPENDABILITY

In [1-2] it is shown that the widely known Esary-Proschan assessments [3-6] (EPA) are NP-complete [7]. In the process of their calculation a mutual cross-over of those assessments occurs despite the fact that the procedure of enumeration of complete sets of simple chains (SChs) and simple cuts (SCus) is performed all the way. This is confirmed by special research of these paradoxical phenomena in EPA conducted in [8] that concludes that EPAs are not assessments, as assessments cannot be NP-complete. In [7] it is clearly stated that in general an enumeration of a complete set of SCh (or SCu) alone already is an NP-complete problem. It implies directly that any NP-complete method cannot be an assessment one. In [9-10] a number of problems are classified depending on the associated computational complexity. As we can see out of those presented the most favourable is the intellectual intensity, as it allows controlling the computational process in the most desirable way, i.e. allows implementing the forced interruption principle (FIP) in regards to the computational procedure that is assessed by a certain parameter. For example, the parameter of achieved relative computational error. It should be noted that the devices, mechanisms and other systems we deal with in real life are called automated because such man-machine systems implement the FIP at the discretion of the human operator. We deal much less with automatic systems. The aim of this paper is to set forth the formal rules that allows quite easily the conventional NPcomplete Esary-Proschan assessments to be transformed to the class of intelligent (IN-class) assessment methods that implement the FIP. Complete sets of SCh and SCu do not need to be enumerated here. Expanding the class of existing [1-6, 8, 11-29] methods that in one way or another implement the FIP is without a doubt a relevant problem for experts involved in structural dependability analysis of complex systems. It is an axiom that any of the tools of such system analysis, of which the exhaustive events (EE) are the “delivery nurse”, contributes to the design of structurally dependent systems, while developing at the same time the analysis tool system itself. Essentially, the problem consists in casting the classic EPAs in the form of logic symbol multiplication (LSM) of logical operands the method uses. The result consists in the fact that we remove the “hardships” of NP-completeness from the classic EPAs and obtain a sufficiently efficient analysis tool.

dependability, probability, two-pole network, simple chain, simple cut, working condition, faulty condition

1. Krivulets VG. Ob otsenke otsenok Esary-Proschana v zadachakh analiza strukturnoy nadiozhnosti setey sviazi [On the assessment of Esary-Proschan assessments as part of analysis of structural dependability of communication networks]. Proceedings of the 55th scientific session dedicated to the Radio Day. RNTORES im. AS Popova; 2000 [in Russian].

2. Filin BP. O predelnom razviazyvanii klatterov v otsenkakh Polesskogo granits kombinatornoy nadiozhnosti sluchainykh binarnykh sistem [On the ultimate clutter disentanglement in Polessky assessment of combinatorial dependability of random binary systems]. Avtomatika i telemekhanika 2005; 9: 149-189 [in Russian].

3. Esary J, Proschan F. Coherent Structures of Non-Identifical Components. Technometrics 1963; 5 (2): 191-209.

4. Esary J, Proschan F. The reliability of coherent systems in Redundancy techniques for computing systems . Moscow: Radio i sviaz; 1966.

5. Barlow R, Proschan F. Mathematical theory of reliability. Gnedenko BV, editor. Moscow: Sov. radio; 1978.

6. Барлоу Р., Прошан Ф. Статистическая теория надёжности и испытания на безотказность: . . Gnedenko BV, editor. Moscow: Nauka, 1969.

7. Garey M, Johnson D. Computers and intractability. Moscow: Mir; 1982.

8. Labutin AG, Filin BP. Ob uklonenii ot NP-polnoty v otsenkakh Esary-Proschana [On avoiding NP-completeness in Esary-Proschan assessments]. Avtomatika i lelemekhanika 2017 [in print] [in Russian].

9. Gadasin VA. Triada substantsiy v mikromire “Korpuskula – Sluchainost – Volna” [Triade od substances in the microworld Corpuscule – Eventuality – Wave]. Proceedings of VNII PVTI; 2015 [in Russian].

10. Gadasin VA. Aksiomatika kontepsii triad – triokhmernaya gruppa [Axiomatics of the concept of triad – threedimensional group]. Proceedings of the XV international conference The problem of safety of complex systems. Moscow: RAS ICS; 2007 [in Russian]. .

11. Polovko AM, Gurovich BI. Tekhnicheskaya kibernetika 1971;4:78 [in Russian].

12. Panteley VG, Shubinsy IB. Raschotnie metody otsenki nadiozhnosti priborov [Computational methods of devices dependability assessment]. Moscow: Mashinostroenie; 1974 [in Russian].

13. Shubinsky IB. Topologichskiy metod i algoritm opredelenia statsionarnykh pokazateley nadiozhnosti tekhnicheskikh sistem [Topological method and algorithm of identification of steady-state dependability indicators of technical systems]. Dependability and quality control 1984; 5:3 10.

14. Shubinsky IB. Strukturnaya nadiozhnost informatsionnykh sistem [Structural dependability of information systems]. Metody analiza [Analysis methods]. Moscow: Dependability; 2016 [in Russian].

15. Polessky VP. Razviazyvania klatterov, korreliatsionnie neravenstva i granitsy kombunatornoy nadiozhnosti [Clutter untyings, correlation inequalities, and bounds for combinatorial reliability]. Problems of information transmission 1997; 33 (3): 50-70 [in Russian].

16. Nosov MV. Metod polnogo razlozhenia mostikovykh soedineniy v zadachakh analiza sviaznosti strukturnoslozhnykh dvukhpoliusnykh setey [Method of complete decomposition of bridge connections in connectivity analysis problems of structurally complex bipolar networks]. Dependability 2015; 4: 68-74.

17. Filin BP. Metody analiza strukturnoy nadiozhnosti setey sviazi [Methods of structural dependability analysis of communication networks]. Moscow: Radio i sviaz, 1988 [in Russian].

18. Filin BP. Metod posledovatelnogo starta v opredelenii prostykh secheniy [Method of successive start in identifying simple crossections]. TsIVTI; 1977 [in Russian].

19. Bogatyrev VA. K raschiotu nadiozhnosti setey sviazi po sovokepnosti putey [On dependability calculation of communication networks per all route]. Elektrosviaz 1981; (2): 42-44 [in Russian].

20. Filin BP. O printsipe dualnosti v zadachakh analiza strukturnoy nadiozhnosti slozhnykh sistem [On the duality principle in the structural dependability analysis of complex systems]. Avtomatika i telemekhanika 1989; 6: 158-172 [in Russian].

21. Ivanitskaya LG. O funktsiakh nadiozhnosti ustroistv relsovogo deistvia [On the dependability functions of rail devices]. In: Proceedings of science and technology conference of VZEIS teaching staff chaired by Varakin L.E., Doctor of Engineering, Professor. Moscow: VZEIS; 1967 . 1: 111-132 [in Russian].

22. Hansler E. A fast recursive to calculate the reliability of a communication network. IEEE Trans. Commun. 1972 ; 3: 637-642.

23. Bogatyrev VA. K raschiotu nadiozhnosti seti po sovokepnosti putey [On dependability calculation of network per all route]. Elektrosviaz 1981; 5: 42-44 [in Russian].

24. Riabinin IA, Cherkesov GN. Logiko-veroyatnostnye metody issledovania nadiozhnosti strukturno slozhnykh sistem [Logical and probabilistic methods of dependability study of structurally complex systems]. Moscow: Radio i sviaz; 1981.

25. Ushakov IA, Litvak EI. Verkhiaia i nizhniaia otsenki parametrov dvukhpoliusnoy seti [Lower and upper bound estimates of a two-pole net]. . Izv. AN SSSR, Tekhnicheskaya kibernetika; 1977.

26. Ushakov IA, Harrison R., editors. Handbook of Reliability Engineering. New York: John Wiley and Sons inc.; 1994.

27. Filin BP. O metode ekspress-otsenki i kefficiente potentsialnoy strukturnoy neuyazvimosti sviazey v slozhnykh sistemakh [On the method of express assessment of and coefficient of structural invulnerability of connections in complex systems]. Avtomatika i telemekhanika. 1994; 5: 158-182 [in Russian].

28. Netes VA, Filin BP. Consideration of Node Failures in Network-Reliability Calculation. IEEE Transactions on Reliability 1996; . 49 (1): 67-68.

29. Filin BP, Shaparev AV. Ob odnom podkhode k raschiotu veroyatnosti sokhranenia maksimalnogo potoka [On an approach to the calculation of the probability of maximum flow maintenance]. Avtomatika i telemekahinika 2001; 1: 102-117 [in Russian].

30. Busacker R, Saaty T. Finite graphs and networks. Moscow: Nauka; 1974.

31. Wentzel ES. Probability theory. Moscow: Nauka; 1964.

32. Burachenko VA, Kolesnikov AN, Korzhik VI, Fink LM. Obshchya teoria sviazy [General theory of communication]. Leningrad: SM Budyonny Military Academy of the Signal Corps; 1970 [in Russian].

33. Davydenko VP, Loskutov NG, Ivanov LT. Osnovy voennoy kibernetiki [Introduction to military cybernetics]. Leningrad: SM Budyonny Military Academy of the Signal Corps; 1971 [in Russian].