A Verified Parallel Scheduler for OCaml 5
Clément Allain, Gabriel Scherer
Abstract
We present the implementation and mechanized verification of a realistic parallel scheduler for OCaml 5 using the Iris-based Zoo framework. Similarly to Domainslib , it relies on a work-stealing strategy to perform load balancing but also supports other scheduling strategies thanks to its flexible interface. We provide basic benchmarks demonstrating that its performance is on par with other schedulers from the OCaml ecosystem. As part of this effort, we verify the Chase-Lev work-stealing deque, as implemented in the Saturn library. We show that it features a subtle external and future-dependent linearization point. To deal with it, we introduce new abstractions for reasoning about prophecy variables in Iris.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on6
- The future is ours: prophecy variables in separation logicRalf Jung, Rodolphe Lepigre, Gaurav Parthasarathy, Marianna Rapoport et al.POPL 2020 · 62 citations
- Retrofitting effect handlers onto OCamlK. C. Sivaramakrishnan, Stephen Dolan, Leo White, Tom Kelly et al.PLDI 2021 · 56 citations
- A separation logic for effect handlersPaulo Emílio de Vilhena, François PottierPOPL 2021 · 24 citations
- Modular Verification of Safe Memory Reclamation in Concurrent Separation LogicJaehwang Jung, Janggun Lee, Jaemin Choi, Jaewoo Kim et al.OOPSLA 2023 · 10 citations
- PulseCore: An Impredicative Concurrent Separation Logic for Dependently Typed ProgramsGabriel Ebner, Guido Martínez, Aseem Rastogi, Thibault Dardinier et al.PLDI 2025 · 8 citations
Related papers
- Zoo: A Framework for the Verification of Concurrent OCaml 5 Programs using Separation LogicClément Allain, Gabriel SchererPOPL 2026 · 2 citations
- A Relational Separation Logic for Effect HandlersPaulo Emílio de Vilhena, Simcha van Collem, Ines Wright, Robbert KrebbersPOPL 2026 · 3 citations
- Raven: An SMT-Based Concurrency VerifierEkanshdeep Gupta, Nisarg Patel, Thomas WiesCAV 2025 · 1 citation
- Spy game: verifying a local generic solver in IrisPaulo Emílio de Vilhena, François Pottier, Jacques-Henri JourdanPOPL 2020 · 15 citations
- Leaf: Modularity for Temporary Sharing in Separation LogicTravis Hance, Jon Howell, Oded Padon, Bryan ParnoOOPSLA 2023 · 3 citations
