💻 computer science

Interactive Safety Verification of Distributed Protocols by Inductive Proof Decomposition

This paper introduces "inductive proof decomposition," an interactive methodology that guides human verifiers in constructing safety proofs for complex distributed protocols by incrementally building an inductive proof graph, localizing counterexamples, and slicing irrelevant state to overcome the limitations of fully automated verification tools.

Original authors: William Schultz, Edward Ashton, Heidi Howard, Stavros Tripakis

Published 2026-04-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: William Schultz, Edward Ashton, Heidi Howard, Stavros Tripakis

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to prove that a massive, complex machine (like a distributed computer network or a cloud database) will never crash or make a mistake. In the world of computer science, this is called safety verification.

For years, experts have tried to build "robots" (automated tools) to do this proof for them. But these robots are like brilliant but stubborn students: they can solve simple math problems instantly, but when faced with a giant, messy real-world problem, they either get stuck, take forever, or just give up without telling you why. They are "all or nothing."

This paper introduces a new way to work: Inductive Proof Decomposition. Instead of asking a robot to solve the whole puzzle at once, it gives a human expert a new set of tools to break the giant puzzle into tiny, manageable pieces, working with the computer rather than just waiting for it.

Here is the breakdown using simple analogies:

1. The Problem: The "Monolithic" Wall

Traditionally, proving a system is safe is like trying to climb a 100-foot wall in one giant leap. You have to find a single, perfect "safety net" (called an inductive invariant) that catches every possible mistake the machine could make.

The Issue: If the wall is too high, the automated robot can't jump it. If a human tries to build the net from scratch, it becomes a tangled mess of thousands of rules. It's hard to see where the holes are, and hard to fix them without breaking something else.

2. The Solution: The "Proof Graph" (A Map of Dependencies)

The authors created a new structure called an Inductive Proof Graph.

The Analogy: Imagine you are building a house. Instead of trying to build the whole roof at once, you draw a blueprint that shows exactly which beam supports which other beam.
How it works: The graph breaks the giant "safety net" into small, logical steps (nodes). Each node represents a specific rule or action the computer takes. The lines connecting them show which rules depend on which others.
The Benefit: Instead of looking at the whole 100-foot wall, you only look at one small brick at a time. If a brick is shaky, you only need to fix that specific spot, not the whole wall.

3. The "Local Slicing" (The X-Ray Goggles)

When the computer finds a potential mistake (a counterexample), it usually shows you a massive amount of data—like showing you the entire history of the universe to explain why you dropped your coffee cup.

The Analogy: The authors developed a technique called Variable Slicing. Think of this as putting on X-Ray goggles or a spotlight.
How it works: When analyzing a specific part of the graph, the tool automatically hides everything irrelevant. If you are checking the "Door Lock" mechanism, the tool hides the "Kitchen Light" and "Car Engine" data. It only shows you the variables relevant to the door.
The Benefit: This reduces a mountain of confusing data to a single, clear pebble. It stops the human from getting overwhelmed.

4. The Workflow: Working Backwards

The process is interactive and works backwards from the goal.

Start at the Goal: You start with the safety rule you want to prove (e.g., "No two people can decide on different values").
Find the Crack: The computer tries to break this rule and shows you a "Counterexample" (a scenario where it fails).
Zoom In: Thanks to the graph and the X-Ray goggles, you see exactly where the failure happened (e.g., "The door lock failed because the key wasn't turned").
Add a Lemma: You add a small, new rule (a "lemma") to fix that specific crack.
Repeat: You move to the next crack. Because you are fixing small pieces, the graph grows organically until the whole structure is solid.

5. The Real-World Test: The Raft Protocol

The authors tested this on Raft, a famous and complex protocol used to keep databases in sync across the world.

The Result: Automated tools had failed to prove Raft's safety on their own. Using this new "decomposition" method, a human expert, guided by the tool, built the proof in about 3 weeks.
The Insight: The resulting "Proof Graph" didn't just prove the system was safe; it actually taught the engineers how the system works. It revealed hidden patterns and cycles in the logic that they hadn't noticed before. It was like solving a mystery and finding a map of the criminal's mind in the process.

Summary

Think of this paper as a new construction method for skyscrapers.

Old Way: Try to lift the whole building into place with a crane (Automated tools). If the crane is too weak, the building falls.
New Way: Use a scaffold (The Proof Graph) to build the building floor by floor. Use a laser level (Variable Slicing) to ensure each brick is perfectly aligned without worrying about the bricks on the 50th floor.

This approach bridges the gap between human intuition and machine power, making it possible to verify the safety of the massive, critical systems that run our modern world.

1. Problem Statement

Verifying the safety of large-scale distributed and concurrent systems is a critical but difficult challenge. The standard approach involves developing an inductive invariant—a state predicate that holds true in all initial states and is preserved by all system transitions.

Limitations of Automation: While automated tools (e.g., IC3/PDR, syntax-guided synthesis) have made progress, they often fail unpredictably on complex, industrial-scale protocols. Their failure modes are opaque, offering little guidance on how to construct a manual proof.
Limitations of Current Interactive Methods: Existing interactive frameworks (like Ivy) or theorem provers (like Coq/Isabelle) often require users to manage a monolithic list of lemmas linearly. As invariants grow to include dozens of complex conjuncts, analyzing counterexamples becomes increasingly difficult. Users struggle with:
1. Management: Deciding which counterexample to analyze next.
2. Localization: Focusing only on relevant lemmas, actions, and variables for a specific counterexample.
3. Structure: Tracking the progress and logical dependencies of the proof as it evolves.

