Causal Failures in Network Systems

The failure of system components can cause serious damage to the performance of the system (e.g., link failures can disrupt flow in a network system). In traditional models, the failures of links are usually considered to be independent. However, link failures could be causal, wherein a link fails due to the failure of another non-adjacent link in the network. We call this kind of failure a causal link failure. In this paper, we formally define causal link failures in flow networks and investigate the impact of such failures on flow transmission. We formulate a discrete optimization problem to find the maximum number of causal link failures after which the flow network can deliver <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d$</tex> units from source node <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$s$</tex> to terminal node <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$t$</tex>. We prove that the formulated problem is NP-hard and construct the corresponding optimization model. Furthermore, we present a greedy algorithm to approximately compute the solution to the problem. The experiments show the efficiency of the greedy algorithm compared to the optimization model.