Principled network reliability approximation: A counting-based approach

R. Paredes, Dueñas-Osorio, L., K.S. Meel and M.Y. Vardi

Reliability Engineering and System Safety, 2019, vol. 191, issue C

Abstract: As engineered systems expand, become more interdependent, and operate in real-time, reliability assessment is key to inform investment and decision making. However, network reliability problems are known to be #P-complete, a computational complexity class believed to be intractable, and thus motivate the quest for approximations. Based on their theoretical foundations, reliability evaluation methods can be grouped as: (i) exact or bounds, (ii) guarantee-less sampling, and (iii) probably approximately correct (PAC). Group (i) is well regarded due to its useful byproducts, but it does not scale in practice. Group (ii) scales well and verifies desirable properties, such as the bounded relative error, but it lacks error guarantees. Group (iii) is of great interest when precision and scalability are required. We introduce K-RelNet, an extended counting-based method that delivers PAC guarantees for the K-terminal reliability problem. We also put our developments in context relative to classical and emerging techniques to facilitate dissemination. Then, we test in a fair way the performance of competitive methods using various benchmark systems. We note the range of application of algorithms and suggest a foundation for future computational reliability and resilience engineering, given the need for principled uncertainty quantification across complex networked systems.

Keywords: Network reliability; FPRAS; PAC; Relative variance; Uncertainty; Model counting; Satisfiability (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0951832018305209
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:reensy:v:191:y:2019:i:c:s0951832018305209

DOI: 10.1016/j.ress.2019.04.025

Access Statistics for this article

Reliability Engineering and System Safety is currently edited by Carlos Guedes Soares

More articles in Reliability Engineering and System Safety from Elsevier
Bibliographic data for series maintained by Catherine Liu ().