Structural Analysis of Ambiguity Emergence Scenarios in Self‑Testing of Fault‑Tolerant Multiprocessor Systems

Abstract

The relevance of the study is determined by the need to improve the reliability and efficiency of self-testing procedures for fault-tolerant multiprocessor systems. Existing approaches based on a minimal set of diagnostic connections may leave some processor states unresolved, requiring additional tests. The aim is to refine the structural description of ambiguity formation in systems whose diagnostic graph is a strongly connected directed circulant with two jumps. The objectives include deriving new restrictions on ?-chains and ?-subgraphs, determining conditions for the existence of such subgraphs with the minimum admissible number of incoming fault links, and establishing when several independent subgraphs can arise. Methods. Graph-theoretic analysis, modular relations for circulant parameters, structural decomposition of ambiguity regions, and analysis of admissible ?-chain configurations are used. The results establish a finite upper bound on ?-chain length for the considered unresolved-fault state. It is proved that a ?-subgraph with the minimum admissible number of incoming fault links can contain only one processor whose state remains unresolved. A necessary relation between circulant jumps allowing two independent ?-subgraphs of this type to coexist is also established. The scientific novelty lies in extending the structural theory of ambiguity formation for the considered number of faults and substantially narrowing the set of configurations requiring further analysis. The practical value of the results consists in their applicability in refining self-testing algorithms, excluding impossible ambiguity configurations, and reducing additional diagnostic checks required to resolve uncertain processor states.