Control Policies for Recovery of Interdependent Systems After Disruptions

Since node $i_{1}$ is partially repaired by the entity before it targets the nodes $i_{2},\ldots,i_{k}$ in sequence $A$, there cannot be an edge that starts from $i_{1}$ and ends at a node in the set $\{i_{2},\ldots,i_{k}\}$. Thus, if sequence $A$ follows the precedence constraints, the non-jumping sequence $B$ also respects the precedence constraints. We can now leverage the analysis in [14], which proved that (1)-(3) hold and each node in sequence $B$ is targeted at an earlier time-step than in sequence $A$. Therefore, sequence $B$ permanently repairs all the nodes that are permanently repaired by sequence $A$ while respecting the precedence and time constraints. Thus, the result follows. ∎

Let $x$ be the number of nodes that are permanently repaired in sequence $A$. Denote the order of nodes in the sequence $A$ as $\{i_{1},\ldots,i_{x}\}$. The proof for the case when $x=1$ is trivial because $x-1=0$; we thus focus on the case when $x\geq 2$. Denote the ordering of the first $x-1$ nodes in sequence $B$ as $\{i^{\prime}_{1},\ldots,i^{\prime}_{x-1}\}$, where $i^{\prime}_{1}=h$. Note that the proof when $x=2$ is also trivial because node $i^{\prime}_{1}=h$ in the non-jumping sequence $B$ is permanently repaired since the time taken to permanently repair node $h$ in sequence $B$ is less than the time taken to permanently repair the nodes in sequence $A$ (because node $h$ has larger initial health than node $i_{1}$). Therefore, the non-trivial cases are when $x\geq 3$.

We first argue that sequence $B$ permanently repairs at least $x-1$ nodes, regardless of the time it takes to repair the nodes. We prove the result by contradiction. Suppose sequence $B$ permanently repairs less than $x-1$ nodes. Let $i^{\prime}_{k}$ be the first node that permanently fails in sequence $B$, where $2\leq k\leq x-1$. We first argue that either $i^{\prime}_{k}=i_{k-1}$ or $i^{\prime}_{k}=i_{k}$. If node $h$ does not appear in sequence $A$, then the first $x-1$ nodes of sequence $B$ are ordered as follows $\{h,i_{1},\ldots,i_{x-2}\}$ and thus $i^{\prime}_{k}=i_{k-1}$. On the other hand, if node $h$ is permanently repaired in sequence $A$, let the position of node $h$ in sequence $A$ be $z$, where $z\in\{2,\ldots,x\}$. Then, $i^{\prime}_{1}=h$, $i^{\prime}_{j}=i_{j-1},\quad\forall j\in\{2,\ldots,z\}$ and $i^{\prime}_{j}=i_{j},\quad\forall j\in\{z+1,\ldots,x-1\}$. Thus, if the first node that fails in sequence $B$ (i.e., node $i^{\prime}_{k}$) is such that $k\leq z$, then $i^{\prime}_{k}=i_{k-1}$; otherwise $i^{\prime}_{k}=i_{k}$. We now consider the cases when $i^{\prime}_{k}=i_{k-1}$ and $i^{\prime}_{k}=i_{k}$ one by one.

Suppose $i^{\prime}_{k}=i_{k-1}$. If node $i_{k-1}$ fails in sequence $B$, then we show that node $i_{k+1}$ must permanently fail in sequence $A$ (where $2\leq k\leq x-1$). Consider $k=2$. Let $t_{h}=\frac{1-v_{0}^{h}}{\Delta_{inc}}$ be the number of time-steps taken to permanently repair node $h$ from its initial health to the full health. If node $i_{1}$ permanently fails after permanently repairing node $h$ in sequence $B$, then $v_{0}^{i_{1}}\leq\Delta_{dec}t_{h}$. That is,

Denote $t_{j}=\frac{1-v_{0}^{i_{j}}}{\Delta_{inc}}$ as the number of time-steps taken to permanently repair node $i_{j}$ from its initial health to full health. Then,

