# Structural Methodologies for Distributed Fault Detection and Isolation
## 4 Equation-Based Distributed Fault Detection and Isolation
### Computational Complexity  
The time complexity of Algorithm 5 is mostly governed by Algorithm 4 (Count-Matchings) that has exponential complexity \(O(|\mathcal{U}|\times|E_{N}|!)\), where \(|\mathcal{U}|\) is the number of required unknown variables in the subsystem and \(|E_{N}|\) is the number of equations in the neighboring subsystems. Algorithm 6 calls Algorithm 5 for every fault in the subsystem. Therefore, Algorithm 6 has \(O(|F_{i}|\times|\mathcal{U}|\times|E_{N}|!)\) time complexity for subsystem \(S_{i}\), where \(|F_{i}|\) is the number of faults in the subsystem. Note that in the case that no globally-accurate diagnoser can be derived using neighboring subsystems, the solution gradually expands to include all subsystems. Therefore, the time complexity of our proposed method in Algorithm 7 for subsystem \(i\) is \(O(|F_{i}|\times|\mathcal{U}|\times|E|!)\), where \(|E|\) is total number of equations in the system.  
In practice, Algorithm 4 finds the answer much faster. For example, consider Figure 6 where Algorithm 4 is searching for a set of equations to solve \(q_{1}\). As soon as the algorithm reaches an equation that does not have the required unknown variable, the algorithm discards that equation and, therefore, avoids enumerating the rest of the candidate equations in that branch. To achieve even faster solutions, we can sort the equations by the number of their unknown variables before the search. In this way, the algorithm starts with equations with fewer unknown variables and, therefore, has to expand fewer branches on average.  
The equation-based solution is exponential in terms of the number of equations in the system. The MSO-based solution is exponential in terms of the number of MSO sets in the system. The total number of MSO sets for fault detection and isolation grows exponentially as the number of measurements increase [29]. Consider Definition 1. The total number of redundancies introduced into the system model is equal to the number of measurements, \(|M|\). Theoretically, each MSO set can include anything from one to \(|M|\) measurements. Therefore, the total number of MSO sets, \(N_{MSO}\), is proportional to all possible combinations of the measurements:  
\[N_{MSO}\propto\sum_{i=1}^{|M|}\binom{|M|}{i}=2^{|M|} \tag{12}\]  
In general, there are many more MSO sets in a system than equations. For example, the running example in this paper has 20 equations, and the fault diagnosis toolbox generated 165 MSO sets for  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Subsystem** & **Augmented Equations** & **Augmented Measurements** \\ \hline \(S_{1}\) & \(e_{10}\) & \(y_{3}\) \\ \(S_{2}\) & \(e_{6},e_{12},e_{14},e_{15},e_{16}\) & \(y_{2},u_{2},y_{5}\) \\ \(S_{3}\) & \(e_{11},e_{17},e_{18},e_{19},e_{20}\) & \(y_{4},y_{6}\) \\ \(S_{4}\) & \(e_{16}\) & \(y_{5}\) \\ \hline \hline \end{tabular}
\end{table}
Table 2: Set of augmented constraints and measurements for each subsystem model.  
this system. Therefore, we expect the equation-based approach to solve the problem in a more efficient way, which is demonstrated next.