Grounding Thin-Air Reads with Event Structures

Abstract

The key challenge in defining the concurrency semantics of a programming language is how to enable the most efficient compilation to existing hardware architectures, and yet forbid programs from reading thin-air values, i.e., ones that do not appear in the program. At POPL'17, Kang et al. achieved a major breakthrough by introducing the promising semantics that came with results showing that it was a good candidate solution to the problem. Unfortunately, however, the promising semantics is rather complicated, and due to its complexity it contains some flaws and limitations that are very hard to address.

In response, we present an alternative solution to this problem based on event structures. We show that it is indeed a solution by establishing the standard results about the semantics (DRF theorems, implementation and optimization correctness) as well as a formal connection to the semantics of Kang et al. Further, we show that it is easier to adapt, by extending the semantics to cover features (such as SC accesses) that are not supported by Kang et al. and to rule out some dubious behaviors admitted by the promising semantics.

Paper

• Soham Chakraborty and Viktor Vafeiadis
  Grounding Thin-Air Reads with Event Structures
  Proc. ACM Program. Lang. 3, POPL, Article 70 (January 2019)
  [Technical appendix]

People

• Soham Chakraborty (MPI-SWS)
• Viktor Vafeiadis (MPI-SWS)

Related projects

• promise-sem: An alternative approach solving the thin-air problem
• llvmcs: Formalizing the concurrency semantics of an LLVM fragment
• validc: Validating optimizations of concurrent C/C++ programs
• c11comp: Reasoning about C/C++11 program transformations
• scfix: Repairing sequential consistency in C/C++11