Invariant generation for linearizability proofs
Graeme Smith, John Derrick · 2016
Linearizability is a widely recognised correctness criterion for concurrent objects. A number of proof methods for verifying linearizability exist. In this paper, we simplify one such method with a systematic approach for invariant generation. Although this existing refinement-based method is itself systematic and fully tool-supported, it requires the verifier to provide a specific invariant over the implementation. While a chosen invariant may suffice for some proof obligations of the method, it may not for others resulting in a new, stronger invariant to be chosen and the previously completed proof steps to be redone. Our approach avoids such wasted proof effort by generating an invariant which is guaranteed to be sufficient for all proof obligations.