Towards linking correctness conditions for concurrent objects and contextual trace refinement

Brijesh Dongol
(Brunel University London)
Lindsay Groves
(Victoria University of Wellington)

Correctness conditions for concurrent objects describe how atomicity of an abstract sequential object may be decomposed. Many different concurrent objects and proof methods for them have been developed. However, arguments about correctness are conducted with respect to an object in isolation. This is in contrast to real-world practice, where concurrent objects are often implemented as part of a programming language library (e.g., java.util.concurrent) and are instantiated within a client program. A natural question to ask, then is: How does a correctness condition for a concurrent object ensure correctness of a client program that uses the concurrent object? This paper presents the main issues that surround this question and provides some answers by linking different correctness conditions with a form of trace refinement.

In John Derrick, Eerke Boiten and Steve Reeves: Proceedings 17th International Workshop on Refinement (Refine'15), Oslo, Norway, 22nd June 2015, Electronic Proceedings in Theoretical Computer Science 209, pp. 107–111.
Published: 4th June 2016.

ArXived at: https://dx.doi.org/10.4204/EPTCS.209.8 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org