Source-linked AI summary
Survey on Models and Techniques for Root-Cause Analysis
Marc Solé, Victor Muntés-Mulero, Annie Ibrahim Rana, Giovani Estrada
TL;DR
Complex cloud and IoT systems raise the question of how RCA techniques can handle growing data, scalability, and real-time demands. This survey reviews IT-system RCA models and their generation and inference algorithms, focusing on performance. It finds a broad range of techniques with a trade-off between tractability and expressiveness.
Problem
The survey addresses limited understanding of how RCA techniques fit the scalability and real-time demands of IoT and similar environments, where vast data volumes must be managed.
Source: §I · p. 1Method
The survey reviews RCA models and their generation and inference algorithms, emphasizing performance and restricting its scope to techniques applicable to IT systems.
Source: §I · p. 1Results
The survey finds a wide spectrum of RCA techniques with the usual trade-off between tractability and expressiveness.
Source: §V · p. 12Takeaways & Limitations
RCA strategy selection should account for system and application requirements, while recognizing the trade-off between tractability and expressiveness.
Source: §I · p. 1, §V · p. 12The survey restricts its coverage to RCA techniques applicable to IT systems.
Source: §I · p. 1
Abstract
from arXiv · showhide
Automation and computer intelligence to support complex human decisions becomes essential to manage large and distributed systems in the Cloud and IoT era. Understanding the root cause of an observed symptom in a complex system has been a major problem for decades. As industry dives into the IoT world and the amount of data generated per year grows at an amazing speed, an important question is how to find appropriate mechanisms to determine root causes that can handle huge amounts of data or may provide valuable feedback in real-time. While many survey papers aim at summarizing the landscape of techniques for modelling system behavior and infering the root cause of a problem based in the resulting models, none of those focuses on analyzing how the different techniques in the literature fit growing requirements in terms of performance and scalability. In this survey, we provide a review of root-cause analysis, focusing on these particular aspects. We also provide guidance to choose the best root-cause analysis strategy depending on the requirements of a particular system and application.
I. INTRODUCTION
Cloud and IoT growth is making complex, distributed systems harder to manage, while traditional dashboards are insufficient for human oversight. The survey reviews IT-system RCA models and their generation and inference algorithms, emphasizing performance and scalability.
I. INTRODUCTION
- Complex, distributed IoT systems require RCA to synthesize system status and generate more accurate root-cause hypotheses for human decision-making.The paper says traditional dashboards will no longer suffice for controlling such systems.Source: §I · p. 1
- The survey identifies a gap in understanding how RCA techniques can meet the scalability and real-time demands of IoT and similar environments.Managing the vast data generated in these environments also needs support from IoT and Cloud platforms.Source: §I · p. 1
- The survey examines RCA models and their generation and inference algorithms, with particular attention to performance and a scope limited to techniques applicable to IT systems.It builds on earlier general surveys, including.Source: §I · p. 1
II. MAIN CONCEPTS AND TERMINOLOGY
Causality and explanation are central concepts in RCA, but neither has a settled formal definition. Explanation matters because it is often a desired RCA output, and multiple alternatives have been proposed.
II. MAIN CONCEPTS AND TERMINOLOGY
- Causality and explanation are central to RCA, yet their formal definitions remain unsettled despite centuries of discussion,.Source: §II · p. 2
- Explanation is often a desired RCA output, motivating the range of alternatives discussed for inference.Source: §II · p. 2
A. Terminology
The survey adopts terminology in which root causes are initiating faults, errors are system-state discrepancies, failures are externally observable errors, and symptoms are external manifestations.
A. Terminology
- An event is an exceptional condition in system operation; a fault, problem, or root cause can cause other events but is not itself caused by another event.Faults are classified by duration as permanent, intermittent, or transient.Source: A. Terminology · p. 2
- An error is a discrepancy between the system's condition and its theoretically correct condition, caused by one or more faults [2].Source: A. Terminology · p. 2
- A failure is an error observable from outside the system, while a symptom is an external manifestation of failure [2].Symptoms can include alarms indicating a failure without themselves being failures [2].Source: A. Terminology · p. 2
- Root-cause analysis infers the faults that generated observed symptoms, using a model of fault–symptom relationships when faults are not directly observable [2].Source: A. Terminology · p. 2
B. Classification of the RCA challenges
RCA strategy depends on the diagnosed system and analysis requirements, including available knowledge, desired output, timing, scale, and change over time.
B. Classification of the RCA challenges
- Analysis intent distinguishes finding root causes from producing an explanation, while analysis time ranges from real-time diagnosis to post-mortem diagnosis [2].Real-time approaches may precompute some or all inference, trading storage for online checking time [2].Source: B. Classification of the RCA challenges · p. 2
- Diagnosis complexity depends on system size, data volume, and inference length, including separate training and observation data sizes for learned models [2].The survey restricts its discussion to systems with inference length of at least one, beyond anomaly detection alone [2].Source: B. Classification of the RCA challenges · p. 2
- Effect-propagation time can determine the window of relevant observations and thus affect observation-data size [2].The survey notes that some settings treat propagation as immediate, while others do not [2].Source: B. Classification of the RCA challenges · p. 2
- For slowly changing systems, investing in an accurate expert-built manual model may pay off because the model is expected to need only minor changes [2].Source: B. Classification of the RCA challenges · p. 2
- RCA problems differ in available domain knowledge and access to the diagnosed system, which ranges from black-box to white-box information [2].These are separate dimensions: system access does not imply knowledge of the system's domain [2].Source: B. Classification of the RCA challenges · p. 3
C. RCA workflow
RCA follows a model-construction and inference workflow, with model updates or reconstruction considered when system knowledge changes.
C. RCA workflow
- RCA models are constructed from domain knowledge, system knowledge, and observations, although an approach need not use all three.The resulting model is populated with system observations for inference.Source: C. RCA workflow · p. 3
- Inference can return root causes, an explanation of the observations, or both, depending on the algorithm and model.Source: C. RCA workflow · p. 3
- System-knowledge changes such as adding or removing components may permit incremental updates, while other models require reconstruction.Domain-knowledge changes are considered less frequent and are not explicit in the workflow because they often entail reconstruction.Source: C. RCA workflow · p. 3
III. GENERATION OF RCA MODELS
The section surveys RCA models and the techniques used to learn or construct them, emphasizing that model choice affects inference performance.
III. GENERATION OF RCA MODELS
- The type of RCA model heavily affects inference-process performance.Source: §III · p. 3
- The survey describes many RCA models available in the literature.Source: §III · p. 3
- The section also covers techniques for learning or constructing those models.Source: §III · p. 3
A. Models for RCA
RCA models span deterministic and probabilistic approaches, with model structure and generation choices affecting how diagnosis is performed. Their categories overlap, and the survey’s model table is selective rather than exhaustive.
A. Models for RCA
- RCA models include techniques from AI, and their implementations and Bayesian Network subtypes can differ in learning and inference complexity.Decision trees and neural nets are distinct classifier implementations, and Bayesian Networks have a hierarchy of subtypes.Source: A. Models for RCA · p. 3
- Deterministic models represent known facts and inferences without uncertainty, whereas probabilistic models can handle uncertainty.Source: A. Models for RCA · p. 3
- The model table presents selected well-known RCA models and example diagnostic references, but is not exhaustive of usable classifiers.Any classifier may be used for single-fault diagnosis when sufficient training data are available.Source: A. Models for RCA · p. 3, Table I · p. 4
- Classifiers, especially advanced ones such as neural nets, may return only a predicted cause, provide difficult-to-obtain explanations, and complicate multi-fault diagnosis.They may also be difficult to combine with domain knowledge; multi-fault diagnosis requires a selection strategy or a multi-label classifier.Source: A. Models for RCA · p. 4
- Model categories overlap: process models consider observation order, while some process models are Bayesian approaches such as Dynamic Bayesian Networks and Hidden Markov Models.Codebooks can also be viewed as a particular implementation of propositional logic.Source: A. Models for RCA · p. 4
- Models can sometimes be converted into other forms, and compiling Bayesian Networks into Arithmetic Circuits can make diagnosis faster after an expensive compilation step.The passage also describes conversions among rules, classifiers, Bayesian Networks, and other model forms.Source: A. Models for RCA · p. 5
- Manual model generation tends to be accurate but slow, making it potentially impractical for rapidly evolving systems.Source: A. Models for RCA · p. 5
- Assisted generation assembles submodels using domain knowledge and system information, while automated generation builds the model from data when domain knowledge is unavailable or impractical to obtain.Source: A. Models for RCA · p. 5
B. Learning models for RCA
RCA model learning ranges from data-driven methods to fast rule and process-model learners, with costs and availability varying by model and system conditions. High evolution rates favor incremental updates or rapid relearning, while stream-oriented trees address continuously arriving data.
B. Learning models for RCA
- Some model families lack specific learning algorithms in the surveyed literature, while Bipartite BN learning is described only for a constrained subclass with cost exponential in k.The cited Bipartite BN approach is linear in the number of causes multiplied by the number of symptoms; conversion from another learned model is also noted as an option for some model types.Source: B. Learning models for RCA · p. 5
- Rule learners, including greedy MinEntropy used at eBay, are among the fastest; automata and Petri-net methods can be fast for process models but are often inaccurate.Source: B. Learning models for RCA · pp. 5–6
- Stream-oriented decision trees handle data that may be read only once and need not fit in memory; adaptive Hoeffding-tree variants detect change and update trees.Apache Samoa implements attempts to parallelize decision-tree creation for heavy streams.Source: B. Learning models for RCA · p. 6
- Training costs differ sharply: Naïve Bayes can use one data pass, general SVM training is O(n^2) to O(n^3), and neural-net learning is NP-complete.An iterative approximate SVM approach can reduce complexity to O(nr), where r is the number of iterations.Source: B. Learning models for RCA · p. 6
- LGL raised causal-inference scale to one million variables, from PC’s difficulty beyond about a hundred, though LGL runtime ranges from quadratic to exponential with its parameters.Learning Bayesian Networks is NP-complete.Source: B. Learning models for RCA · p. 6
- Parallel versions of existing learning algorithms have been proposed, but parallelizability does not ensure speedup close to the theoretical maximum.Source: B. Learning models for RCA · p. 6
- With high system evolution, RCA requires incremental model updates or fast relearning; classifiers can be a poor fit, especially when they need many instances.ID5R and chi-square updates for Bayesian Networks are examples of incremental algorithms; fast change can leave few training instances, while human diagnosis is typically slow.Source: B. Learning models for RCA · pp. 6–7
IV. INFERENCE IN RCA MODELS
Inference algorithms map observed symptoms to potential causes, but their outputs and computational costs vary across RCA models. The survey compares these approaches and describes trade-offs among tractability, expressiveness, and response time.
IV. INFERENCE IN RCA MODELS
- Marginals, MPE, and MAP differ in which possible worlds or variables they aggregate, so the choice depends on model meaning and concurrent-fault scope.Marginals suit single-fault diagnosis, while MPE and MAP are more suited to multiple failures; MAP can abstract variables not representing causes.Source: §IV · p. 7
- Approximate inference can suit real-time diagnosis when it provides a sufficiently accurate answer within the available time.Exact diagnosis can be expensive: even basic set covering on a bipartite non-probabilistic graph is NP-hard.Source: §IV · p. 8
- Exact and approximate MPE and MAP remain NP-hard for general Bayesian networks, with complexity also depending on network structure.MPE is O(n exp(w)); MAP is O(n exp(wc)), where constrained tree width wc exceeds regular tree width w.Source: §IV · p. 8
- Arithmetic circuits trade compilation and possible exponential circuit size for fast evaluation and reusable computation, but structural network changes require recompilation.Under an assumption of at most k simultaneous root causes, another MAP approach has complexity O(f^k).Source: §IV · p. 8
- Classifiers and codebooks can offer fast inference, but codebooks ordinarily assume one failure; supporting up to k faults expands the codebook to f^k entries.Decision-tree classifier inference is O(d), while exhaustive codebook search for up to k faults is O(f^k · s).Source: §IV · pp. 9, 11
- Explanatory extensions can organize large variable subsets as relevance-ranked trees, while parallel inference offers another route to address computational cost.Causal explanation trees require O(nd) inference-engine calls per node, compared with O(n^2d^2) for explanation trees.Source: §IV · pp. 11–12
V. CONCLUSION
The survey reviews RCA models and inference algorithms, finding a spectrum of techniques that trade tractability against expressiveness. It identifies a Big Data-focused users’ guide as future work.
V. CONCLUSION
- The survey reviews models and inference algorithms used for root-cause analysis.The reviewed techniques span a trade-off between tractability and expressiveness.Source: §V · p. 12
- The survey plans to extend its coverage to Big Data RCA with a users’ guide for that setting.Source: §V · p. 12