Evaluation of testing assignment for system level self‐ diagnosis Viktor Mashkov1[0000-0001-9817-3388], Jiri Fiser1[ 0000-0002-5404-1727 ], Volodymyr Lytvynenko2[ 0000-0002-1536-5542 ], Maria Voronenko2[0000-0002-5392-5125] 1University J.E. Purkyne, Usti nad Labem, Department of Informatics, Usti nad Labem, Czech Republic, viktor.mashkov@ujep.cz, jf@jf.cz 2Kherson National Technical University, Department of Informatics & Computing Tech- nology, Kherson, Ukraine immun56@gmail.com, mary_voronenko@i.ua Abstract: The research concerns a task of comparing and assessing test- ing graphs in context of system level self-diagnosis. System level self- diagnosis aims at diagnosing systems composed of units, with the require- ment that they are able to test each other by exchanging information through available links. A set of tests performed in a system can be repre- sented as a testing graph. The obtained testing graph can be assessed based on the quality of diagnosis that it allows to achieve. In the research, we suggest the method allowing different testing graphs to be assessed and compared. The method uses the characteristic numbers. We have shown how such numbers can be computed. Keywords: complex systems, self-diagnosis, probabilistic algorithm, deci- sion rule 1 Introduction Research in the area of system level self-diagnosis started in the late 60s of the last century. Since that time there has been done a great amount of research. Achieve- ments in theoretical research gave impulse to practical implementation and enabled a broadening of the application domains of system level self-diagnosis. Initially, system level self-diagnosis was applied in complex multiprocessor systems and then it gradu- ally spread to distributed systems, different types of networks, multi-agent systems [1, 2, 3, 4] etc. There are four main issues, which form the context of system level self- diagnosis [5]. The first issue is the system testing assignment that defines the possible set of tests among the system units. The second issue is the assumptions underlying the diagnosis algorithms. Particularly, these assumptions tackle the possible faulty sets and the test results. These assumptions have direct impact on achievable quality of diagnosis (i.e., correctness and completeness). The third issue is the organization of test performance. It concerns the tasks of test scheduling, test repetition, test performing (random or deterministic), etc. The fourth issue relates to the problem of determining the unit(s), which will perform a diagnosis algorithm and/or will provide environment with the information about system state. Usually, the first and second issues are considered together, and they can be viewed as theoretical ground of system level self-diagnosis. In the theory of system level self-diagnosis, three main problems were formulated. They are characterization, diagnosability and diagnosis problems [6]. The characterization problem (i.e., the problem of testing assignment) was the first one which was considered in context of system level self-diagnosis. The work of Pre- parata at al. [7] studied the requirements to the system testing assignment. In this research, the authors have introduced the diagnosability measure which, to a great extent, depends on the system testing assignment. Particularly, in this research, they proved that for correct diagnosis of at most t faulty units there must be satisfied the following two requirements: a system must have n units, where n  2t  1 ; each sys- tem unit must be tested by at least t distinct other units. When these requirements are not satisfied correct diagnosis is not guaranteed. Nevertheless, there is a probability (sometimes great enough) that in this case it is also possible to achieve correct diag- nosis. In this research, we suggest new diagnosability measure which allows compar- ing system testing assignments and evaluating the formed testing graphs obtained after performing a set of tests. 2 Formal problem statement System level self-diagnosis is based on the results of tests performed by system units. System units test each other either according to predefined schedule or randomly. One of the ways of how to express a testing assignment consists in presenting it as a testing graph. Testing graph is a basis for a model of test performance. This model can be used for simulation of tests execution and obtaining a syndrome. Syndrome is an input for a diagnosis algorithm (see Fig. 1). Fig.1. The role of task of evaluation of testing assignment Different testing assignments, T (i.e., testing graphs) allow obtaining different credibility of diagnosis result (i.e., probabilities of correct diagnosis result, PCT ). To 3 predict the credibility of possible diagnosis results it is needed to evaluate the avail- able testing graph. It can be expressed as T  PCT . The problem of computing a credibility of diagnosis results consists in determining the function f, where Pcr  f T  . Characteristic numbers Ck can be used for computing f . 3 Literature review System level self-diagnosis (SLSD) was introduced by Preparata at al. [7] and has been deeply investigated in literature. There are four main issues that form the context of SLSD [8]. The first issue is the testing assignment that defines the possible set of tests among the system units. The second issue is the assumptions underlying the diagnosis algorithms. The third issue is the organization of tests performance. The fourth issue relates to the problem of choosing the diagnostic nucleus. The first and second issues can be considered as theoretical ground of SLSD. In the theory of SLSD, three basic problems were formulated [6, 9]. These are characterization prob- lem, diagnosability problem and diagnosis problem. The problem of testing assign- ment (i.e., characterization problem) was the first task that was considered in context of SLSD. The work of Preparata at al. [7] determined the requirements to the testing assignment of a system. Diagnosis problem concerns the task of determining a fault set from an allowable family, for a given testing assignment, fault model, and syn- drome [8]. There have been developed many algorithms allowing to identify a fault set uniquely (when some assumptions are made about the faulty units). The main task while developing these algorithms is to reduce their complexity. Among the most efficient algorithms there could be named algorithm proposed by Dahbura and Mas- son [10] which has O  N 2.5  time complexity and O  t 3  E  algorithm suggested by Sullivan [11]. Both algorithms were developed for t-diagnosable systems under the symmetric invalidation model and when permanent fault are allowable only. There are many special classes of t-diagnosable systems that support more efficient diagno- sis techniques than above mentioned ones, and this is reason to believe that an O  E  diagnosis solution exists for all t-diagnosable systems. Preparata et al. defined the D .t structure in which unit ui tests uj if and only if j  i   m  mod n  , where m  1, 2 , , t . Meyer and Masson [12] gave O  nt  ) solution to the case of   1 . In real complex systems, units are not necessarily homogeneous and can operate under different conditions. Therefore, units can have different levels of their reliabil- ity. This fact can be accounted for by assigning probabilities to the unit states. Prob- abilistic approach to system level self-diagnosis doesn’t deal with such problems as t -diagnosability and testing assignment. Among the first who investigated the prob- abilistic algorithms were H. Fujiwara and K. Kinoshita [13]. Probabilistic algorithms are based on the computing of the posterior probabilities of system unit states, upon which the decision about the system state is made. 4 Testing graph Tests in a system can be performed: - either in accordance with a preset schedule (i.e., defined a priori) - or in an adapted manner when, at the beginning, the tests are performed in accor- dance with defined a priori testing assignment. Once a unit is diagnosed as fault free, the tests it performs are considered reliable, and therefore, any other units should only be tested ones by this fault-free unit to cor- rectly determine its status. Thus, the testing assignment is adapted such that units diagnosed as fault-free perform all the testing in the system [14]: - or entirely randomly (i.e., from the beginning to the end of testing); - or adaptively randomly. At the beginning, all units are engaged in tests performing. Tests are performed randomly. Once a test reset takes the value of 1, the units participated in this test (so- called suspected pair) should only be tested by other system units (i.e., should not perform tests on other units). The choice of each pair of units for testing is performed randomly. Testing graph is a convenient form for presenting the tests performed in a system. Testing graph is a directed graph G  V , E  . Each vertex vi  V of G repre- sents unit ui and edge eij  E represents the test which is performed by unit ui on unit u j . Having obtained the testing graph, we can investigate the diagnosis properties which this graph possesses. Based on these diagnosis properties, it is possible to com- pare different testing graphs and find the best one from a certain criteria. It is easy to show that diagnosis result depends on number of faulty units. Let t be the total number of faulty units that are allowable in the system. For some values of t , it is always possible to construct the testing graph, which will ensure the correct and full diagnosis whichever syndrome is obtained. Syndrome is a set of test results. Test result is represented by binary variable rij , such that rij  1 if unit u j has not passed the test, and rij  0 otherwise. Correct diagnosis means that the detected faulty units are indeed faulty units. Full diagnosis means that every faulty unit is identified. For the testing graphs that ensure unique diagnosis [5] of at most t faulty units (so called t-diagnosability) the following conditions should be satisfied [7]: each vertex of the graph should have at least t incoming edges and there should not be multiple edg- es. For example, a testing graph may satisfy the requirements for t-diagnosability for t  1 and for t  2 , but fails to be t-diagnosable for t  3 . The maximum value of t for which a testing graph is t-diagnosable is denoted as tmax . Many t-diagnosable testing graphs (for t  tmax ) can exist. Thus, the task arises to determine those testing graphs which have the least number of edges for providing t-diagnosability. 5 Definition: Testing graph is t-optimal if it contains minimal number of edges and at the same time it ensures t-diagnosability. For the value t  tmax , t-optimal testing graph could be simply named as optimal. The number of edges of t-optimal testing graph can be easily computed as follows: l  tN (1) Thus, the number of edges of optimal testing graph is equal to:  N  1 (2) l  tmax N    N  2  Whichever testing graph that contains more than l edges is considered as redun- dant testing graph. It is also possible for the given value t to construct instances of testing graphs which provide certain diagnosis properties, e.g., capability to detect certain number of faulty units. For example, testing graph (see Fig. 1.a) is t-optimal for t  1 since it provides unique diagnosis of any faulty unit, and it has minimal total number of edges which is needed for such diagnosis. Fig. 2. Optimal testing graphs Testing graph in Fig. 1.b has t  2 and provides unique diagnosis of any two faulty units. Moreover, this graph is optimal since t  tmax . All testing graphs depicted in Fig. 2 provide unique diagnosis of the same number of faulty units (particularly, t  1 ) but have different total number of edges. Fig. 3. Examples of the testing graphs with t  1 5 Assessment of testing graphs The method suggested by Preparata et al. [7] for assessing testing graphs does not allow comparing the testing graphs and determining more precisely their diagnosis properties. Only parameter t and its maximum value are taken into account. Besides parameter t, there also exist further criteria for evaluating diagnosis properties of test- ing graphs, which make it possible to assess and compare the testing graphs. For example, to each testing graph there could be assigned the value of probability, which will reflex the fault detection property of testing graph [15, 16, 17]. It can be a probability that a syndrome (obtained after performing all tests, which are depicted in testing graph) is sufficient to detect all possible faulty units, PFD. It is only assumed that a fault-free unit is always able to detect a faulty unit (i.e., test covering is 100% ). This probability can be also interpreted as probability that a system is fault-free when obtained syndrome contains only zero test results. The probability PFD can be calculated as a sum of probabilities of the events when a fault-free units test all the other units. In the testing graph, it means that vertices which correspond to the fault-free units have edges directed to all remaining vertices. The computation of these probabilities can be explained with help of a simple ex- ample. Let the testing graph be the one as shown in Figure 3. Fig. 4. Exemplary testing graph For this testing graph there is seven   23  1 possible combinations of faulty- free units. The combination without faulty-free unit occurring with probability PU3 , where PU is probability of unit faulty state (it is assumed that all system units have the same probability), is irrelevant because empty set of fault-free units cannot test the other system units. More useful are three situations with one fault-free unit. In Fig. 4, this faulty-free unit is depicted by white vertex: Fig. 5. Exemplary situations with one faulty free unit 7 Each of these situations occurs with probability 1  PU  PU2 , but only one of them corresponds the condition that fault-free units test all the other system units. Two other situations do not allow to perform correct diagnosis of system units. The probability of all satisfactory situations with one fault-free unit is: P  A1   1  PU  PU2 1 (3) The probability of each situation with two faulty-free units is 1  PU  PU . There 2 are three such situations (see Fig. 5): Fig. 6. Situations with two fault-free units In the first situation, fault-free units u1 and u2 test the remaining unit (i.e., unit u3 ). Therefore its probability 1  PU  PU should be considered as one of the sum- 2 mands for computing probability PFD . In a similar way, the probability of the second situations (units u1 , u3 test unit u2 ) should be taken into account. The third situation (units u2 , u3 are fault-free) does not guarantee correct diagnosis of the remaining units (and, therefore, it is not a summand for computing probability PFD ). The probability of all satisfactory situations with two faulty free units is: P  A2   1  PU  PU  2 2 (4) Now, there is only one situation left. Particularly, the situation when all units are faulty-free. This case also leads to correct diagnosis. The probability of this situations is 1  PU  3 and it is always included in computing probability PFD regardless of testing assignment: P  A2   1  PU  2 (5) The total probability PFD can be generally expressed by the following sum: N N PFD   P  Ak    1  Pu  PUN  k Ck k k 1 k 1 (6) where Ck is the number of options to choice the subgraph with k vertices from which all the remaining vertices are achievable ( CN is always 1). For the considered testing graph C1  1 (only one subgraph is satisfactory for cor- rect diagnosis) and C1  2 (two subgraphs are satisfactory). Therefore, the total prob- ability is: PFD  1  PU  PU2 1  1  PU  P  2  1  PU  2 2 (7) For given PU  0.1 , we receive PFD  0.9 . Let’s make some changes in this testing graph. Particularly, edges from u3 to u2 and u1 are added, which makes testing graph 1-diagnosable (see Fig. 6). Fig. 7. Exemplary testing graph with t=1 For this graph, C1  1 (both units u1 and u3 test all remaining units) and C2  3 (all sets with two units test remaining unit). Therefore, for PU  0.1 we receive prob- ability PFD  0.9  0.12  0.9 2  0.1  3  0.93  0.99 . The graph in Figure 7 has six edges (every unit tests all remaining units). Fig. 8. Testing graph with six edges In this graph, number C1 is increased up to 3 (from each vertex of the testing graph now it is possible to directly reach all the remaining vertices of the graph). Clearly, number C2 is also equal to 3. The value of PFD is 0.9 ∙ 0.12 ∙ 3 + 0.92 ∙ 0.1 ∙ 3 + 0.93 = 0.999. This graph has the same value t (particularly t  1 ) and provides the same 1- diagnosability. However, from the point of probability PFD, it is evident that the graph in Figure 6 has better diagnosis properties  PFD  0.999  than the graph in Figure 5  PFD  0.99  . For comparing the probabilities PFD , we need to have the numbers Ck , k  1, 2 , , n to be computed in advance. These numbers is called as characteristic numbers. Definition: Characteristic numbers Ck , k  1, 2 , , n are the numbers of choices of k vertices (resp. sub-graphs) from the testing graph so that all the remaining verti- ces of the graph are directly reachable. 9 For more complex graphs the characteristic numbers can be computed from the modified adjacency matrix of the testing graph. Adjacency matrix of a testing graph M   aij  has the following entries: 1 if unit ui tests unit u j (8) aij    0 otherwise Modified adjacency matrix is derived from the adjacency matrix by way of setting the values of 1 alongside the main diagonal. An algorithm for computing the charac- teristics numbers for particular testing graph have to account all the combinations of choices a unit(s), from which all the remaining ones are directly reachable, according to the following expression:  n  (9)  Ck    ac1 j  ac2 j    ack j  cC  k ,n   j 1   where Ck , C  k , n  is set of all k-combination i.e. all subsets of set 1, 2 , , n with k distinct element. 6 Computation of characteristic numbers The effectiveness of calculation of probability PFD for a testing assignment strongly depends on implementation of computation of characteristic number Ck for this test- ing assignment. Modern programming languages make possible straightforward computation of equation 3.2. For example in Julia programming language [18], the program is almost identical to its mathematical form (where parameter a is a modified adjacency ma- trix). function C(a::Matrix{Int}, k::Int) n = size(a, 1) # size in the first = second dimension return sum(prod(reduce(|, a[c,j]) for j = 1:n) for c in combinations(1:n, k)) end The outer summation iterates over sequences of every k -combinations of set 1, 2 , ,n (set is generated by range 1:n) produced by function combinations. The individual combination (denoted as c) is vector of integers. The computation of inner   logical summation ac1 j  ac2 j    ack j of selected items in columns is provided by discontinuous indexing (index is vector of integers) and by reduction (folding) using bitwise or operation. This initial and naïve implementation is depicted in Figure 9 (example of compu- tation of characteristic number C2 for system with tree units). Fig. 9. Straightforward computation of character number This implementation is compact but it has some shortcomings such as: ─ effective iterator over all k-combination is not available in most programming lan- guages (e.g. Matlab or Java); ─ it does not use any form of parallelism (including bit-wise parallelism which is supported by all processors); ─ the computation does not utilize already calculated values (outputs). The first two shortcomings can be eliminated by iteration over k-combinations which are represented by bit patterns. These patterns are formed by string of bits con- taining k 1's and n-k 0's. Sequences of all k-combinations are special cases of combi- natorial Gray codes [19] (generalization of commonly used and well-known Gray code) and they are realizable by elementary bitwise operations at processor level (e.g. bit complement, bitwise OR, AND and shifts). In our implementation we use simple generator [20] which utilizes only basic bit- wise operations as well as operation of counting trailing zeros. This operation is often directly and efficiently supported by current CPUs (for example, trailing_zeros func- tion is directly translated to BSF instruction in x86-64 platform [21] by Julia pro- gramming language). The generator of k-combinations Gray codes in Julia has a form of iterator func- tion. For pattern v it returns pair (v,w) where w is next patterns. function Base.next(c:: Combinations {Int}, v:: Int) t = v | (v - 1) 11 w = (t + 1) | (((~t & -~t) - 1) >> ( trailing_zeros (v) + 1)) return (v,w) end At every step of iteration over bit patterns, only relatively simple operations are performed. The parameter pa is a modified adjacency matrix packed as array of inte- ger values each of which corresponds to one column of the original matrix. For exam- ple sample matrix from Figure 5 is represented as array [6, 8, 5] i.e. [100, 110, 011] in binary notation. Parameter gcode is again bit pattern (integer) representing a selection of modules of diagnostic graph (the so-called subgraph). function cover_test (pa:: Vector {Int64}, gcode :: Int64) for column in pa #iteration over packed column if column & gcode == 0 return false end end return true #OK subgraph covers all remaining vertices end Bitwise AND operator in this code replaces slow discontinuous indexing of the original code. The reduction by logical OR is substituted by one instruction of integer equality (operator ==). Product is performed by for each-loop which realizes short circuit evaluation (the first occurrence of zero exits loop). This new implementation is illustrated on Figure 10 (only one of summation is de- picted). Fig. 10. Fragment of suggested computation of characteristic number C2 Further acceleration of algorithm is possible by utilization of trivial assertion: if vertices of subgraph of a testing graph cover all the remaining vertices of this testing graph then the vertices of any graph which include this subgraph (the so-called super- graph) also cover the remaining vertices. The improved algorithm computes characteristic numbers all together concur- rently i.e. it returns vector of characteristic number  c1 , c2 , , cn  . The first tested subgraph in this algorithm contains one unit and it is represented by bit pattern with 1 on the leftmost position (e.g. bit pattern 1000 for system with four unit). If this subgraph covers the remaining vertices (i.e. function cover_test re- turns value true) then c1 is incremented and its supergraphs containing 2 to n vertices (e.g. 1100, 1101, 1111) are taken in account in increment of values c2 , , cn (number of subgraphs is determined by appropriate binomial coefficient). These supergraphs need not be consequently iterated and tested in the following phases of computation. Otherwise, the next subgraphs with two units represented by 1's on the leftmost posi- tion is tested (e.g. pattern 1100). When all supergraphs of the first one-vertex subgraph are considered (i.e. directly tested or automatically included in bulk) the next one-vertex subgraph is tested (eg. 0100). This implementation requires additional memory for generation of sequences of bit patterns but generated combinatorial Gray codes take into consideration partial ordering of combination by supergraph relation i.e. codes are hierarchical in some sense. Optionally the precomputed table of binomial coefficients can be used. The as- ymptotic space complexity of algorithm is O(k) which is acceptable because k is rela- tively small (time complexity is still exponential). The code is more complex but it is still usable in small devices. function Cvec(a:: Matrix {Int}, sorting :: Bool) pa = pack(a) # packing of matrix to vector of bit patterns (i.e integer values) if sorting # sort by 1’s count (i.e. by outdegree of given vertex), see next paragraph sort!(pa , by= count_ones) end n = length (pa) # number of vertices binom = binomials(n) # populating of matrix of binomials coefficients p = zeros0(Int , n + 2) #vector of indexes of the leftmost positions of ones (indexed from zero) gc = zeros0(Int64 , n + 1) # vector of subgraph bit patterns (zero based indexing) c = zeros(Int , n) # vector of characteristic numbers (one based indexing) p[0] = n + 1 # p[0] is only formal stop position k = 1 # number of vertices in subgraph (= number of 1's in patterns) while k > 0 p[k] += 1 # shift leftmost 1-bit position to the right if p[k] == p[k -1] # if it is not possible p[k] = 0 k -= 1 # return to iteration over (k-1)-vertex subgraph else gc[k] = gc[k -1] | (1 << (p[k] - 1)) # bit pattern of k-vertex subgraph if cover_test (pa , gc[k]) c[k] += 1 # it counts this subgraph for j=1:p[k]-1 # and all its super-graphs c[k+j] += binom[p[k] - 1, j] end 13 else k += 1 # or test next subgraph end end end return c end According to the above mentioned assertion the algorithm is rather asymmetrical. The subgraphs which are represented by 1-bits positioned on the left side of a bit pat- tern take advantage of the assertion on greater extent (the generator fills bit strings from the leftmost bit). The (one vertex) subgraph represented by the least significant bit does not utilize assertion anymore. The partial improvement consists of the sorting of vertices by out-degree values because the vertex with greater out-degree is better candidate for participation in sub- graph covering all remaining vertices (i.e. should be placed on more significant bit of packed column). The efficiency of algorithms is evaluated by the time required for application of algorithms on random diagnostics graphs (see Figure 11). The random testing graphs contain approximately n / 2 edges (close to density of edges in optimal testing graphs). Fig. 11. Time of computation of characteristic number for different number of units All algorithms have exponential time complexity but their application areas are different. The straightforward implementation is usable only for relatively small num- ber of units (<17 for subseconds execution times on PC range CPU). The algorithm using bit-level parallelism is usable to greater number of units (approximately 25). The algorithm with hierarchical bit patterns makes possible computation with sub- seconds delays for system with 34 unit. The pre-sorting of vertices leads to some speed-up but it is in most real cases practically negligible. The hierarchical algorithm also depends on specific structures of testing graph (de- tails are subject to further research). Figure 12 shows effectiveness of algorithms for almost tmax -optimal testing graphs i.e. or graphs with a large number of tests. For t-optimal testing graphs  t  tmax  the situation may be very different. Plot in Figure depicts the time of computation for simple t-optimal graphs for system with 25 units ( tmax is 12) and for both algorithms based on bit patterns (straightforward implementation is useless for system with 25 units). Fig. 12. Computational time for t-optimal testing graphs For testing graphs with a small number of edges (tests) the simple (non- hierarchical) algorithm is better compared to tmax optimal testing graphs because iteration is simpler and short circuit evaluation of product operation is performed almost immediately (only two direct instruction are executed per subgraph). On other hand the hierarchical approach is more complicated (tens of direct instruction per subgraph) and it cannot utilize acceleration of bulk increments (small subgraphs do not cover its remaining vertices). But this acceleration outperform short-circuit for 3- optimal graph and for nearly tmax –optimal graphs the difference is in order of tens. The computation of probability PFD using equation 3.1 requires floating point unit because it uses multiplication of rational numbers (computation of characteristic number is limited to integer arithmetic with simple operation without multiplication). Fortunately, the relative comparison of probabilities (i.e. evaluation of testing assign- ment) does not depend on probability of a unit faulty state PU (if it is assumed that all system units have the same probability PU ). Therefore we can choose any probabil- ity PU from interval [0,1]. For probability 0.5 (although it is unrealistic) the equation 3.1 is simplified to form: k Ck (10) i 1 2 N 15 Comparison of probabilities for concrete system requires only (integer) summation of characteristic number (value 2 N is constant). When we need to compare testing graphs with differed number of units the computation can be performed by way of bit shift operation on fixed point representation of probability values. 7 Conclusions Tests performed in a system can be represented as a testing graph. Analysis of the obtained testing graph aims at checking whether all system units have been tested or whether the formed testing graph belongs to predefined subset of testing graphs. It depends on the value of required credibility of system self-diagnosis. Testing graph can be also used as input data for diagnosis algorithm. For different testing graphs the obtained diagnosis results will have different credibility. In the research, we have considered the probability that all system units can be cor- rectly diagnosed after performing all tests. This probability can be used as a diag- nosability measure which will allow comparing system testing assignments and evaluating obtained testing graphs. This probability is computed by using characteris- tic numbers. In the research, we suggested relatively effective method for computing characteristic numbers and developed the algorithm (based on bitwise operations with integer values). Efficiency of the developed algorithm was also evaluated for different scenarios of testing assignments. References 1. Mashkov, V.: Task allocation among agents of restricted alliance. Proc. of IASTED ISC’2005 conference, Cambridge, MA, USA, 2005, pp.13-18 (2005) 2. Mashkov, V.: Restricted Alliance and Coalitions Formation. Proc. of IEEE/WIC/ACM In- ternational Conference on Intelligent Agent Technology/ Beijing, China, 2004, pp.329-332 (2004) 3. Qin, L., He, X., Zhou, D.: A survey of fault diagnosis for swarm systems. Systems Science and Control Engineering. Vol. 2, 2014, pp. 13-23 (2014) 4. Mahapatro, A., Khilar, P.: Fault diagnosis in wireless sensor networks: a survey IEEE Commun Surv Tutorials. Vol. 15, 2013, pp. 2000-2026 (2013) 5. Mashkov, V., Mashkov, O.: Interpretation of diagnosis problem of system level self- diagnosis. Int. Journal „Mathematical Modeling and Computing“, Vol.2, No.1, 2015, pp.71-76 (2015) 6. Barborak, M., Malek, M., Dahbura, A.: The consensus problem in fault-tolerant comput- ing. ACM Computing Surveys. Vol.25, No.2, 1663, pp.171-220 (1663) 7. Preparata, T., Metze, G., Chien, R.: On the connection assignment problem of diagnosable system. IEEE Transactions on Electronic Computers. Vol.EC-16, No.12, 1967. pp. 848- 854(1967) 8. Mashkov, V.: Selected problems of system level self-diagnosis. Lviv: Ukrainian Academic Press, 2011, 184 pages (2011) 9. Somani, A.: System Level Diagnosis: A Review. (1997) [online]. Available from www: . 10. Dahbura, A., Masson, G. :An O(n2.5) fault identification algorithm for diagnosable sys- tems. IEEE Trans. Comput., Vol.C-33, 1984. pp.486-492 (1984) 11. Sullivan, G.: An O(t3 + |E| ) fault identification algorithm for diagnosable systems. IEEE Trans. Comput., Vol.C-37, 1988. pp.388-397 (1988) 12. Meyer, G., Masson, G.: An efficient fault diagnosis algorithm for symmetric multiple processor architectures. IEEE Trans. Comput., Vol.C-27, 1978. pp.1059-1063 (1978) 13. Fujiwara, H., Kinoshita, K.: Some existence theorems for probabilistically diagnosable systems. IEEE Trans. on Comp. Vol.C-27, No.4, 1981. pp.297-303 (1981) 14. Bianchini, R., Buskens R.: An adaptive distributed system-level diagnosis algorithm and its implementation. In the 21st International IEEE Simposium on Fault-tolerant Comput- ing. New York (USA), 1991, pp.222-229 (1991) 15. Mashkov, V., Barabash, O.: Self-checking and self-diagnosis of module systems on the principle of walking diagnostic kernel. Engineering Simulation, Vol.15, 1998, pp. 43-51 (1998) 16. Jarrah, H., Sarkar, N., Gutierrez, J.: Conparison-based system-level fault diagnosis proto- cols for obile ad-hoc networks: A survey. Journal of Network and Computer Applications. Vol. 60, 2016, pp. 68-81 (2016) 17. Weber, A., Kutzke, A., Chessa, S.: Energy-aware test connection assignment for the self- diagnosis. J Braz Comput Soc. Vol. 18, 2012, pp. 19-27 (2012) 18. Bezanson, J., Karpinski, S., Shah, V., Edelman, A.: Julia: A Fast Dynamic Language for Technical Computing. 2012, ARXIV (2012) 19. Savage, C.: A Survey of Combinatorial Gray Codes. SIAM Review [online]. 1997, 39(4), 605-629 (1997) [cit. 2016-04-16]. 20. Anderson, S.: Bit Twiddling Hacks [online] (2005) htps://graphics.stanford.edu/~seander/bithacks.html 21. AMD64 Architecture Programmer's Manual Volume 3: General Purpose and System In- structions3 . AMD. 2011. pp. 204–205, (2011)