Efficient Algorithms for Analyzing Cascading Failures in a Markovian Dependability Model
| Autor: | Matthew Downey, Sashank Tadepalli, Marvin K. Nakayama, Mihir Sanghavi, Timothy J. Boyle |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
021110 strategic
defence & security studies 021103 operations research Theoretical computer science Markov chain Computer science Computation 0211 other engineering and technologies Markov process Approximation algorithm 02 engineering and technology Tree (graph theory) Cascading failure symbols.namesake Approximation error symbols Dependability Electrical and Electronic Engineering Safety Risk Reliability and Quality Algorithm |
| Zdroj: | IEEE Transactions on Reliability. 66:258-280 |
| ISSN: | 1558-1721 0018-9529 |
| DOI: | 10.1109/tr.2017.2684785 |
| Popis: | We devise efficient algorithms to construct, evaluate, and approximate a Markovian dependability system with cascading failures. The model, which was previously considered by Iyer et al. , represents a cascading failure as a tree of components that instantaneously and probabilistically fail. Constructing the Markov chain presents significant computational challenges because it requires generating and evaluating all such possible trees, but the number of trees can grow exponentially in the size of the model. Our new algorithm reduces runtimes by orders of magnitude compared to a previous method devised by Iyer et al. Moreover, we propose some efficient approximations based on the idea of most likely paths to failure to further substantially reduce the computation time by instead constructing a model that uses only a subset of the trees. We also derive two new dependability measures related to the distribution of the size of a cascade. We present numerical results demonstrating the effectiveness of our approaches. For a model of a large cloud-computing system, our approximations reduce computation times by orders of magnitude with only a few percent error in the computed dependability measures. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|