Bounded Synthesis of Synchronized Distributed Models from Lightweight Specifications

Pablo F. Castro, Luciano Putruele, Renzo Degiovanni, Nazareno Aguirre · 2025

Read Bounded Synthesis of Synchronized Distributed Models from Lightweight Specifications by Pablo F. Castro, Luciano Putruele, Renzo Degiovanni, Nazareno Aguirre (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-2502-13955.txt.

Introduction

Pablo Castro, Luciano Putruele, Renzo Degiovanni, and Nazareno Aguirre wrote a paper in two thousand twenty-five on building distributed systems from light formal specs. A distributed system has parts that must act together. Their method takes part specs and a global time rule that the joint action must meet.

The method builds runnable models for each part, in a style like the Promela language, and checks their joint run against the global rule. A search tool lists possible builds up to a set size. Since that list can grow fast, the authors use groups of counterexamples to cut the search. They built a test tool and compared it with other approaches.

Catalog record

CREATORPablo F. Castro, Luciano Putruele, Renzo Degiovanni, Nazareno Aguirre
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-13955

Browse the full library · About the Tower of Babel

Full text

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

Bounded Synthesis of Synchronized Distributed Models from Lightweight Specifications Pablo F. Castro, Luciano Putruele, Renzo Degiovanni, Nazareno Aguirre Abstract We present an approach to automatically synthesize synchronized models from lightweight formal specifications. Our approach takes as input a specification of a distributed system along with a global linear time constraint, which must be fulfilled by the interaction of the system’s components. It produces executable models for the component specifications (in the style of Promela language) whose concurrent execution satisfies the global constraint. The component specifications consist of a collection of actions described by means of pre and post conditions together with first-order relational formulas prescribing their behavior. We use the Alloy Analyzer to encode the component specifications and enumerate their potential implementations up to some bound, whose concurrent composition is model checked against the global property. Even though this approach is sound and complete up to the selected bound, it is impractical as the number of candidate implementations grows exponentially. To address this, we propose an algorithm that uses batches of counterexamples to prune the solution space, it has two main phases: exploration , the algorithm collects a batch of counterexamples, and exploitation , where this knowledge is used to speed up the search. The approach is sound, while its completeness depends on the batches used. We present a prototype tool, describe some experiments, and compare it with related approaches. 1 Introduction Program synthesis [ 1 , 2 , 3 ] allows for the automated construction of programs from specifications. Ideally, the user only provides a formal description of the intended behavior of a to-be-developed program, and then a program, correct with respect to the given specification, is automatically derived. A clear benefit of this ideal scenario is that users only need to concentrate in writing software specifications, which are typically stated in a higher level of abstraction, that abstracts away involved implementation details. In the last decades, the constant advances in hardware, and the emergence of new synthesis methods, have made possible the application of synthesis to complex case studies (see, e.g., [ 4 ] ). This paper focuses on the synthesis of high-level descriptions for distributed systems, such as protocols and multi-agent systems. These systems are crucial in modern software applications, including collaborative tools, communication networks, and cryptocurrencies. Moreover, their correct implementation is in general rather complex and time consuming, which often results in subtle programming errors. Particularly, when synchronization primitives (e.g., semaphores, locks, monitors) are used to manage access to shared resources. Their incorrect use often leads to challenging issues like race conditions and deadlocks, which are difficult to identify and fix using conventional methods. Thus, distributed algorithms, and in particular the use of synchronization primitives, constitute a compelling target for synthesis approaches. Approaches to automated synthesis have seen significant improvement in recent years. Some techniques are based on game theory for temporal logic specifications [ 5 ] , the synthesis from input-output examples [ 6 ] , inductive programming [ 7 ] , and techniques based on theorem proving [ 8 ] , which have been successfully applied in various contexts. Synthesis techniques for distributed algorithms are less common, as mentioned above, in this setting we have additional difficulties, such as the problem of dealing with several interacting processes, complying with specific communication architectures, and correctly instrumenting coordination via synchronization mechanisms. In fact, the problem of synthesizing distributed code from specifications is undecidable in many settings [ 9 ] . The (bounded) synthesis technique presented in this paper targets asynchronous distributed systems that use shared memory for the communication and synchronize via locks. A system specification, in this setting, is composed of a (finite) collection of process or component specifications consisting of actions specified via pre/post-conditions, together with local constraints expressing required properties of the action executions; and global properties that the process/component interaction must guarantee. Local constraints are expressed in Alloy’s relational logic [ 10 ] , a first-order logic with transitive closure (necessary for expressing certain constraints, notably reachability), whereas global constraints are specified in linear-time logic. If successful, the technique produces implementations for the components that use their corresponding local actions as well as lock-based synchronizations, and satisfy the local constraints, while their interaction satisfies the global constraints. More specifically, the approach encodes component specifications into an Alloy model [ 10 ] , in such a way that satisfying instances of the model correspond to locally correct implementations of the corresponding process. Thus, we indirectly use Boolean satisfiability to enumerate (bounded) locally valid implementations of processes. When locally valid implementations of processes are found, their combination is checked against the global specification, to verify whether the current local candidates lead to a correct distributed solution. For efficiency reasons, this latter global check is performed using a symbolic model checker. The search is performed in a lexicographic manner, in which a backtracking is performed when the possible instances of a component specification are exhausted. However, this basic algorithm is impractical due to the exponential number of potential component implementations, for which we also have to consider all their possible combinations. To address this, we introduce an improved algorithm that uses counterexample batches to speed up the process. This algorithm consists of two phases: an exploratory phase that collects instances from the solver and generates counterexamples via a model checker; followed by an exploitation phase that refines component specifications based on these counterexamples. If no solutions are found, the process repeats with the refined specifications. The algorithm’s efficiency and completeness depend on the chosen batch configurations, which we explore in Section 7 , discussing their benefits and drawbacks. The paper is structured as follows. In Section 2 we introduce preliminary concepts. Section 3 illustrates our approach via a motivating example. Sections 6 and 7 describe the main algorithm and discuss experimental results. Finally, Sections 8 and 9 discuss related work and present some final remarks. 2 Preliminaries Labeled Transition Systems. A well-established mechanism to provide semantics for reactive and distributed systems is via labeled transition systems (LTSs). An LTS is a tuple \langle S,\textit{Act},\rightarrow,I,\textit{AP},L\rangle where: S is a (finite) non-empty set of states , Act is a (finite) set of actions , \rightarrow\subseteq S\times\textit{Act}\times S is a labeled transition relation, I\subseteq S is a set of initial states , AP is a (finite) set of atomic propositions, and L:S\rightarrow 2^{\textit{AP}} is a labeling function. Intuitively, S is an abstraction of the system states, L indicates which atomic properties hold in each state, Act is an abstraction of the system actions, and \rightarrow indicates how the system changes state as actions occur. For convenience, we write s\xrightarrow{a}s^{\prime} instead of \langle s,a,s^{\prime}\rangle\in\rightarrow , and \mathit{Post}(s,s^{\prime}) if there is an a\in\textit{Act} such that s\xrightarrow{a}s^{\prime} . The reflexive-transitive closure of relation \mathit{Post} helps capturing system executions, and is written \mathit{Post}^{*} . A path over an LTS is a sequence of alternating states and actions \pi=s_{0},a_{0},s_{1},a_{1}\dots such that \forall i:s_{i}\xrightarrow{a_{i}}s_{i+1} . We say that a path is an execution (or trace ) if it is maximal. Without loss of generality, we assume that each state has at least one successor. When only states or transitions are relevant, we refer to executions as sequences of states or transitions. We extend L

Read the complete text