Accelerating Protocol Synthesis and Detecting Unrealizability with Interpretation Reduction
Derek Egolf, Stavros Tripakis · 2025
Read Accelerating Protocol Synthesis and Detecting Unrealizability with Interpretation Reduction by Derek Egolf, Stavros Tripakis (2025) 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-2501-14585.txt.
Introduction
Egolf and Tripakis present in twenty twenty-five a faster method to build distributed software protocols from sketches and fix-it feedback. Protocol design is slow because checkers must test many wrong candidates one by one. Their method cuts the search space early, dropping bad candidates before checking and avoiding near-duplicate candidates altogether.
A smarter step also generalises each failure into a broad rule that prunes whole families at once. On standard benchmarks their tool beat the prior best almost always, often by orders of magnitude. It built one full protocol from scratch in minutes where the rival timed out after an hour. The method is proven sound and complete under common assumptions.
Catalog record
| CREATOR | Derek Egolf, Stavros Tripakis |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-14585
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Accelerating Protocol Synthesis and Detecting Unrealizability with Interpretation Reduction Derek Egolf, Stavros Tripakis Abstract We present a novel counterexample-guided, sketch-based method for the synthesis of symbolic distributed protocols in TLA + . Our method’s chief novelty lies in a new search space reduction technique called interpretation reduction, which allows to not only eliminate incorrect candidate protocols before they are sent to the verifier, but also to avoid enumerating redundant candidates in the first place. Further performance improvements are achieved by an advanced technique for exact generalization of counterexamples. Experiments on a set of established benchmarks show that our tool is almost always faster than the state of the art, often by orders of magnitude, and was also able to synthesize an entire TLA + protocol “from scratch” in less than 3 minutes where the state of the art timed out after an hour. Our method is sound, complete, and guaranteed to terminate on unrealizable synthesis instances under common assumptions which hold in all our benchmarks. 1 Introduction Distributed protocols are the foundation of many modern computer systems. They find use in domains such as finance [ 8 , 7 ] and cloud computing [ 9 , 10 ] . Distributed protocols are notoriously difficult to design and verify. These difficulties have motivated the advances in fuller automation for verification of both safety [ 17 , 19 , 44 , 42 , 36 , 35 ] and liveness [ 43 ] properties of distributed protocols. In this paper, we study the automated synthesis of distributed protocols. In verification, the goal is to check whether a given protocol satisfies a given property. The goal in synthesis is to invent a protocol that satisfies a given property. Synthesis is a challenging problem [ 32 , 24 , 33 , 39 , 40 ] , and we use the sketching paradigm [ 37 , 38 ] to turn the synthesis problem into a search problem. The user provides a protocol sketch , which is a protocol with holes in it; each hole is associated with a grammar. The goal is to choose expressions from the grammars to fill the holes in the sketch to obtain a protocol that satisfies a given property. Our target protocols are represented symbolically in the TLA + language [ 27 ] , a popular specification language for distributed systems used in both academia and industry [ 31 ] . In this paper we propose a novel method for synthesis of distributed protocols by sketching. Our method follows the counterexample-guided inductive synthesis (CEGIS) paradigm [ 38 , 18 ] , but with some crucial innovations, explained below. In CEGIS, a learner is responsible for generating candidate protocols, and a verifier is responsible for checking whether the candidate protocols satisfy the property. In addition to saying correct/incorrect, the verifier also provides a counterexample when the candidate protocol is incorrect. Existing approaches generalize the counterexample to a set of constraints which allows to prune the search space [ 2 , 4 , 12 ] . Such pruning eliminates candidate protocols that are sure to exhibit previously encountered counterexamples before they make it to the verifier, which is crucial for scalability: e.g., [ 12 ] show that pruning constraints can be used to prevent hundreds of thousands of model-checker calls. Unfortunately, pruning alone only goes so far. Even when many calls to the verifier are avoided, the sheer size of the search space is often huge. Therefore, enumerating all candidates (and checking each one of them against the pruning constraints) can be prohibitive in itself. In this paper, we address this problem by introducing a novel search space reduction technique called interpretation reduction . While pruning constraints eliminate incorrect candidate protocols before they are sent to the verifier, reduction avoids enumerating redundant candidates in the first place. Reduction can be achieved by choosing an equivalence relation, partitioning the search space into classes of equivalent expressions, and enumerating at most one expression from each equivalence class. One choice of equivalence relation is universal equivalence . Two expressions are universally equivalent if they evaluate to the same value under all interpretations (an interpretation is an assignment mapping terminal symbols of sketch grammars to values). E.g., x+y and y+x are universally equivalent. Our expression enumerator does better, and will only generate semantically distinct expressions up to a coarser notion of equivalence, namely, interpretation equivalence . If \alpha is an interpretation, then two expressions, e_{1} and e_{2} , are interpretation equivalent with respect to \alpha if they evaluate to the same value under \alpha . E.g., x and x+x are not universally equivalent, but are interpretation equivalent with respect to the interpretation \alpha=[x\mapsto 0] . Our experiments show that our method is almost always faster than the state of the art, and in many cases, more than 100 times faster. In addition to improving efficiency, interpretation reduction also enables recognizing unrealizable synthesis instances, i.e., instances where there is no solution. Under certain conditions (met in all of our benchmarks), interpretation reduction partitions the search space into finitely many equivalence classes. Then, if the algorithm has enumerated an expression from each equivalence class and none of them satisfy the property, the algorithm can infer that the synthesis instance is unrealizable and terminate. Our experiments show that our method is able to recognize five times more unrealizable synthesis instances than the state of the art. In summary, this work makes the following contributions: (1) a novel search space reduction technique based on interpretation equivalence, (2) the first, to our knowledge, method for synthesizing TLA + protocols by sketching that is guaranteed to terminate on unrealizable synthesis instances when there are a finite number of equivalence classes modulo interpretation equivalence, and (3) a synthesis tool called PolySemist that implements our method and outperforms the state of the art. Most notably, PolySemist was able to synthesize an entire TLA + protocol from scratch in less than 3 minutes where the state of the art timed out after an hour. To the best of our knowledge, ours is the first tool to synthesize a TLA + protocol from scratch. 2 Distributed Protocol Synthesis Protocol Representation in TLA + We consider symbolic transition systems modeled in TLA + [ 27 ] , e.g., as shown in Fig. 1 . A primed variable, e.g., \textit{vote\_yes}^{\prime} , denotes the value of the variable in the next state. Formally, a protocol is a tuple \langle\textsc{Vars},\textsc{Init},\textsc{Next}\rangle . Vars is the set of state variables (e.g. Fig. 1 line 2 ). Init and Next are predicates specifying, respectively, the initial states and the transition relation of the system, as explained in detail in the next subsections. In Fig. 1 , the protocol is parameterized by the set of nodes participating in the protocol, which is denoted by the declaration on line 1 . As in [ 12 ] , we are able to synthesize parameterized protocols. For space reasons, we omit all discussion of parameterized protocols in this paper and refer the reader to [ 12 ] for details. Protocol Semantics A state of a protocol is an assignment of values to the variables in Vars . We write s[v] to denote the value of the state variable