FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
Operational Semantics of a Weak Memory Model with Channel Synchronization

Authors: Daniel Fava, Martin Steffen and Volker Stolz

Paper Information

Title:Operational Semantics of a Weak Memory Model with Channel Synchronization
Authors:Daniel Fava, Martin Steffen and Volker Stolz
Proceedings:FM FMComplete
Editors: Jan Peleska, Klaus Havelund and Bill Roscoe
Keywords:concurrency, memory model, operational semantics
Abstract:

ABSTRACT. A multitude of weak memory models exists supporting various types of relaxations and different synchronization primitives. On one hand, they must be lax enough to allow for hardware and compiler optimizations; on the other, the more lax the model, the harder it is to reason about programs. Though the right balance is up for debate, a memory model should provide what is known as the SC-DRF guarantee: data-race free programs behave in a sequentially consistent manner. Memory models are often defined axiomatically where the notion of a program is abstracted away (often as a graph with memory events as nodes) and orderings of memory events are defined via constraints. In this work we present a weak memory model for a calculus inspired by Go. Different from previous approaches, we thus focus on a memory model with buffered channel communication as the sole synchronization primitive. We formalize the memory model via an operational semantics and prove the SC-DRF guarantee using a standard simulation technique. The proof highlights meaningful invariants and gives insight into the workings of the memory model. Finally, we provide a concrete implementation in K, a rewrite-based executable semantic framework, which allows us to derive an interpreter for the proposed language.

Pages:18
Talk:Jul 16 12:00 (Session 111B)
Paper: