Formalization of resilience for constraint-based dynamic systems

Nicolas Schwind, Morgan Magnin, Katsumi Inoue, Tenda Okimoto, Taisuke Sato, Kazuhiro Minami, Hiroshi MaruyamaJ. Reliab. Intell. Environ 2016 · DOI

Introduction

While the term "resilience" is ubiquitous across engineering, ecology, and social sciences, its application in computer science has often remained qualitative and domain-specific. A resilient power grid is modeled differently than a resilient cloud network, leading to a lack of cross-disciplinary rigor. This paper addresses this gap by proposing a formal mathematical framework that quantifies resilience for systems that are both constrained and dynamic.

A Unified Mathematical Framework

The authors bridge two distinct fields to create their model:

  1. Constraint Optimization Problems (COPs): Used to represent the static state of a system, including resource configurations, operational costs, and performance penalties.
  2. Discrete Event Dynamic Systems (DEDS): Used to model the system's evolution over time as it responds to external shocks or "trajectories."

At the heart of this framework is the introduction of $(k, l)$-resilience. In this definition, $k$ represents a specific time interval, and $l$ represents a performance or cost threshold. A system is considered $(k, l)$-resilient if its average performance remains within the threshold $l$ for every window of time $k$. This parameterization allows for a unified definition of three classic resilience concepts:

  • Resistance: The capacity to absorb shocks without a drop in performance.
  • Recoverability: The speed and effectiveness of returning to a safe state after a disruption.
  • Functionality: The long-term maintenance of service levels.

Illustrative Example: Dynamic Server Management

To demonstrate the framework, the authors utilize a running example of a web service managing a server fleet. The system must adapt its configuration (e.g., scaling server sizes) to meet fluctuating demand while minimizing costs.

Dynamic adaptation of server configurations in response to a drastic increase in demand.

In this scenario, a "drastic increase of demand" forces the system to transition from a medium-capacity state to a high-capacity state. The framework measures how effectively the system's strategy manages this transition within defined cost constraints.

Key Insights: The Resiliency Function

A pivotal concept introduced is the "resiliency function." By plotting the minimum threshold $l$ required for various time intervals $k$, researchers can generate a unique "fingerprint" for a system's health. This allows for the visual comparison of different architectural strategies, distinguishing between systems that are robust (resistant to breaking) and those that are elastic (quick to recover).

A trajectory of system costs over time, demonstrating a threshold for 8-resistance.

As shown in the cost trajectory above, the framework can formally verify if a specific strategy maintains costs below a critical threshold (e.g., 8-resistance) across a sequence of events.

Results and Computational Complexity

The paper successfully provides the first rigorous mathematical definitions for $(k, l)$-resilience in constraint-based systems. However, the authors also highlight a significant challenge: while calculating the resilience of a single known path is computationally efficient (quadratic time), determining if a dynamic system is resilient across all possible future scenarios is far more complex due to the exponential growth of potential states.

Future Directions

Current limitations include the assumption of "perfect knowledge"—the idea that a controller always knows the exact state of the system. Future work aims to incorporate Partially Observable Markov Decision Processes (POMDPs) to account for sensor noise and uncertainty. Additionally, the authors suggest exploring the impact of human-in-the-loop decision-making on formal resilience metrics.

Summary updated

BibTeX
@article{schwind2016formalization,
  author = {Nicolas Schwind and Morgan Magnin and Katsumi Inoue and Tenda Okimoto and Taisuke Sato and Kazuhiro Minami and Hiroshi Maruyama},
  title = {{Formalization of resilience for constraint-based dynamic systems}},
  journal = {J. Reliab. Intell. Environ.},
  year = {2016},
  doi = {10.1007/s40860-015-0016-0},
}
Figure