We address the problem of verifying PCTL properties of Markov Decision Processes whose state transition probabilities are only known to lie within uncertainty sets. Using results from convex theory and duality, we propose a suite of veriﬁcation algorithms and prove their soundness, completeness and termination when arbitrary convex models of uncertainty are considered. Furthermore, soundness and termination can also be guaranteed when non-convex models of uncertainty are adopted. We validate the proposed approach on two case studies: the verification of a consensus protocol when one of the processes behaves erroneously and the dining philosopher problem.
To Be Certain about Uncertainties: Probabilistic Model Checking with Uncertainties
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).