Trillium: Higher-Order Concurrent and Distributed Separation Logic for Intensional Refinement
Authors:
- Amin TimanyATAmin Timany
- Simon Oddershede GregersenSGSimon Oddershede Gregersen
- Léo StefanescoLSLéo Stefanesco
- Jonas Kastberg HinrichsenJHJonas Kastberg Hinrichsen
- Léon GondelmanLGLéon Gondelman
- Abel NietoANAbel Nieto
- Lars BirkedalLBLars Birkedal
Preprint
Abstract
Expressive state-of-the-art separation logics rely on step-indexing to model semantically complex features and to support modular reasoning about imperative higher-order concurrent and distributed programs. Step-indexing comes, however, with an inherent cost: it restricts the adequacy theorem of program logics to a fairly simple class of safety properties. In this paper, we explore if and how intensional refinement is a viable methodology for strengthening higher-order concurrent (and distributed) separation logic to prove non-trivial safety and liveness properties. Specifically, we introduce Trillium, a language-agnostic separation logic framework for showing intensional refinement relations between traces of a program and a model. We instantiate Trillium with a concurrent language and develop Fairis, a concurrent separation logic, that we use to show liveness properties of concurrent programs under fair scheduling assumptions through a fair liveness-preserving refinement of a model. We also instantiate Trillium with a distributed language and obtain an extension of Aneris, a distributed separation logic, which we use to show refinement relations between distributed systems and TLA+ models.Keywords
All Related Versions
This publication has 33 references indexed in Scilit:
- Aneris: A Mechanised Logic for Modular Reasoning about Distributed Systems2020
- Iris from the ground up: A modular foundation for higher-order concurrent separation logicJournal of Functional Programming, 2018
- Paxos Consensus, Deconstructed and Abstracted2018
- Cutoff Bounds for Consensus Algorithms2017
- A Higher-Order Logic for Concurrent Termination-Preserving Refinement2017
- Formal Verification of Multi-Paxos for Distributed Consensus2016
- Sound, Modular and Compositional Verification of the Input/Output Behavior of Programs2015
- Eventually consistentCommunications of the ACM, 2009
- Equivalence and Preorder Checking for Finite-State Systems2001
- Notes on data base operating systems1978