New Lace and Arsenic: adventures in weak memory with a program logic - Bornat, Richard; Alglave, Jade; Parkinson, Matthew J. (ArXiv, 2016)
We describe a program logic for weak memory (also known as relaxed memory). The logic is based on Hoare logic within a thread, and rely/guarantee between threads. It is presented via examples, giving proofs of many weak-memory litmus tests. It extends to coherence but not yet to synchronised assignment (compare-and-swap, load-logical/store-conditional). It deals with conditionals and loops but not yet arrays or heap. The logic uses a version of Hoare logic within threads, and a version of rely/guarantee between threads, with five stability rules to handle various kinds of parallelism (external, internal, propagation-free and two kinds of in-flight parallelism). There are B and U modalities to regulate propagation, and temporal modalities since, Sofar and Ouat to deal with global coherence (SC per location). The logic is presented by example. Proofs and unproofs of about thirty weak-memory examples, including many litmus tests in various guises, are dealt with in detail. There is a proof of a version of the token ring.
Matthew Parkinson