A network with multi-state arcs or nodes is commonly called a multi-state network. In the real world, the system reliability of a multi-state network can vary over time. Hence, a critical issue emerges to characterize the time attribute in a stochastic flow network. To solve this issue, this study bridges conventional reliability theory and the reliability of multi-state network. This study utilizes exponential distribution as a possible reliability function to quantify the time attribute in a multi-state network. First, the reliability of every single component is modeled by exponential distribution, where such components comprise a multi-state element. Once the time constraint is given, the capacity probability distribution of arcs can be derived. Second, an algorithm to generate minimal capacity vectors for given demand is provided. Finally, the system reliability can be calculated in terms of the derived capacity probability distribution and the generated minimal capacity vectors. A maintenance issue is further discussed according to the result of system reliability.