as $n\geq 1$ and $v_{0}^{i_{1}}<1$. Therefore,

where the first inequality from the left comes by conditions (4)-(5) and the second inequality comes from the fact that $t_{h}<t_{1}$ (as node $h$ has larger initial health than node $i_{1}$). Note that in sequence $A$, it takes $t_{1}$ time-steps to repair node $i_{1}$, and $nt_{1}+t_{2}$ time-steps to repair node $i_{2}$ (it takes $nt_{1}$ time-steps to repair the health that is lost by node $i_{2}$ due to deterioration and it takes $t_{2}$ time-steps to repair the difference in the initial health of $i_{2}$ and full health). By (6), the total reduction in the health of node $i_{3}$ after $(1+n)t_{1}+t_{2}$ time-steps in sequence $A$ satisfies

as $n\geq 1$ and $t_{1},t_{2}>0$. Thus, node $i_{3}$ permanently fails in sequence $A$ by the time it is reached, contradicting the fact that $A$ permanently repairs $x(\geq 3)$ nodes.

Now consider the case when $k=3$. If node $i_{2}$ permanently fails in sequence $B$, then $v_{0}^{i_{2}}\leq\Delta_{dec}((1+n)t_{h}+t_{1})$. Following the same arguments as before, we get

As before, the total number of time-steps required to permanently repair nodes $i_{1},i_{2}$, and $i_{3}$ in sequence $A$ is equal to $(1+n)^{2}t_{1}+(1+n)t_{2}+t_{3}$. Thus, the total reduction in the health of node $i_{4}$ by the time it is reached in sequence $A$ satisfies

by (7), $n\geq 1$ and $t_{1},t_{2},t_{3}>0$. Thus, $i_{4}$ permanently fails by the time it is reached in sequence $A$, leading to a contradiction.

We can repeat the above arguments to show that if node $i_{k-1}$ permanently fails in sequence $B$, where $k>3$, then

Therefore, the total reduction in the health of node $i_{k+1}$ after $(1+n)^{k-1}t_{1}+(1+n)^{k-2}t_{2}+\ldots+(1+n)^{0}t_{k}$ time-steps in sequence $A$ is

Thus, for $k>3$, we get

by (8), (9), $n\geq 1$ and $t_{j}>0\hskip 2.84526pt\forall j$. Since, the total reduction in the health value of node $i_{k+1}$ before the entity starts targeting it is larger than one, it is not possible to permanently repair node $i_{k+1}$ in sequence $A$, leading to a contradiction.

We now consider the case when $i^{\prime}_{k}=i_{k}$ (along with $x\geq 3$). We prove that if node $i^{\prime}_{k}=i_{k}$ permanently fails in sequence $B$, then it is not possible to permanently repair node $i^{\prime}_{k+1}=i_{k+1}$ in sequence $A$. Recall that the case $i^{\prime}_{k}=i_{k}$ happens when node $h$ is permanently repaired in sequence $A$ and $k>z$. Since $z\geq 2$, we have $k>2$. Consider $k=3$. Then, $z=2$ (i.e., $i_{2}=h$) because $z<k$ and $z\geq 2$. If node $i^{\prime}_{3}=i_{3}$ permanently fails in sequence $B$, then

or equivalently,

Therefore, the total reduction in the health of node $i_{4}$ after $(1+n)^{2}t_{1}+(1+n)t_{2}+t_{3}$ time-steps in $A$ satisfies

by (10), $n\geq 1$ and $t_{1},t_{2}>0$. Thus, node $i_{4}$ permanently fails in sequence $A$, contradicting the fact that $A$ permanently repairs $x$ nodes.

Similarly, it can be shown that if node $i^{\prime}_{k}=i_{k}$ permanently fails in sequence $B$, where $k>3$, then

