Verification of Concurrent Programs. Part II. Temporal Proof Principles

摘要

In this paper, the second of a series on the application of temporal logic to concurrent programs, we present proof methods for establishing invariance (safety) and eventuality (liveness) properties. The proof principle for establishing invariance properties is based on computational induction, and is a generalization of the inductive assertion method. For a restricted class of concurrent programs we present an algorithm for the automatic derivation of invariant assertions. In order to establish eventuality properties we present several proof principles that translate the structure of the program into basic temporal statements about its behavior. These principles can be viewed as providing the temporal semantics of the program. The basic statements thus derived are then combined into temporal proofs for the establishment of eventuality properties.