2. Methodology: Inductive Proof Decomposition

The authors propose Inductive Proof Decomposition, a methodology that shifts from a linear, monolithic approach to a compositional, graph-based approach. The core innovation is the Inductive Proof Graph.

A. The Inductive Proof Graph

This is a directed graph $(V, E)$ that explicitly models the logical dependencies between lemmas and protocol actions.

Nodes:
- Lemma Nodes ( $V_L$ ): Represent state predicates (lemmas) that form the inductive invariant.
- Action Nodes ( $V_A$ ): Represent specific logical actions ( $A_1, \dots, A_n$ ) in the protocol's transition relation. Each action node is associated with a specific lemma.
Edges: Represent support relationships. An edge exists from a lemma $L_{support}$ to an action node $(L_{target}, A)$ if $L_{support}$ is required to prove that $L_{target}$ is inductive relative to action $A$ .
Construction: The graph is built incrementally by a human verifier working backwards from the target safety property.
1. Start with the safety property as the root.
2. Identify unproven nodes (those with outstanding Counterexamples to Induction, or CTIs).
3. Analyze a specific CTI at a specific action node.
4. Develop a new lemma to rule out that CTI.
5. Add the new lemma and support edges to the graph.
6. Repeat until all nodes are "discharged" (locally valid).

B. Local Variable Slicing

A key feature of the graph structure is the ability to apply local variable slicing.

Concept: When analyzing a CTI for a specific action node $(L, A)$ , the verifier does not need to consider the entire system state.
Mechanism: The system computes a "slice" of variables relevant to that node:
1. Variables in the precondition of action $A$ .
2. Variables in the definition of lemma $L$ .
3. Variables upon which the update expressions of $L$ depend (Cone of Influence).
Benefit: This projects out irrelevant protocol state, significantly reducing the complexity of the counterexample presented to the human user.

C. Interactive Workflow

The process is guided by a backend solver (using model checkers like TLC or Apalache) that generates CTIs. The human user:

Selects an unproven action node.
Views the localized CTI (filtered by the variable slice).
Synthesizes a new lemma to eliminate the CTI.
Updates the graph, potentially discharging the current node and revealing new sub-problems.

3. Key Contributions

Formalization of Inductive Proof Graphs: A new formal structure representing the logical dependencies between invariant conjuncts and protocol actions, enabling localized reasoning.
Inductive Proof Decomposition Methodology: A compositional approach to interactive verification that guides human effort through incremental graph construction, addressing the "all-or-nothing" failure of automated tools.
Novel Variable Slicing Technique: A static analysis method that projects irrelevant state variables at each proof node, making counterexample analysis tractable for complex systems.
Implementation (Scimitar): An interactive tool implementing this methodology, accepting TLA+ specifications and providing a GUI for graph visualization and CTI analysis.

4. Results and Evaluation

The authors evaluated the technique using the Scimitar tool on five distributed protocols, ranging from medium complexity to industrial scale.

Protocols Tested:
- SimpleConsensus: A basic leader-based consensus protocol.
- TwoPhase: Two-phase commit protocol.
- AbstractRaft: High-level Raft specification (abstracting message passing).
- Bakery: Lamport's Bakery algorithm for mutual exclusion.
- AsyncRaft: A large-scale, industrial-level specification of the Raft consensus protocol, including asynchronous message passing and fine-grained local state.
Key Findings:
- Feasibility: The team successfully developed an inductive invariant for AsyncRaft (a specification previously beyond the capabilities of modern automated tools) in approximately 3 human-weeks.
- Efficiency: Compared to other industrial verification efforts (which often take 1-2 months for smaller invariants), the decomposition approach significantly accelerated the process.
- Localization: The variable slices were highly effective. For example, in SimpleConsensus, slices reduced the state variables by 67% (median slice proportion 0.33). In AsyncRaft, slices allowed reasoning over disjoint subsets of the 12 total variables.
- Insight: The resulting proof graphs provided new insights into protocol structure, such as identifying induction cycles related to message passing (e.g., between LogMatching and LogMatchingInAppendEntriesMsgs) that are difficult to see in monolithic invariants.

5. Significance

This paper addresses a critical gap in formal verification: the scalability of human-guided proof construction for complex distributed systems.

Bridging the Gap: It moves beyond the binary "tool succeeds/fails" paradigm of automated verification and the steep learning curve of traditional theorem proving.
Scalability: By decomposing the problem into localized sub-problems via the proof graph and variable slicing, it makes verifying industrial-scale protocols (like Raft) feasible for human engineers.
Interpretability: The proof graph serves as a documentation artifact that explicitly visualizes the logical structure and dependencies of the proof, aiding in understanding and maintenance.

In summary, the authors demonstrate that Inductive Proof Decomposition transforms the verification of complex distributed protocols from an opaque, monolithic struggle into a structured, manageable, and interactive process.