Therefore, the total reduction in the health of node $i_{k+1}$ (where $k>3$) after $(1+n)^{k-1}t_{1}+(1+n)^{k-2}t_{2}+\ldots+(1+n)^{0}t_{k}$ time-steps in sequence $A$ is

by (11), $n\geq 1$ and $t_{j}>0\hskip 2.84526pt\forall j$. Therefore, it would not be possible to permanently repair $x$ nodes in sequence $A$, leading to a contradiction.

We will now show that sequence $B$ permanently repairs $x-1$ nodes in less time than the time taken to permanently repair $x$ nodes in sequence $A$. Suppose node $h$ is not permanently repaired in sequence $A$. Consider $x=3$. Then, the time taken to permanently repair the first two nodes, i.e., nodes $h$ and $i_{1}$, in sequence $B$ is equal to $(1+n)t_{h}+t_{1}$ and the time taken to permanently repair three nodes in sequence $A$ is equal to $(1+n)^{2}t_{1}+(1+n)t_{2}+t_{3}$. Note that $(1+n)t_{h}+t_{1}<(2+n)t_{1}<(1+n)^{2}t_{1}+(1+n)t_{2}+t_{3}$ because $t_{h}<t_{1}$, $n\geq 1$ and $t_{1},t_{2},t_{3}>0$. Consider the case when $x>3$. Then, the time taken to permanently repair $x-1$ nodes in sequence $B$ is equal to

and the time taken to permanently repair $x$ nodes in sequence $A$ is equal to

Then, $(1+n)^{x-2}t_{h}+(1+n)^{x-3}t_{1}+(1+n)^{x-4}t_{2}+\ldots+(1+n)^{0}t_{x-2}<\left((2+n)(1+n)^{x-3}\right)t_{1}+(1+n)^{x-4}t_{2}+\ldots+(1+n)^{0}t_{x-2}<(1+n)^{x-1}t_{1}+(1+n)^{x-2}t_{2}+\ldots+(1+n)^{0}t_{x}$ as $t_{h}<t_{1}$, $n\geq 1$ and $t_{j}>0,\forall j\in\{1,\ldots,x\}$.

Now consider the case when node $h$ is permanently repaired in sequence $A$. When $z\geq x-1$ (and $x\geq 3$), the time taken to permanently repair $x-1$ nodes in sequence $B$ and the time taken to permanently repair $x$ nodes in sequence $A$ are given by expressions (12) and (13), respectively, and therefore the proof proceeds in the same way as when node $h$ is not permanently repaired in sequence $A$. Thus, the proof for $x=3$ follows in exactly the same way as before because $z\geq 2$. We now focus on the case when $z\leq x-2$ and $x>3$. Then, the total time taken to permanently repair $x-1$ nodes in sequence $B$ is equal to

and the time taken to permanently repair $x$ nodes in sequence $A$ is given by the expression (13). Note that the value of the expression (14) is less than the value of the expression (13) because $t_{h}<t_{1}$, $n\geq 1$ and $t_{j}>0,\forall j\in\{1,\ldots,x\}$. Therefore, if sequence $A$ permanently repairs $x$ nodes by time-step $T$, then sequence $B$ must permanently repair at least $x-1$ nodes by time-step $T$. Thus, the result follows. ∎

