Induction duality: primal-dual search for invariants
Oded Padon, James R. Wilcox, Jason R. Koenig, Kenneth L. McMillan, Alex Aiken
Abstract
Many invariant inference techniques reason simultaneously about states and predicates, and it is well-known that these two kinds of reasoning are in some sense dual to each other. We present a new formal duality between states and predicates, and use it to derive a new primal-dual invariant inference algorithm. The new induction duality is based on a notion of provability by incremental induction that is formally dual to reachability, and the duality is surprisingly symmetric. The symmetry allows us to derive the dual of the well-known Houdini algorithm, and by combining Houdini with its dual image we obtain primal-dual Houdini , the first truly primal-dual invariant inference algorithm. An early prototype of primal-dual Houdini for the domain of distributed protocol verification can handle difficult benchmarks from the literature.
Ask Lune
Know where this paper stands in minutes, not an afternoon.
Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.
13 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
its abstract · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Anvil: Verifying Liveness of Cluster Management Controllers cites DuoAI: Fast, Automated Inference of Inductive Invariants for Verifying Distributed Protocols
- Anvil: Verifying Liveness of Cluster Management Controllers cites Mostly Automated Verification of Liveness Properties for Distributed Protocols with Ranking Functions
- Mostly Automated Verification of Liveness Properties for Distributed Protocols with Ranking Functions cites DuoAI: Fast, Automated Inference of Inductive Invariants for Verifying Distributed Protocols
Cited by top-tier papers13
- Anvil: Verifying Liveness of Cluster Management ControllersXudong Sun, Wenjie Ma, Jiawei Tyler Gu, Zicheng Ma et al.OSDI 2024 · 50 citations
- DuoAI: Fast, Automated Inference of Inductive Invariants for Verifying Distributed ProtocolsJianan Yao, Runzhou Tao, Ronghui Gu, Jason NiehOSDI 2022 · 50 citations
- Modular Primal-Dual Fixpoint Logic Solving for Temporal VerificationHiroshi Unno, Tachio Terauchi, Yu Gu, Eric KoskinenPOPL 2023 · 23 citations
- Mostly Automated Verification of Liveness Properties for Distributed Protocols with Ranking FunctionsJianan Yao, Runzhou Tao, Ronghui Gu, Jason NiehPOPL 2024 · 12 citations
- Affine Loop Invariant Generation via Matrix AlgebraYucheng Ji, Hongfei Fu, Bin Fang, Haibo ChenCAV 2022 · 10 citations
Related papers
- A Primal-Dual Perspective on Program Verification AlgorithmsTakeshi Tsukada, Hiroshi Unno, Oded Padon, Sharon ShohamPOPL 2025 · 2 citations
- Basilisk: Using Provenance Invariants to Automate Proofs of Undecidable ProtocolsTony Nuda Zhang, Keshav Singh, Tej Chajed, Manos Kapritsos et al.OSDI 2025 · 9 citations
- QSM-Cutoff: Systematic Derivation of Quantified Cutoff Formulas for Distributed ProtocolsYun-Rong Luo, Aman Goel, Karem A. SakallahCAV 2025
- DistAI: Data-Driven Automated Invariant Learning for Distributed ProtocolsJianan Yao, Runzhou Tao, Ronghui Gu, Jason Nieh et al.OSDI 2021 · 76 citations
- H-Houdini: Scalable Invariant LearningSushant Dinesh, Yongye Zhu, Christopher W. FletcherASPLOS 2025 · 7 citations
