# IFDA: Intermittent Fault Diagnosis Algorithm for Augmented Cubes Under the PMC Model
## 2 Preliminaries  
In the field of system-level fault diagnosis, multiprocessor systems are typically represented as an undirected graph \(G=(V_{G},E_{G})\), where \(V_{G}\) is a node set and \(E_{G}\) is an edge set. The node represents the processor, and the edge represents the communication link. \(u,v\in V_{G}\), \((u,v)\in E_{G}\) represents the adjacent nodes \(u\) and \(v\). The set of neighbor nodes for node \(u\) is represented as \(N(u)\), \(N(u)=\{u\in V_{G},(u,v)\in E_{G}\}\). A graph \(S=\{V_{S},E_{S}\}\) is a subgraph of \(G=\{V_{G},E_{G}\}\), where \(V_{S}\subseteq V_{G}\) and \(E_{S}\subseteq E_{G}\). The neighbor nodes of node \(x\) in a subgraph \(S\subseteq G\), denoted by \(N_{S}(x)\), is the set of all nodes in \(S\) that are adjacent to node \(x\). \(deg_{S}(x)\) represents the degree of node \(x\), and is the number of all nodes in \(S\) that are adjacent to node \(x\), i.e., \(|N_{S}(x)|=deg_{S}(x)\). Given a set of nodes \(U\subseteq V_{S}\), the neighboring nodes of \(U\) in \(S\subseteq G\) is denoted by \(N_{S}(U)=(\cup_{x\in U}N_{S}(x))-U\). The minimum degree in graph \(S\) are denoted as \(\delta(S)\), and the maximum degree is denoted as \(\Delta(S)\), \(\delta(S)=\min\{deg_{S}(x)\mid x\in V_{S}\}\), \(\Delta(S)=\max\{deg_{S}(x)\mid x\in V_{S}\}\). If \(\delta(S)=\Delta(S)=m\), then graph \(S\) is called an \(m\)-regular graph. Furthermore, the connectivity of graph \(G\) refers to the minimum number of nodes removed from \(G\) that causes \(G\) to disconnect, or causes only one node to remain, denoted by \(\kappa\). Let \(G=(V,E)\) and \(G^{\prime}=(V^{\prime},E^{\prime})\), if there is a bijective function \(g\): \(V\to V^{\prime}\) such that \(e=(u,v)\in E\) if and only if \(e^{\prime}=(g(u),g(v))\in E^{\prime}\), we say that \(G\) is isomorphic to \(G^{\prime}\), and is typically denoted by \(G\cong G^{\prime}\). In graph theory, a Hamiltonian cycle within a graph \(G\) is defined as a cycle (or path) that traverses each vertex of \(G\) exactly once. A simple graph containing a Hamiltonian cycle is termed a Hamiltonian graph, and numerous well-known network structures exhibit this property. A subpath within a graph is characterized as a sequence of distinct vertices, denoted as \(\langle v_{0},v_{1},\ldots,v_{n-1},v_{n}\rangle\) where \(n\geq 1\), with the condition that for each \(i=0,\ldots,n-1\), the vertices \(v_{i}\) and \(v_{i+1}\) are adjacent. In this sequence, the vertex \(v_{0}\) is referred to as the head, \(v_{n}\) as the tail, \(v_{1}\) as the tail-first vertex, and \(v_{n-1}\) as the tail-lastvertex. The length of a sequence \(P_{i}\) is defined as the number of vertices contained within the sequence and is represented by \(|P_{i}|\). In a multiprocessor system \(G=\{V_{G},E_{G}\}\), under the PMC model. If node \(u\) is connected to node \(v\), \(u,v\in V_{G}\), then node \(u\) is able to test whether node \(v\) is faulty or faultless. The test results can be represented by 0 or 1; a test result of 0 indicates that node \(u\) has tested node \(u\) as fault-free, and a test result of 1 indicates that node \(u\) has tested node \(u\) as faulty. If test node \(u\) is a normal node, the test results are reliable; if test node \(u\) is a faulty node, the test results are unreliable. In augmented cubes, the system is modeled by an undirected graph \(G(V,E)\). For a node \(u\) in graph \(G\), assume \(v\) is an adjacent node in \(N(u)\), and the undirected link is represented by \((u,v)\). Based on the PMC model, the adjacent nodes will evaluate each other. We use \((R_{1},R_{2})\) to represent the diagnosis results, where \(R_{1}\) is the result of \(u\to v\), and \(R_{2}\) is the result of \(v\to u\). Combined with intermittent fault characterization, four possible syndromes could be generated. If \((u,v)=(0,0)\), called 0-path, \(u\) and \(v\) have the same correctness; otherwise, it is called 1-path, and at least one of the two nodes is in a fault state. The results are shown in Table 2.  
The term rounds are used to describe the iteration of the graph test.