No effective methods exist to predict failure regimes in large distributed systems—the search space is 

large and causality is difficult to establish. Our research goals are to: (1) develop design-time methods 

that system engineers can use to detect existence and causes of costly failure regimes prior to system 

deployment and (2) develop run-time methods that system managers can use to detect onset of costly 

failure regimes in deployed systems, prior to collapse.

Mitigating Global Failure Regimes in Large Distributed Systems

(Ongoing Research)

C. Dabrowski, J. Filliben, K. Mills, S. Ressler and B. Rust from NIST

Approach One: Combine Markov Models, 

Graph Analysis and Perturbation Analysis

First 

Hard

Problem

http://www.nist.gov/itl/antd/emergent_behavior.cfm

Second 

Hard

Problem

Approach Two: Combine Anti-Optimization 

and Genetic Algorithms

Approach Three: Measuring Key System 

Properties such as Critical Slowing Down

How might your organization benefit from 

collaborating with us?

Innovations in Measurement Science 

Example: Markov simulation and 

perturbation of a minimal s-t cut set 

of a Markov chain graph:

Using simulated failure scenarios in a 

Markov chain model to predict failures in a Cloud

• Corresponds to software failure 

scenario involving multiple 

faults/attacks.

• Simulation identifies threshold 

beyond which increased failure 

incidence causes drastic 

performance collapse

 Verified in target system being 

modeled (i.e., Koala, a large-scale 

simulation of a Cloud)

0.0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1.0

0.0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1.0 Decrease in Probabilities of Transition Proportion of Requests Granted

Total Grants (Large Scale 

Simulation)

Increase in Probability of Transition from Allocating_Partial

state (11) to Transferring_Failure_Estimate state (10). 

Increase in Probability of Transition from Allocating_ 

Maximum state (9) to Allocating_Partial state (11). 

Decrease in probability of 

transition from Allocating_Maximum

state (9) to Recording_Allocation (12) state. 

Decrease in Probability of Transition 

from Allocating_Partial state (11) to 

Recording_Allocation state (12). 

0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1 Decrease in Probabilities of Transition Proportion of Requests Granted (both Full and Partial)

Increase in Probability of Transition from Selecting 

Next Cluster state (14) to Selection_Failing state (15)

(a) Total Grants (Markov Simulation)

(b) Total Grants (Large Scale Simulation)

Decrease in probability of transition from

Selecting_Next_Clusterstate (14) to Transferring_

Implementation_Request (F) state (17)

Decrease in probability of transition from Selecting_ 

Next_Cluster state (14) to Transferring_

Implementation_Request (P) state (18)

 IF your organization designs and deploys Clouds and other large distributed 

systems AND

 You wish to improve the reliability of your system AND

 You have a model of your system OR 

 You are willing to share sufficient information for us to construct a model AND 

you are willing to help us ensure our model suitability represents your system

 THEN working together we could help you improve the reliability of 

your system (or specific aspects of your system) by:

 Applying our design-time methods to search the design space for potential 

collapse scenarios (and iterating on any proposed design revisions you create to 

mitigate collapse scenarios) AND/OR

 Exploring run-time monitoring and measurement approaches that could signal 

incipient onset of collapse scenarios that were not detected using our designtime methods 

WIN-WIN: we would gain additional evaluation and refinement of our methods and 

you could gain a transfer of our technology to enhance your design process. 

A simple univariate example predicting power 

grid blackout in a human engineered system*

*From P. Hines, E. Cotilla-Sanchez, and S. Blumsack. Topological Models and Critical Slowing Down: Two Approaches to Power System Risk Analysis. 

Proceedings of the 44th Hawaii Conference on System Sciences. IEEE Computer Society, Washington, DC, USA, pp. 1-10.