ECOOP 2026
Mon 29 June - Fri 3 July 2026 Brussels, Belgium
Wed 1 Jul 2026 11:22 - 11:45 at I.2.03 - Concurrency Chair(s): António Ravara

Compositionality is essential for managing complexity in verification of concurrent programs, especially when proof certificates are needed. An effective verification scheme is to divide programs into abstraction layers and verify by composing refinements between layers. However, vanilla verified layers come with \emph{global states} which severely limit their extensibility. This problem may be solved by dividing a layer into objects with \emph{encapsulated local states}. Although the idea has been successfully realized in the sequential setting, it remains unclear if it also works in a concurrent setting where function calls across layers are no longer atomic steps and foundational proofs are needed.

We propose an approach to foundational and compositional verification of concurrent objects organized into multiple layers. The central idea is to represent concurrent objects as \emph{open} labeled transition systems with \emph{encapsulated threads} and to adopt \emph{trace refinements} as a uniform notion of functional correctness which supports both \emph{vertical composition} (layered refinement) and \emph{horizontal composition} (extension of layer interfaces). Due to the operational nature of transition systems, it is straightforward to adopt traditional simulation techniques to produce foundational proof certificates. We implement this framework in the Rocq theorem prover and demonstrate its capability in foundational and compositional verification by verifying non-trivial lock-free concurrent data structures.

Wed 1 Jul

Displayed time zone: Brussels, Copenhagen, Madrid, Paris change

11:00 - 12:30
ConcurrencyTechnical Papers at I.2.03
Chair(s): António Ravara Nova University of Lisbon
11:00
22m
Talk
A Complete Program Logic for Compositional LinearizabilityDistinguished paper award
Technical Papers
Eashan Hatti Yale University, Arthur Oliveira Vale Yale University, Zhongye Wang Yale University, Yueyang Feng Yale University, Zhong Shao Yale University
11:22
22m
Talk
Foundational and Compositional Verification of Layered Concurrent Objects
Technical Papers
Yicheng Ni , Yuting Wang Shanghai Jiao Tong University
11:45
22m
Talk
Verifying wait-freedom for concurrent higher-order programs
Technical Papers
Egor Namakonov , Lars Birkedal Aarhus University, Amin Timany Aarhus University
12:07
22m
Talk
Vardalith: Hybrid Detection of Persistent Memory Concurrency Bugs
Technical Papers
João Gonçalves IST U. Lisboa & INESC-ID, Miguel Matos IST, INESC-ID, U. Lisboa, Rodrigo Rodrigues Instituto Superior Técnico, U. Lisboa & INESC-ID, José Fragoso Santos INESC-ID; Instituto Superior Técnico - University of Lisbon