TY - JOUR
T1 - The Safe and Effective Application of Probabilistic Techniques in Safety-Critical Systems
AU - Agrawal, Kunal
AU - Baruah, Sanjoy
AU - Guo, Zhishan
AU - Li, Jing
N1 - Funding Information:
This research was supported, in part, by the National Science Foundation (USA) under Grant Numbers CNS–1948457, CNS–1814739, CNS–1911460, CPS–1932530, CNS–1850851, OIA–1937833, CCF-1733873 and CCF–1725647, and in part by Northrop Grumman Corporation grant.
Publisher Copyright:
© 2020 Association on Computer Machinery.
PY - 2020/11/2
Y1 - 2020/11/2
N2 - The use of randomized algorithms in safety-critical systems is investigated. Under the vast majority of circumstances, randomized algorithms out-perform deterministic ones on average; however, it is not obvious how one goes about establishing the correctness of safety-critical systems that use such algorithms. The approach advocated in this work is to exploit the fact that many safety standards allow for small probabilities of failure of even the most critical functionalities. We explore the use of concentration bounds - probabilistic bounds on the likelihood of the performance of a randomized algorithm deviating from its expected performance - to bound the probability of failure of systems that incorporate randomized algorithms, thereby showing compliance with safety standards that allow for small probabilities of failure. We illustrate the use of the proposed approach on several examples that both explain how the approach is to be applied, and demonstrate the benefits of doing so.
AB - The use of randomized algorithms in safety-critical systems is investigated. Under the vast majority of circumstances, randomized algorithms out-perform deterministic ones on average; however, it is not obvious how one goes about establishing the correctness of safety-critical systems that use such algorithms. The approach advocated in this work is to exploit the fact that many safety standards allow for small probabilities of failure of even the most critical functionalities. We explore the use of concentration bounds - probabilistic bounds on the likelihood of the performance of a randomized algorithm deviating from its expected performance - to bound the probability of failure of systems that incorporate randomized algorithms, thereby showing compliance with safety standards that allow for small probabilities of failure. We illustrate the use of the proposed approach on several examples that both explain how the approach is to be applied, and demonstrate the benefits of doing so.
KW - concentration bounds
KW - failure probabilities
KW - randomized algorithms
KW - safety standards
KW - safety-critical systems
UR - http://www.scopus.com/inward/record.url?scp=85097924441&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85097924441&partnerID=8YFLogxK
U2 - 10.1145/3400302.3415674
DO - 10.1145/3400302.3415674
M3 - Conference article
AN - SCOPUS:85097924441
SN - 1092-3152
VL - 2020-November
JO - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
JF - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
M1 - 9256415
T2 - 39th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2020
Y2 - 2 November 2020 through 5 November 2020
ER -