Toggle Main Menu Toggle Search

Open Access padlockePrints

The Newcastle University research output collection, currently available on ePrints, will shortly be moving to a new open repository platform, Figshare. To prepare for the data migration we have paused adding new content to ePrints, and will resume once the new repository is launched. During this time you will continue to have access to ePrints (but no new content will appear). We will share updates here when available.

A structural proof of the soundness of rely/guarantee rules (revised)

Lookup NU author(s): Dr Joey Coleman, Emeritus Professor Cliff JonesORCiD

Downloads

Abstract

Various forms of rely/guarantee conditions have been used to record and reason about interference in ways that provide compositional development methods for concurrent programs. This paper illustrates such a set of rules and proves their soundness. The underlying concurrent language allows fine-grained interleaving and nested concurrency; it is defined by an operational semantics; the proof that the rely/guarantee rules are consistent with that semantics (including termination) is by a structural induction. A key lemma which relates the states which can arise from the extra interference that results from taking a portion of the program out of context makes it possible to do the proofs without having to perform induction over the computation history. This lemma also offers a way to think about expressibility issues around auxiliary variables in rely/guarantee conditions.

Publication metadata

Author(s): Coleman JW, Jones CB

Publication type: Report

Publication status: Published

Series Title: School of Computing Science Technical Report Series

Year: 2007

Pages: 31

Print publication date: 01/06/2007

Source Publication Date: June 2007

Report Number: 1029

Institution: School of Computing Science, University of Newcastle upon Tyne

Place Published: Newcastle upon Tyne

URL: http://www.cs.ncl.ac.uk/publications/trs/papers/1029.pdf

Share