DissProve: Automated Verification of Distributed Protocols with Affine Communication Conference: ; 2026;

Christian Fontenot, Gowtham Kaki, Bor-Yuh Evan Chang · 2026

Read DissProve: Automated Verification of Distributed Protocols with Affine Communication Conference: ; 2026; by Christian Fontenot, Gowtham Kaki, Bor-Yuh Evan Chang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-24003.txt.

Introduction

Fontenot, Kaki, and Chang present DissProve, a tool that checks safety traits of distributed protocols on its own. Such protocols, the rule sets letting many computers act as one system, are hard to verify. Messages arrive out of order, so the count of execution histories explodes. Protocols are also defined for any number of actors, so histories have no bound. Older methods demanded global invariants that describe the whole system at once. Those are painful to write even for simple protocols.

Reasoning backwards from error states is the core move. The tool proves bad states unreachable, instead of tracking all behaviour forward. Fontenot's team splits affine protocols from harder non-affine ones. Affine histories grow in length but stay within bounded rounds of communication. New goal-directed notions of materialization, causality, and summarization then let DissProve verify affine protocols with unlimited actors, with no hand-supplied global invariants.

Catalog record

CREATORChristian Fontenot, Gowtham Kaki, Bor-Yuh Evan Chang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE180 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.24003

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

DissProve: Automated Verification of Distributed Protocols with Affine Communication Conference: ; 2026; Christian Fontenot, Gowtham Kaki, Bor-Yuh Evan Chang Abstract . We consider the problem of automatically proving safety properties of distributed protocols. Distributed protocols have been particularly challenging for automated verification due to their asynchronous and parametric nature. Compared to synchronous systems, asynchronous communication leads to a combinatorial explosion of possible execution histories of message handlers. And because distributed protocols are typically defined parametrically on the number of actors, these definitions lead to an unbounded number of possible execution histories of unbounded length. Existing verification techniques for such distributed protocols typically require global invariants about the entire actor system, which are complex even for simple protocols. In this paper, we present an automated verification technique based on proving unreachability backwards from error states in an actor system. One key insight is that the unboundedness from parametricity can be further classified into affine and non-affine protocols, where affine protocols have execution histories of unbounded length in a bounded number of communication rounds. We show how to use novel, goal-directed notions of materialization, causality, and summarization to verify safety properties of affine protocols with an unbounded number of actors in an automated manner. Using our prototype verification tool DissProve , we provide evidence for the feasibility of automated safety verification of asynchronous parametrized systems with affine communication. 1. Introduction Fully automated formal verification of distributed protocols remains elusive despite decades of research. In this work, we identify a large, non-trivial class of distributed protocols for which we can automatically verify safety properties. We say a distributed protocol has affine communication if each actor sends at most one message of a given type to each receiver. Effectively, affine protocols are those where a communication round is bounded by a static number of message types. Affine protocols can have an unbounded number of messages in their execution history from an unbounded number of actors, but a round of communication must reach a quiescent point where no more messages of a given type are sent. Distributed protocols are often designed to communicate in rounds, where safety can be decomposed into intra-round and inter-round safety ( 12 ) . Following this intuition, communication within a round is usually bounded modulo the number of actors, and so a variety of protocols that real distributed systems rely on, including Paxos ( 27 ) , Raft ( 34 ) , and Two-Phase Commit ( 15 ) , can be defined with affine communication (for a single round). Safety verification ultimately boils down to deriving and checking an inductive invariant over-approximating the behavior of the system. Existing automated reasoning tools typically rely on inductive invariants about the forward reachable states of the unbounded set of actors (e.g., an array of actors of machine type Node ) to prove properties of distributed protocols (e.g., Ivy ( 36 ; 43 ) ). This approach is effective but not always practical, as the inductive invariants required to verify distributed protocols are often quite complex ( 46 ) . For example, the one-shot leader election protocol that we discuss in Section 2 requires six different quantified invariants, some with nested quantification, to be proven correct ( 30 ) . Working out the sufficient inductive invariants that are strong enough to imply the safety property of a protocol is therefore hard (manually or algorithmically). In this paper, we present an approach to automatically verify safety properties of distributed protocols with affine communication. In particular, we design a goal-directed, backwards-from-error, program logic for reasoning about actor systems. This style of reasoning, which we extend to reason about distributed protocols, has been considered previously for event-driven systems ( 5 ; 33 ) , as well as synchronous parametric systems ( 13 ; 7 ) . This program logic uses a symbolic abstraction of actor systems using separation, linear, and ordered logics to represent the memory of an unbounded number of actors, the network buffer of an unbounded number of messages, and the unbounded history of message handling, respectively. We then define a backwards abstract interpretation using this symbolic abstraction to consider the relevant slice of the system necessary to refute error states (i.e., prove them unreachable ). Overall, we make the following technical contributions: • We build a novel symbolic abstraction of actor systems using separation, linear, and ordered logics and introduce actor-location materialization as a means to enable goal-directed safety verification of parametric asynchronous actor systems ( Section 3 ). • We introduce two key operations to ensure the termination of a backwards abstract interpretation using this symbolic abstraction: (a) actor-causality reduction to reduce the non-deterministic branching ( Section 4 ), and (b) message-segment summarization to summarize cyclic message histories ( Section 5 ). We prove the soundness of these operations and establish convergence guarantees using a notion of causal dependences. • We implement this approach in a verification tool called DissProve — the Dis tributed S ystems Prove r and describe our experience using it to automatically verify the safety of several distributed protocols with affine communication ( Section 6 ). 2. Overview ⬇ machine Node { var id: int ; var forMe: int ; var leader: int ; on eInit do ( c: tConfig ) { 1 id = c . id ; 2 forMe = 0; // no votes for me yet 3 leader = -1; // no leader yet 4 send ChooseLeader (), eVote ; 5 } on eVote do { 6 forMe = forMe + 1; ⬇ - if ( forMe >= sizeof Node )/2) { ⬇ + if ( forMe > sizeof Node )/2) { ⬇ leader = id ; // Broadcast, "I am the leader." \ldots } } } Figure 1 . A simplified “one-shot” leader election protocol. Each node will choose a node to vote for, and send an eVote message to it. When a node has received enough of these, it marks itself as leader (and can broadcast its assumption of leader and start the next phase). We show a bug-fix commit; in the buggy version (the - version of line 1 ), the protocol can reach an unsafe state where two nodes believe they are elected at the same time. In this section, we illustrate the intuition behind our techniques, using a leader election protocol shown in Figure 1 . In practice, leader election is only a fragment of a larger distributed system. Unrelated code is omitted in the figures, and we will see that the goal-directed approach ignores any irrelevant code even in a distributed context. The protocol in question starts with each actor receiving an initial message ( eInit ), which configures its unique identifier ( id = c.id at location 1 ) and initializing other fields accordingly ( forMe = 0 at 2 and leader = -1 at 3 ). The initial message handler ends with the actor choosing who to vote for and sending that actor a eVote message (at 4 ). Upon receiving a vote (an eVote message), an actor will increment a counter for itself ( \text{\small forMe}\mathrel{\text{\small=}}\text{\small forMe + 1} at location 6 ). If it has received enough votes — a quorum (the condition at 1 ),

Read the complete text