A Perspective on Specifying and Verifying Concurrent Modules
Venue
Journal of Logical and Algebraic Methods in Programming, vol. 98, pp. 1–25
Publication Year
2018
Keywords
Concurrency, Specification, Program verification
Identifiers
Authors
- Thomas Dinsdale-Young
- Pedro da Rocha Pinto
- Philippa Gardner
Abstract
The specification of a concurrent program module, and the verification of implementations and clients with respect to such a specification, are difficult problems. A specification should be general enough that any reasonable implementation satisfies it, yet precise enough that it can be used by any reasonable client. We survey a range of techniques for specifying concurrent modules, using the example of a counter module to illustrate the benefits and limitations of each. In particular, we highlight four key concepts underpinning these techniques: auxiliary state, interference abstraction, resource ownership and atomicity. We demonstrate how these concepts can be combined to achieve two powerful approaches for specifying concurrent modules and verifying implementations and clients, which remove the limitations highlighted by the counter example.