Distributed Spectrum-Based Fault Localization

Avraham Natan, Roni Stern, Meir KalechAAAI 2023 · DOI

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.

Local spectrum (a) and the resulting similarity counters (b) used to calculate component health in DSFLA-SINGLE.

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:

  1. 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.
  2. Ranking via Distributed Gradient Descent: To rank these diagnoses without sharing raw data, the system maximizes a Likelihood Function.
The iterative process of Distributed Gradient Descent, showing how health estimates (H) and gradients are updated across components.

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

BibTeX
@inproceedings{natan2023distributed,
  author = {Avraham Natan and Roni Stern and Meir Kalech},
  title = {{Distributed Spectrum-Based Fault Localization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i5.25798},
}
Figure