Degrees of Separation: A Flexible Type System for Safe Concurrency

Abstract:

Data races have long been a notorious problem in concurrent programming. They are hard to detect, and lead to non-deterministic behaviours. There has been a lot of interest in type systems that statically guarantee data race freedom. Significant progress has been made in this area, and these type systems are increasingly usable and practical. However, their adoption in mainstream programming languages is still limited, which is largely attributed to their strict alias prevention principles that obstruct the usage of existing programming patterns. This is a deterrent to the migration of existing code bases. To tackle this problem, we propose Capture Separation Calculus (System CSC), a calculus that models fork-join parallelism and statically prevents data races while being compatible with established programming patterns. It follows a control-as-you-need philosophy: by default, aliases are allowed, but they are tracked in the type system. When data races are a concern, the tracked aliases are controlled to prevent data-race-prone patterns. We study the formal properties of System CSC. Type soundness is proven via the standard progress and preservation theorems. Additionally, we formally verify the data race freedom property of System CSC by proving that the reduction of a well-typed program is confluent.

BibTeX:

@article{xu_degrees_2024,
    title = {{Degrees of Separation: A Flexible Type System for Safe Concurrency}},
    author = {Xu, Yichen and Boruch-Gruszecki, Aleksander and Odersky, Martin},
    year = {2024},
    journal = {{Proc. ACM Program. Lang.}},
    number = {OOPSLA1},
    doi = {10.1145/3649853},
    pages = {136:1181--136:1207},
    url = {https://dl.acm.org/doi/10.1145/3649853},
    volume = {8},
    shorttitle = {Degrees of Separation},
}

Journal article