Lune

POPL2022Top-tier venue

Connectivity graphs: a method for proving deadlock freedom based on separation logic

Jules Jacobs, Stephanie Balzer, Robbert Krebbers

Abstract

We introduce the notion of a connectivity graph-an abstract representation of the topology of concurrently interacting entities, which allows us to encapsulate generic principles of reasoning about deadlock freedom. Connectivity graphs are parametric in their vertices (representing entities like threads and channels) and their edges (representing references between entities) with labels (representing interaction protocols). We prove deadlock and memory leak freedom in the style of progress and preservation and use separation logic as a meta theoretic tool to treat connectivity graph edges and labels substructurally. To prove preservation locally, we distill generic separation logic rules for local graph transformations that preserve acyclicity of the connectivity graph. To prove global progress locally, we introduce a waiting induction principle for acyclic connectivity graphs. We mechanize our results in Coq, and instantiate our method with a higher-order binary session-typed language to obtain the first mechanized proof of deadlock and leak freedom.

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.

7 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Higher-Order Leak and Deadlock Free Locks cites Zooid: a DSL for certified multiparty computation: from mechanised metatheory to certified multiparty processes
  • Zooid: a DSL for certified multiparty computation: from mechanised metatheory to certified multiparty processes cites Actris: session-type based reasoning in separation logic
  • Deadlock-Free Separation Logic: Linearity Yields Progress for Dependent Higher-Order Message Passing cites Zooid: a DSL for certified multiparty computation: from mechanised metatheory to certified multiparty processes
  • Deadlock-Free Separation Logic: Linearity Yields Progress for Dependent Higher-Order Message Passing cites Actris: session-type based reasoning in separation logic
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers7

  1. Deadlock-Free Separation Logic: Linearity Yields Progress for Dependent Higher-Order Message PassingJules Jacobs, Jonas Kastberg Hinrichsen, Robbert KrebbersPOPL 2024 · 12 citations
  2. Mechanizing Session-Types using a Structural View: Enforcing Linearity without LinearityChuta Sano, Ryan Kavanagh, Brigitte PientkaOOPSLA 2023 · 10 citations
  3. Higher-Order Leak and Deadlock Free LocksJules Jacobs, Stephanie BalzerPOPL 2023 · 5 citations
  4. Using Dynamically Layered Definite Releases for Verifying the RefFS File SystemMo Zou, Dong Du, Mingkai Dong, Haibo ChenOSDI 2024 · 4 citations
  5. Borrowing from Session TypesHannes Saffrich, Janek Spaderna, Peter Thiemann, Vasco T. VasconcelosOOPSLA 2025

Builds on4

  1. Actris: session-type based reasoning in separation logicJonas Kastberg Hinrichsen, Jesper Bengtson, Robbert KrebbersPOPL 2020 · 44 citations
  2. Zooid: a DSL for certified multiparty computation: from mechanised metatheory to certified multiparty processesDavid Castro-Perez, Francisco Ferreira, Lorenzo Gheri, Nobuko YoshidaPLDI 2021 · 25 citations
  3. Session Logical Relations for NoninterferenceFarzaneh Derakhshan, Stephanie Balzer, Limin JiaLICS 2021 · 6 citations
  4. Intrinsically typed compilation with nameless labelsArjen Rouvoet, Robbert Krebbers, Eelco VisserPOPL 2021 · 5 citations

Related papers

  1. Verified Lock-Free Session Channels with LinkingThomas Somers, Robbert KrebbersOOPSLA 2024 · 2 citations
  2. A concurrent program logic with a future and historyRoland Meyer, Thomas Wies, Sebastian WolffOOPSLA 2022 · 9 citations
  3. Concurrent incorrectness separation logicAzalea Raad, Josh Berdine, Derek Dreyer, Peter W. O'HearnPOPL 2022 · 24 citations
  4. Raven: An SMT-Based Concurrency VerifierEkanshdeep Gupta, Nisarg Patel, Thomas WiesCAV 2025 · 1 citation
  5. Multris: Functional Verification of Multiparty Message Passing in Separation LogicJonas Kastberg Hinrichsen, Jules Jacobs, Robbert KrebbersOOPSLA 2024 · 6 citations
Dusk over the sea between two cliffs drawn in fine vertical lines