C4: Verified Transactional Objects

Mohsen Lesani, Li-yao Xia, Anders Kaseorg, Christian J. Bell, Adam Chlipala, Benjamin C. Pierce, Steve Zdancewic. C4: Verified Transactional Objects. Proceedings of the 2022 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, & Applications (OOPSLA'22). November 2022.

Paper as PDF

Transactional objects combine the performance of classical concurrent objects with the high-level programmability of transactional memory. But verifying the correctness of transactional objects is tricky, requiring reasoning simultaneously about classical concurrent objects, which guarantee the atomicity of individual methods -- the property known as linearizability -- and about software-transactional-memory libraries, which guarantee the atomicity of user-defined sequences of method calls -- or serializability.

We present a formal verification framework, built up from the familiar notion of linearizability and its compositional properties, that allows proof of both kinds of libraries, along with composition of theorems from both styles to prove correctness of applications or further libraries. We apply the framework in a significant case study, verifying a transactional set object built out of both classical and transactional components following the technique of transactional predication; the proof is modular, reasoning separately about the transactional and non-transactional parts of the implementation. Central to our approach is the use of syntactic transformers on interaction trees -- e.g., transactional libraries that transform client code to enforce a particular synchronization discipline. Our framework and case studies are mechanized in Coq.