Trillium: Unifying Refinement and Higher-Order Distributed Separation Logic

Authors:
  • ATAmin Timany
    Amin Timany
  • SGSimon Oddershede Gregersen
    Simon Oddershede Gregersen
  • LSLéo Stefanesco
    Léo Stefanesco
  • LGLéon Gondelman
    Léon Gondelman
  • ANAbel Nieto
    Abel Nieto
  • LBLars Birkedal
    Lars Birkedal

Abstract
We present a unification of refinement and Hoare-style reasoning in a foundational mechanized higher-order distributed separation logic. This unification enables us to prove formally in the Coq proof assistant that concrete implementations of challenging distributed systems refine more abstract models and to combine refinement-style reasoning with Hoare-style program verification. We use our logic to prove correctness of concrete implementations of two-phase commit and single-decree Paxos by showing that they refine their abstract TLA+ specifications. We further use our notion of refinement to transfer fairness assumptions on program executions to model traces and then transfer liveness properties of fair model traces back to program executions, which enables us to prove liveness properties such as strong eventual consistency of a concrete implementation of a Conflict-Free Replicated Data Type and fair termination of a concurrent program.