The Safe and Effective Application of Probabilistic Techniques in Safety-Critical Systems

Kunal Agrawal, Sanjoy Baruah, Zhishan Guo, Jing Li

Research output: Contribution to journalConference articlepeer-review

Abstract

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.

Original languageEnglish (US)
Article number9256415
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
Volume2020-November
DOIs
StatePublished - Nov 2 2020
Externally publishedYes
Event39th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2020 - Virtual, San Diego, United States
Duration: Nov 2 2020Nov 5 2020

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

Keywords

  • concentration bounds
  • failure probabilities
  • randomized algorithms
  • safety standards
  • safety-critical systems

Fingerprint Dive into the research topics of 'The Safe and Effective Application of Probabilistic Techniques in Safety-Critical Systems'. Together they form a unique fingerprint.

Cite this