💻 computer science

DissProve: Automated Verification of Distributed Protocols with Affine Communication

This paper introduces DissProve, an automated verification tool that proves safety properties for asynchronous, parametric distributed protocols with affine communication by employing goal-directed techniques like materialization, causality, and summarization to handle unbounded execution histories within bounded communication rounds.

Original authors: Christian Fontenot, Gowtham Kaki, Bor-Yuh Evan Chang

Published 2026-06-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Christian Fontenot, Gowtham Kaki, Bor-Yuh Evan Chang

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 a massive, chaotic dance floor where thousands of dancers (called "actors") are trying to coordinate a complex routine without ever speaking at the same time. They send notes to each other, but the notes can get lost, delayed, or arrive in a jumbled order. The goal is to prove that no matter how many dancers join the floor or how long they dance, they will never accidentally agree on two different leaders at the same time. This is the problem of verifying distributed protocols.

For decades, proving this automatically has been like trying to count every possible way the dancers could move in a room that keeps getting bigger. It's too complex for computers to solve on their own.

This paper introduces a new tool called DissProve that acts like a super-smart detective. Instead of watching the dance from the beginning and trying to predict every possible future (which is impossible), the detective starts at the disaster (e.g., "Two people are claiming to be the leader") and works backwards to see if that disaster could ever actually happen.

Here is how the paper's magic tricks work, explained simply:

1. The "Affine" Rule (The One-Time Ticket)

The paper focuses on a specific type of dance routine called "Affine Communication."

The Metaphor: Imagine that in this specific dance, every dancer is only allowed to hand out one specific type of note to any other specific dancer. You can't hand out five "Vote for Me" notes to the same person; you get one shot, and that's it.
Why it matters: This rule keeps the chaos manageable. Even if there are infinite dancers, the number of types of interactions in one round is limited. It's like a game where you can only pass a ball once per round. This restriction is the key that allows the computer to solve the puzzle.

2. Working Backwards from the "Crime Scene"

Traditional methods try to build a wall of logic from the start of the program to the end. DissProve does the opposite.

The Metaphor: Imagine a detective arriving at a crime scene where two people claim to be the King. Instead of asking, "How did we get here?" the detective asks, "What specific actions must have happened to cause this?"
The Process: The tool starts with the error (two leaders) and traces the path backward. It asks: "For these two people to be leaders, they must have received enough votes. Who sent those votes? What did those senders need to do before sending?" It keeps peeling back the onion until it either finds a logical contradiction (proving the crime is impossible) or finds a real path to the disaster.

3. "Materialization": Bringing Actors into Focus

When working backward, the computer faces a problem: there are infinite dancers, but it can't think about all of them at once.

The Metaphor: Imagine the detective has a blurry photo of a crowd. Instead of trying to analyze every blurry face, the detective uses a magnifying glass to pull only the specific people involved in the crime into sharp focus.
The Technique: The tool "materializes" (makes real) only the specific actors needed to explain the error. If the error involves Actor A and Actor B, the tool focuses on them and treats everyone else as a vague, unimportant background blur. This prevents the computer from getting overwhelmed.

4. "Causal Reduction": Ignoring the Noise

Even with a magnifying glass, there are too many possibilities.

The Metaphor: If you are tracing a murder back in time, you don't care about the fact that the victim ate breakfast or that a random stranger walked by. You only care about the chain of events that directly caused the murder.
The Technique: The tool uses "causality" to ignore irrelevant steps. If a message wasn't sent by the people involved in the error, or if a field wasn't changed by the people involved, the tool skips it. It cuts out the dead ends instantly.

5. "Message Segments": The Time-Lapse Camera

Sometimes, a dancer receives a hundred notes in a row. Checking them one by one would take forever.

The Metaphor: Instead of watching a video of a dancer receiving 1,000 notes one by one, the tool uses a "time-lapse" camera. It says, "We know this dancer received a segment of 1,000 notes, and here is the mathematical formula for what happens after 1,000 notes."
The Technique: The tool groups repetitive message loops into a single "segment." It uses math (recurrence relations) to calculate the result of the whole loop at once, rather than stepping through it 1,000 times. This allows it to handle infinite loops instantly.

The Results

The authors built a prototype tool named DissProve and tested it on famous distributed protocols like Leader Election (picking a boss), Two-Phase Commit (making sure a bank transaction happens for everyone or no one), and Bakery Algorithm (managing a line).

The Outcome: The tool successfully proved that these protocols are safe (no two leaders, no broken transactions) without needing humans to write complex mathematical proofs.
The Catch: It only works on protocols that follow the "Affine" rule (the one-note-per-person rule). However, the paper shows that many real-world systems fit this rule.

In summary: DissProve is a detective that solves safety mysteries in computer networks by working backward from the disaster, focusing only on the guilty parties, ignoring the innocent bystanders, and using math shortcuts to handle infinite crowds. It proves that for a large class of systems, we can finally automate the proof that they won't crash or behave badly.

