Markov Chains for Fault-Tolerance Modeling of Stochastic Networks

Most real-world networks are time-varying, and many are subject to the stochastic functioning of their nodes and edges. Examples can be seen in the human brain undergoing an epileptic seizure, spontaneous infection and recovery in epidemics, and intermittent functioning of devices in the Internet of Things. Moreover, such networks are becoming increasingly large due to rapid technological advances. However, little has been done to study time-varying, large-scale, stochastic networks (SNs) from a reliability engineering perspective. Toward this goal, this article develops a fault-tolerance model for a type of time-varying network in which nodes (and/or edges) stochastically switch between active and inactive states. It considers fault tolerance from a global connectivity point of view, which has applications in many natural and engineered networks. Specifically, this article presents a Markov chain framework that models the dynamic behavior of nodes and allows for the computation of quantitative measures, including availability and time-to-failure metrics. To accommodate large-scale networks and emphasize global connectivity, this framework utilizes percolation theory, which has recently been of interest in the reliability engineering discipline, to characterize network failure. This article makes several contributions: it proposes a Markov chain framework for computing fault-tolerance metrics that is tractable for large-scale networks, it shows the existence of a phase transition in network availability of a time-varying SN, and it accounts for finite-size effects of percolation in the fault-tolerance model. The proposed methodology is applied to Erdos-Renyi random graphs and a real, large-scale power grid. Experimental results provide insights into network design, maintenance, and failure prevention of time-varying SNs.