Gerhard Schellhorn (University of Augsburg): Verification of Lock-Free Algorithms with RGITL
Abstract: The talk will describe a variant of ITL, which permits to extend the intuitive proof paradigm of symbolic execution for sequential programs to shared-variable parallel programs with temporal properties.
A simple embedding of rely-guarantee reasoning is possible due to the compositional semantics of interleaving.
The calculus is implemented in the interactive theorem prover KIV. We demonstrate its usability by verifying linearizability and lock-freedom for a stack with hazard pointers.
