Sixty Years of Network Reliability

The study of network reliability started in 1956 with a groundbreaking paper by E.F. Moore and C.E. Shannon. They introduced a probabilistic model of network reliability, where the nodes of the network were considered to be perfectly reliable, and the links or edges could fail independently with a certain probability. The problem is to determine the probability that the network remains connected under these conditions. If all the edges have the same probability of failing, this leads to the so-called reliability polynomial of the network. Sixty years later, a lot of research has accumulated on this topic, and many variants of the original problem have been investigated. We review the basic concepts and results, as well as some recent developments in this area, and we outline some important research directions.