Introduction
Spectrum-Based Fault Localization (SFL) is a cornerstone technique for identifying faulty components in complex systems. By analyzing the "spectrum"—the record of which components were active during successful versus failed system runs—SFL uses statistical coefficients to rank potential culprits. However, traditional SFL is inherently centralized, requiring all components to transmit their activity data to a single diagnoser. In modern distributed environments like cloud microservices or multi-agent networks, this centralized model introduces significant privacy risks, communication bottlenecks, and single points of failure.
This paper introduces Distributed SFL (DSFL), a framework where components collaborate to localize faults using only their local spectrum data. The proposed algorithms, DSFLA-SINGLE and DSFLA-MULTI, are mathematically guaranteed to produce the exact same diagnostic results as centralized methods while protecting component privacy and reducing overhead.
Methodology
DSFLA-SINGLE: Localizing Single Faults
In single-fault scenarios, each component $j$ maintains its own "similarity counters" ($n_{11}, n_{10}, n_{01}, n_{00}$), which track its involvement in failed ($e=1$) and successful ($e=0$) runs.
As shown in Figure 3, the local spectrum (a) maps component activity to system outcomes ($E$). In the distributed version, components send targeted requests to peers only for missing information regarding specific runs. This protocol prevents duplicate reporting and ensures that the final ranking of components is identical to a centralized calculation without ever aggregating the full global spectrum in one location.
DSFLA-MULTI: Addressing Multiple Faults
Multi-fault localization is significantly more complex, requiring the identification of combinations of faulty components. The authors address this through a two-stage process:
- Diagnosis Generation: Components iteratively compute Minimal Hitting Sets (MHS). A component identifies local diagnoses and passes them to the next agent in a sequence for refinement.
- Ranking via Distributed Gradient Descent: To rank these diagnoses without sharing raw data, the system maximizes a Likelihood Function.
Figure 5 illustrates this distributed optimization. Components share only current "health" estimates ($h_j$) and global likelihood values ($l$), rather than their internal activity patterns. This allows the system to converge on the most likely faulty candidates through a series of gradient updates.
Evaluation and Key Results
The researchers evaluated these algorithms using 54,000 experiments on synthetic networks modeled after Internet Delay Diagnosis. The networks consisted of 6 to 13 routers with 1 to 5 injected faults.
Accuracy and Privacy
The most significant finding is the Identical Output Guarantee: the distributed baseline algorithms achieved the same "Wasted Effort" and "Precision" scores as centralized diagnosers. Privacy was measured using the Revealed Hidden Information Fraction (RHIF). While the standard distributed baseline revealed some data, a variation called Multi-SMC (which only passes the single best diagnosis candidate) reduced the RHIF to a mere 0.0001, revealing virtually nothing about the components' total activity.
Efficiency
Communication overhead was also drastically reduced. The Multi-SMC variant required only 4.6 messages per agent, compared to 65.51 for the standard baseline. Furthermore, in multi-fault scenarios, the distributed approach was significantly faster, completing tasks in 0.39s versus 10.44s for the baseline.
Conclusion
Distributed Spectrum-Based Fault Localization proves that it is possible to achieve high-fidelity diagnostics without sacrificing privacy or system performance. By leveraging local spectrum data and distributed optimization techniques like gradient descent, DSFLA provides a robust, scalable alternative to centralized monitoring. Future work will focus on making these algorithms resilient to message loss and potential non-collaborative (Byzantine) components in the network.
Summary updated