Let $A$ be the optimal (non-jumping) sequence. Then, we go to the first time-step $T^{\prime}(\leq T)$ in sequence $A$ at which the healthiest available node (i.e., the healthiest node that can be targeted at time-step $T^{\prime}$ without violating the precedence constraints) is not targeted. Denote the portion of sequence $A$ from time-step $0$ to time-step $T^{\prime}-1$ as $A^{\prime}$ and the portion of sequence from time-step $T^{\prime}$ onwards as $A^{\prime\prime}$. We modify the sequence $A^{\prime\prime}$ by Lemma 2 to generate sequence $A^{*}$ such that the healthiest available node (while respecting the precedence and time constraints) is targeted at time-step $T^{\prime}$ in $A^{*}$. Let $y$ be the number of nodes that are permanently repaired by sequence $A^{\prime\prime}$. Then, at least $y-1$ nodes are permanently repaired in sequence $A^{*}$ (while respecting the precedence and time constraints) by Lemma 2. Then, a sequence $B$ is generated by concatenating $A^{\prime}$ with $A^{*}$. After this, we go to the next time-step in sequence $B$ at which the healthiest node (while respecting the precedence and time constraints) is not targeted and repeat this procedure. We iteratively repeat this procedure, so that we finally get a sequence in which the healthiest node (while respecting the precedence and time constraints) is targeted at each time-step. The number of nodes that are permanently repaired in the final sequence will be at least half of the number of nodes that are permanently repaired in sequence $A$ because 1) at each iteration of this procedure we move one node across the given sequence and the number of nodes that are permanently repaired in the modified sequence reduces at most by one, and 2) in the last iteration of this procedure where there is only one node, there is no reduction in the number of permanently repaired nodes because if the last node in the given sequence can be permanently repaired then a healthier node that replaces it can also be permanently repaired. ∎

Consider any optimal (non-jumping) sequence $A=\{i_{1},\ldots,i_{x}\}$ that permanently repairs $x(\leq N)$ nodes. Let $T^{\prime}(\leq T+1)$ be the total number of time-steps taken by the sequence $A$ to permanently repair all $x$ nodes.⁴⁴4Note that the total number of time-steps is one larger than the largest time-step index $T$ because the first time-step in a sequence is time-step 0. Then,

where $E_{j}$ is the health of node $i_{j}$ when it is reached in the sequence, i.e., $E_{1}=v_{0}^{i_{1}}$ and $E_{k}=v_{0}^{i_{k}}-n\sum_{j=2}^{k}\left(1-E_{j-1}\right)$ for $k\in\{2,\ldots,x\}$. Alternatively, $E_{k}=v_{0}^{i_{1}}n\left(1+n\right)^{k-2}+v^{i_{2}}_{0}n(1+n)^{k-3}+\ldots+v_{0}^{i_{k-1}}n+v^{i_{k}}_{0}-n\left(1+n\right)^{k-2}-n(1+n)^{k-3}-\ldots-n$ for all $k\in\{2,\ldots,x\}$. Note that $E_{1}$ is the largest when node $i_{1}$ has the largest initial health; $E_{2}$ is the largest when node $i_{1}$ has the largest initial health and node $i_{2}$ has the second largest initial health (as the coefficients of $v_{0}^{i_{1}}$ and $v_{0}^{i_{2}}$ are $n$ and 1, respectively); $E_{3}$ is the largest when node $i_{1}$ has the largest initial health, node $i_{2}$ has the second largest initial health and node $i_{3}$ has the third largest initial health (as the coefficients of $v_{0}^{i_{1}}$, $v_{0}^{i_{2}}$ and $v_{0}^{i_{3}}$ are $n(1+n)$, $n$ and 1, respectively); and so on. Thus, the non-jumping sequence $B$ that targets the nodes in decreasing order of their initial health is optimal when time is constrained because it permanently repairs $x$ nodes in less time in comparison to the time taken by sequence $A$ to permanently repair $x$ nodes (as the value of $T^{\prime}$ in (15) for sequence $B$ is less than the corresponding value for sequence $A$). Therefore, the policy that targets the healthiest node at each time-step while respecting the time constraint is optimal by Theorem 1. ∎

Due to precedence constraints, we need to permanently repair all the nodes in the first level before targeting the other nodes in a complete series graph. Since the optimal policy is to target the healthiest node at each time-step (while respecting the time constraint) when there are no precedence constraints (by Theorem 4), we follow this policy for the nodes in the first level. After permanently repairing all the nodes in the first level, we need to permanently repair all the nodes in the second level before targeting other nodes. Thus, the policy of targeting the healthiest node at each time-step (while respecting the time constraint) in the second level is followed after permanently repairing all the nodes in the first level. The rest of the proof follows the above argument. ∎

