On progressive recovery in interdependent cyber physical systems

This paper studies how to determine an optimal order of recovering interdependent Cyber Physical Systems (CPS) after a large scale failure. In such a CPS, some failed devices must be repaired first before others can. In addition, such failed devices require a certain amount of repair resources and may take multiple stages to repair. We consider two scenarios: 1) reserved model where all the required repair resources should be prepared at the beginning of repairing a device; and 2) opportunistic model where we can partially repair a device with only part of the required resources. For each scenario, we model it using an Integer Linear Programming (ILP) and use a relaxation and rounding method to design an ILP based algorithm. In addition, we also design a Dynamic Programming (DP) based algorithm. Simulation results show that ILP based algorithm outperforms DP based algorithm by 10%-20% in systems with less than 200 failed devices, but DP based algorithm can support extreme large size systems with more than 5000 failed devices.