All for One and One for All: Program Logics for Exploiting Internal Determinism in Parallel Programs
Open Access
- 8 January 2026
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (POPL) , 748-776
Abstract
Nondeterminism makes parallel programs challenging to write and reason about. To avoid these challenges, researchers have developed techniques for internally deterministic parallel programming, in which the steps of a parallel computation proceed in a deterministic way. Internal determinism is useful because it lets a programmer reason about a program as if it executed in a sequential order. However, no verification framework exists to exploit this property and simplify formal reasoning about internally deterministic programs. To capture the essence of why internally deterministic programs should be easier to reason about, this paper defines a property called schedule-independent safety. A program satisfies schedule-independent safety, if, to show that the program is safe across all orderings, it suffices to show that one terminating execution of the program is safe. We then present a separation logic called Musketeer for proving that a program satisfies schedule-independent safety. Once a parallel program has been shown to satisfy schedule-independent safety, we can verify it with a new logic called Angelic, which allows one to dynamically select and verify just one sequential ordering of the program. Using Musketeer, we prove the soundness of MiniDet, an affine type system for enforcing internal determinism. MiniDet supports several core algorithmic primitives for internally deterministic programming that have been identified in the research literature, including a deterministic version of a concurrent hash set. Because any syntactically well-typed MiniDet program satisfies schedule-independent safety, we can apply Angelic to verify such programs. All results in this paper have been verified in Rocq using the Iris separation logic framework.Keywords
All Related Versions
Funding Information
- National Science Foundation (2318722)
- National Science Foundation (2319168)
This publication has 42 references indexed in Scilit:
- Thirty-Seven Years of Relational Hoare Logic: Remarks on Its Principles and History2020
- Iris from the ground up: A modular foundation for higher-order concurrent separation logicJournal of Functional Programming, 2018
- A program logic for concurrent objects under fair schedulingACM SIGPLAN Notices, 2016
- LVars2013
- Internally deterministic parallel algorithms can be fast2012
- Permission accounting in separation logic2005
- Single Assignment C: efficient support for high-level array operations in a functional settingJournal of Functional Programming, 2003
- State in HaskellHigher-Order and Symbolic Computation, 1995
- Implementation of a Portable Nested Data-Parallel LanguageJournal of Parallel and Distributed Computing, 1994
- ReductionCommunications of the ACM, 1975