Technical Summary: DissProve: Automated Verification of Distributed Protocols with Affine Communication

Problem Statement
Fully automated formal verification of distributed protocols remains a significant challenge due to their asynchronous nature and parametric definition (systems with an unbounded number of actors). Asynchronous communication leads to a combinatorial explosion of execution histories, while parametricity introduces an unbounded number of actors and execution lengths. Existing automated techniques typically rely on deriving complex global inductive invariants over the entire system state (often using forward reachability), which is difficult to construct manually or algorithmically, even for simple protocols.

Methodology
The authors present DissProve, an automated verification technique that proves safety properties by reasoning backwards from error states (negated safety properties) rather than forwards from initial states. The approach is specifically designed for affine protocols, defined as systems where each actor sends at most one message of a given type to each receiver. This constraint ensures that while the total number of messages may be unbounded, a single communication round reaches a quiescent point where no new messages of a specific type are sent.

The core methodology involves a goal-directed, backwards abstract interpretation using a novel symbolic abstraction of actor systems. This abstraction employs three distinct logics to represent different system components:

Separation Logic: Represents the distributed control locations and local stores of an unbounded number of actors, enabling local reasoning and "materialization" of specific actors relevant to the error goal.
Linear Logic: Represents the network buffer (messages sent but not yet handled).
Ordered Logic: Represents the history of message handling to capture causal dependencies.

The verification process proceeds backwards from an error state, attempting to refute the existence of a path to an initial state. To ensure termination and manage the state space explosion, the authors introduce two key mechanisms:

Actor-Causality Reduction: This reduces non-deterministic branching by only materializing actors and exploring message handlers that are causally relevant to the current error goal. Irrelevant actors and message interleavings are abstracted away.
Message-Segment Summarization: To handle cycles in message handling (e.g., an actor receiving multiple votes in a loop), the system summarizes sequences of identical messages from distinct actors into a "message segment" with a symbolic length parameter ( $k$ ). This allows the analysis to derive closed-form solutions (recurrence relations) for field updates, such as vote tallies, rather than unrolling the loop indefinitely.

Key Contributions

Novel Symbolic Abstraction: The paper introduces a symbolic abstraction of actor systems using separation, linear, and ordered logics. A central innovation is actor-location materialization, which allows the analysis to dynamically instantiate specific actors at control locations relevant to the error goal while keeping others abstract.
Termination-Preserving Operations: Two operations are defined to ensure the convergence of the backwards abstract interpretation:
- Actor-Causality Reduction: Reduces branching by focusing only on causal dependencies relevant to refuting the error state.
- Message-Segment Summarization: Summarizes cyclic message histories using recurrence analysis, deriving constraints on segment lengths based on the affine protocol property (e.g., distinct senders imply $k \leq$ system size).
- The authors prove the soundness of these operations and establish convergence guarantees using causal dependence graphs.
Implementation and Evaluation: The approach is implemented in a tool called DissProve. The authors demonstrate its feasibility by automatically verifying safety properties (consensus and mutual exclusion) for several standard distributed protocols, including a one-shot leader election, Lamport's Bakery algorithm, Two-Phase Commit, and a Barrier Lock. Notably, these verifications require no user-provided invariants.

Results
The evaluation on a benchmark suite of distributed protocols shows that DissProve can automatically refute safety violations or prove safety without manual invariant synthesis.

Effectiveness: The tool successfully verified protocols with non-trivial affine communication, including the "One-Shot" leader election (which contains a bug in the unpatched version that the tool detects) and the Two-Phase Commit protocol.
Necessity of Techniques: Ablation studies confirm that both actor-causal reduction and message-segment summarization are critical. Without causal reduction, the state space explodes with shallow, irrelevant histories. Without summarization, the analysis fails to terminate on protocols with cyclic message handling (like leader election).
Performance: While the tool relies on SMT solvers (Z3) for entailment checks, which constitute a significant portion of the runtime, the approach successfully terminates on complex benchmarks. For instance, verifying the Two-Phase Commit protocol took approximately 2 hours, while the Bakery algorithm took roughly 2.5 minutes.

Significance
The paper claims to identify a large, non-trivial class of distributed protocols (those with affine communication) for which automated safety verification is feasible. By shifting from forward reachability to a goal-directed, backwards approach, the authors avoid the complexity of constructing global inductive invariants. Instead, they derive necessary conditions for a violation to occur and show that these conditions lead to contradictions (e.g., requiring more votes than there are actors). This work extends goal-directed verification techniques, previously applied to event-driven and synchronous systems, to the domain of asynchronous, parametric distributed systems, offering a path toward fully automated verification of protocols like Paxos and Raft (for single rounds) without manual proof engineering.