Let $\mathcal{R}$ be the set of root nodes of the trees. Let $A$ denote the sequence that targets the node with the least modified health value in the set $\mathcal{R}$ at each time-step, and let $B$ denote the optimal sequence. Let the number of nodes that are permanently repaired by sequences $A$ and $B$ be $y$ and $x$, respectively. We will show that $y\geq\frac{x}{k}$. We prove this by contradiction. Suppose $\frac{x}{k}>y$. Denote the set of root nodes that are permanently repaired in sequence $B$ by $\mathcal{F}\subseteq\mathcal{R}$, and let $z\triangleq|\mathcal{F}|$. Note that $z\geq\left\lceil\frac{x}{k}\right\rceil$ because the root node in a tree should be permanently repaired before targeting other nodes in the tree. Then, $z\geq y+1$ because $\frac{x}{k}>y$ implies $\left\lceil\frac{x}{k}\right\rceil\geq y+1$. We now construct a sequence $C$ by modifying sequence $B$ such that at every time-step of sequence $B$ where a node not belonging to the set $\mathcal{F}$ is targeted, we replace that node with a node from the set $\mathcal{F}$. Then, sequence $C$ also permanently repairs all the nodes in the set $\mathcal{F}$ because the nodes of set $\mathcal{F}$ are targeted more frequently in sequence $C$ than in sequence $B$. Since the optimal policy is to target the node with the least modified health value at each time-step when there are no precedence and time constraints (by Proposition 1 of [14]), we obtain a contradiction because sequence $C$ permanently repairs $z\geq y+1$ nodes whereas sequence $A$ (which is the optimal sequence to permanently repair the set of root nodes) permanently repairs $y$ nodes. Therefore, the assumption that $\frac{x}{k}>y$ is not true.

Let the sequence that targets the node with the least modified health value (in the set $\mathcal{V}$) at each time-step while respecting the precedence constraints be denoted by $D$. We now argue that sequence $D$ permanently repairs at least as many nodes as sequence $A$. Denote the set of root nodes that are permanently repaired in sequence $A$ by $\mathcal{Z}\subseteq\mathcal{R}$ and the number of nodes in the set $\mathcal{Z}$ by $y$. Then, there exists an ordering of nodes in the set $\mathcal{Z}$, denoted by $\{i_{1},i_{2},\ldots,i_{y}\}$, such that the initial health values of those nodes satisfy

because of the following argument. Let $\mathcal{A}_{t}\subseteq\mathcal{Z}$ denote the set of nodes that have not been targeted at least once by the entity prior to time $t$ in sequence $A$. Note that $\mathcal{Z}=\mathcal{A}_{0}\supseteq\mathcal{A}_{1}\supseteq\ldots\supseteq\mathcal{A}_{y-1}$. At time $t=0$, $|\mathcal{A}_{t}|=y$, where $|\mathcal{A}_{t}|$ denotes the cardinality of set $\mathcal{A}_{t}$. At $t=1$, $|\mathcal{A}_{t}|=y-1$ as there are $y-1$ nodes of the set $\mathcal{Z}$ that have not been targeted at least once by the entity in sequence $A$ and thus each node $k\in\mathcal{A}_{1}$ should have initial health value larger than $\Delta_{dec}^{k}$ to survive until $t=1$. At $t=2$, $|\mathcal{A}_{t}|\geq y-2$ as there are at least $y-2$ nodes of the set $\mathcal{Z}$ that have not been targeted at least once by the entity in sequence $A$ and thus each node $k\in\mathcal{A}_{2}$ should have initial health value larger than $2\Delta_{dec}^{k}$. Repeating this argument for the next $y-3$ time-steps, we can argue that there must be a permutation $\{i_{1},\ldots,i_{y}\}$ of nodes that satisfies the conditions (16) in order for $y$ nodes to be permanently repaired in sequence $A$.