A Perspective on Specifying and Verifying Concurrent Modules

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.

Venue

Journal of Logical and Algebraic Methods in Programming, vol. 98, pp. 1–25

Publication Date

Aug 2018

Keywords

Concurrency, Specification, Program verification

Identifiers

Source Materials