Lune

OSDI2022Top-tier venue

DuoAI: Fast, Automated Inference of Inductive Invariants for Verifying Distributed Protocols

Jianan Yao, Runzhou Tao, Ronghui Gu, Jason Nieh

Abstract

Distributed systems are complex and difficult to build correctly. Formal verification can provably rule out bugs in such systems, but finding an inductive invariant that implies the safety property of the system is often the hardest part of the proof. We present DuoAI, an automated system that quickly finds inductive invariants for verifying distributed protocols by reducing SMT query costs in checking invariants with existential quantifiers. DuoAI enumerates the strongest candidate invariants that hold on validate states from protocol simulations, then applies two methods in parallel, returning the result from the method that succeeds first. One checks all candidate invariants and weakens them as needed until it finds an inductive invariant that implies the safety property. Another checks invariants without existential quantifiers to find an inductive invariant without the safety property, then adds candidate invariants with existential quantifiers to strengthen it until the safety property holds. Both methods are guaranteed to find an inductive invariant that proves desired safety properties, if one exists, but the first reduces SMT query costs when more candidate invariants with existential quantifiers are needed, while the second reduces SMT query costs when few candidate invariants with existential quantifiers suffice. We show that DuoAI verifies more than two dozen common distributed protocols automatically, including various versions of Paxos, and outperforms alternative methods both in the number of protocols it verifies and the speed at which it does so, including solving Paxos more than two orders of magnitude faster than previous methods.

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.

25 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

  • Halfmoon: Log-Optimal Fault-Tolerant Stateful Serverless Computing cites DistAI: Data-Driven Automated Invariant Learning for Distributed Protocols
  • Anvil: Verifying Liveness of Cluster Management Controllers cites Finding Invariants of Distributed Systems: It's a Small (Enough) World After All
  • Anvil: Verifying Liveness of Cluster Management Controllers cites DistAI: Data-Driven Automated Invariant Learning for Distributed Protocols
  • Anvil: Verifying Liveness of Cluster Management Controllers cites Mostly Automated Verification of Liveness Properties for Distributed Protocols with Ranking Functions
  • Verus: A Practical Foundation for Systems Verification cites Finding Invariants of Distributed Systems: It's a Small (Enough) World After All
  • Verus: A Practical Foundation for Systems Verification cites DistAI: Data-Driven Automated Invariant Learning for Distributed Protocols
  • Finding Invariants of Distributed Systems: It's a Small (Enough) World After All cites First-order quantified separators
  • Compiling Distributed System Models with PGo cites Finding Invariants of Distributed Systems: It's a Small (Enough) World After All
  • Compiling Distributed System Models with PGo cites DistAI: Data-Driven Automated Invariant Learning for Distributed Protocols
  • DistAI: Data-Driven Automated Invariant Learning for Distributed Protocols cites CLN2INV: Learning Loop Invariants with Continuous Logic Networks
  • DistAI: Data-Driven Automated Invariant Learning for Distributed Protocols cites Data-driven inference of representation invariants
  • DistAI: Data-Driven Automated Invariant Learning for Distributed Protocols cites Finding Invariants of Distributed Systems: It's a Small (Enough) World After All
  • DistAI: Data-Driven Automated Invariant Learning for Distributed Protocols cites First-order quantified separators
  • Mostly Automated Verification of Liveness Properties for Distributed Protocols with Ranking Functions cites Finding Invariants of Distributed Systems: It's a Small (Enough) World After All
  • Mostly Automated Verification of Liveness Properties for Distributed Protocols with Ranking Functions cites First-order quantified separators
  • Mostly Automated Verification of Liveness Properties for Distributed Protocols with Ranking Functions cites DistAI: Data-Driven Automated Invariant Learning for Distributed Protocols
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers25

  1. Anvil: Verifying Liveness of Cluster Management ControllersXudong Sun, Wenjie Ma, Jiawei Tyler Gu, Zicheng Ma et al.OSDI 2024 · 50 citations
  2. Verus: A Practical Foundation for Systems VerificationAndrea Lattuada, Travis Hance, Jay Bosamiya, Matthias Brun et al.SOSP 2024 · 22 citations
  3. Halfmoon: Log-Optimal Fault-Tolerant Stateful Serverless ComputingSheng Qi, Xuanzhe Liu, Xin JinSOSP 2023 · 16 citations
  4. Compiling Distributed System Models with PGoA. Finn Hackett, Shayan Hosseini, Renato Costa, Matthew Do et al.ASPLOS 2023 · 13 citations
  5. Mostly Automated Verification of Liveness Properties for Distributed Protocols with Ranking FunctionsJianan Yao, Runzhou Tao, Ronghui Gu, Jason NiehPOPL 2024 · 12 citations

Builds on9

  1. DistAI: Data-Driven Automated Invariant Learning for Distributed ProtocolsJianan Yao, Runzhou Tao, Ronghui Gu, Jason Nieh et al.OSDI 2021 · 76 citations
  2. CLN2INV: Learning Loop Invariants with Continuous Logic NetworksGabriel Ryan, Justin Wong, Jianan Yao, Ronghui Gu et al.ICLR 2020 · 72 citations
  3. Finding Invariants of Distributed Systems: It's a Small (Enough) World After AllTravis Hance, Marijn Heule, Ruben Martins, Bryan ParnoNSDI 2021 · 69 citations
  4. Data-driven inference of representation invariantsAnders Miltner, Saswat Padhi, Todd D. Millstein, David WalkerPLDI 2020 · 33 citations
  5. First-order quantified separatorsJason R. Koenig, Oded Padon, Neil Immerman, Alex AikenPLDI 2020 · 31 citations

Related papers

  1. Basilisk: Using Provenance Invariants to Automate Proofs of Undecidable ProtocolsTony Nuda Zhang, Keshav Singh, Tej Chajed, Manos Kapritsos et al.OSDI 2025 · 9 citations
  2. Simplifying Safety Proofs with Forward-Backward Reasoning and ProphecyEden Frenkel, Kenneth L. McMillan, Oded Padon, Sharon ShohamPLDI 2026
  3. Induction duality: primal-dual search for invariantsOded Padon, James R. Wilcox, Jason R. Koenig, Kenneth L. McMillan et al.POPL 2022 · 14 citations
  4. I3DP: Neuro-Symbolic Inductive Invariant Inference for Distributed ProtocolsWeining Cao, Guangyuan Wu, Yuan Yao, Hengfeng Wei et al.SOSP 2026
  5. Counterexample Driven Quantifier Instantiations with Applications to Distributed ProtocolsOrr Tamir, Marcelo Taube, Kenneth L. McMillan, Sharon Shoham et al.OOPSLA 2023 · 5 citations
Dusk over the sea between two cliffs drawn in fine vertical lines