## 6 A Fault Diagnosis Algorithm
### Formal Description of the t/k Diagnosis Algorithm under the MM* Model  
According to Lemma 8, we obtain important information that there exists a largest component with at least \(N-|F|-h\) with \(|F|\leq(h+1)(k-1)+n-1\). Meanwhile, \(BC_{n,k}\) is \([(h+1)(k-1)+n]/h\)-diagnosable under the MM* model. The algorithm can correctly diagnose all faulty nodes, provided that the upper bound on the number of faulty nodes are \((h+1)(k-1)+n\), which contains most \(h\) fault-free nodes that are misdiagnosed as faulty nodes. The algorithm t/h-Diag first repeatedly calls algorithm C-UC(u) choosing the largest connected component. When the case appears that \(|F|\leq(h+1)(k-1)+n\) and \(|U|>0\), UDiag(C,UC,U) is called. t/h-Diag will output C,UC,U. The C set is fault-free, UC are faulty and U is undetermined. Algorithm t/h-Diag is shown in Algorithm 1. ```
0: A syndrome \(\sigma\) on \(BC_{n,k}\) produced by a faulty node set \(F\subset V(BC_{n,k})\) with \(|F|\leq(h+1)(k-1)+n\), where \(n\geq 3\), \(k\geq 2\), \(n\geq k+1\) and \(1\leq h\leq n-1\). 0: C,UC,U. 1:\(U\leftarrow\phi\), \(C_{1}\leftarrow\phi\), \(R\gets V(BC_{n,k})\)
2:while\(R\
eq\phi\)do
3: choose a node \(u\) in R, call algorithm C-UC(u) and return C,UC
4:if\(|C|>|F|\) and \(|C|>|C_{1}|\)then
5:\(C_{1}\leftarrow\phi\), \(C_{1}\gets C_{1}\cup C\)
6:\(UC_{1}\leftarrow\phi\), \(UC_{1}\gets UC_{1}\cup UC\)
7:\(R\gets R-u\)
8:\(C\leftarrow\phi\), \(C\gets C\cup C_{1}\)
9:\(UC\leftarrow\phi\), \(UC\gets UC\cup UC_{1}\)
10: identify all nodes in C as fault-free
11: identify all nodes in UC as faulty
12:\(U\gets V(BC_{n,k})-C-UC\)
13:if\(|U|>h\)then
14: identify all nodes in U as fault-free
15:if\(|UC|=t-1\) and \(|U|>0\)then
16: call algorithm UDiag(C,UC,U) and return C,UC,U
17: return C,UC,U
```  
**Algorithm 1** t/h-Diag  
Algorithm C-UC(u) uses breadth-first search (BFS) to traverse from the selected node, using the Q.push() and Q.pop() operations. If u is fault-free, then the C set is all fault-free nodes and the UC set is all faulty nodes. If u is faulty, then the C set is full of faulty nodes and the UC set is full of fault-free nodes. Algorithm C-UC(u) is shown in Algorithm 2. For \(|F|=(h+1)(k-1)+n-1\), when \(|U|>0\), UDiag is called. Since \(|F|=(h+1)(k-1)+n-1\), U has at most one fault node. Select one node in the U set to test the other two nodes; if the symptom is 1, this indicates that one of the three nodes is a faulty node. At this point, the U set is a fault-free node, except for these three nodes. Select a node to test two of the three nodes, and if the symptom is 0, the two nodes being tested are fault-free. Then, the remaining node is the faulty node. With the exception of this fault node, all nodes in U are fault-free and all nodes are tested out. Algorithm UDiag(C,UC,U) is shown in Algorithm 3. ```
0: C,UC,U and a syndrome \(\sigma\) on \(BC_{n,k}\). 0: C,UC,U. 1: For any node \(u\in U\) such that \(\sigma(v,w)_{u}=1\), where \(\{v,w\}\in N_{U}(u)\). 2:if\(\sigma(v,w)_{x}=0\), where \(x\in(N_{U}(v)-\{u\})\cup(N_{U}(w)-\{u\})\)then
3:\(UC\gets UC\cup u\), \(U\gets U-u\)
4:if\(\sigma(u,w)_{x}=0\), where \(x\in(N_{U}(u)-\{v,w\})\cup(N_{U}(w)-\{u\})\)then
5:\(UC\gets UC\cup v\), \(U\gets U-v\)
6:if\(\sigma(u,v)_{x}=0\), where \(x\in(N_{U}(u)-\{v,w\})\cup(N_{U}(w)-\{u\})\)then
7:\(UC\gets UC\cup w\), \(U\gets U-w\)
8:\(C\leftarrow\cup U\), \(U\leftarrow\phi\)
9: return C,UC,U. ```  
**Algorithm 2** C-UC(u)  
**Input**: C,UC,U and a syndrome \(\sigma\) on \(BC_{n,k}\). **Output**: C,UC,U. ```
1: For any node \(u\in U\) such that \(\sigma(v,w)_{u}=1\), where \(\{v,w\}\in N_{U}(u)\). 2:if\(\sigma(v,w)_{x}=0\), where \(x\in(N_{U}(v)-\{u\})\cup(N_{U}(w)-\{u\})\)then
3:\(UC\gets UC\cup u\), \(U\gets U-u\)
4:if\(\sigma(u,w)_{x}=0\), where \(x\in(N_{U}(u)-\{v,w\})\cup(N_{U}(w)-\{u\})\)then
5:\(UC\gets UC\cup v\), \(U\gets U-v\)
6:if\(\sigma(u,v)_{x}=0\), where \(x\in(N_{U}(u)-\{v,w\})\cup(N_{U}(w)-\{u\})\)then
7:\(UC\gets UC\cup w\), \(U\gets U-w\)
8:\(C\leftarrow\cup U\), \(U\leftarrow\phi\)
9: return C,UC,U.