Abstract
Despite many recent advances, reactive synthesis is still not really a practical technique. The grand challenge is to scale from small transition systems, where synthesis performs well, to complex multi-component designs. Compositional methods, such as the construction of dominant strategies for individual components, reduce the complexity significantly, but are usually not applicable without extensively rewriting the specification. In this paper, we present a refinement of compositional synthesis that does not require such an intervention. Our algorithm decomposes the system into a sequence of components, such that every component has a strategy that is dominant, i.e., performs at least as good as any possible alternative, provided that the preceding components follow their (already synthesized) strategies. The decomposition of the system is based on a dependency analysis, for which we provide semantic and syntactic techniques. We establish the soundness and completeness of the approach and report on encouraging experimental results.
Introduction
Reactive synthesis is often described as the "holy grail" of software engineering: the ability to automatically generate a correct-by-construction implementation from a high-level specification, typically written in Linear Temporal Logic (LTL). Despite its promise, the technique has long been hindered by the "state-space explosion" problem. As the complexity of a system increases, the computational resources required to synthesize it grow exponentially, rendering standard monolithic synthesis impractical for real-world applications.
To combat this, researchers have turned to compositional synthesis, which attempts to break a large system into smaller, manageable components. However, traditional compositional methods face a significant hurdle: interdependence. In most systems, one component's success depends on the correct behavior of another. Because standard synthesis algorithms look for strict "winning" strategies against an adversarial environment, they often fail to find a solution for individual components in isolation unless a human expert manually decouples the specifications. This paper introduces a novel incremental synthesis approach that automates this decomposition using variable dependencies and dominant strategies.
Moving Beyond Winning Strategies
The core innovation of this work is the shift from seeking "winning" strategies to "dominant" strategies, specifically remorsefree dominance. In a standard synthesis game, a strategy is only successful if it guarantees the specification is met against any possible environment behavior. In a multi-component system, this is often an impossible standard for a single component to meet alone.
A dominant strategy, by contrast, is one that performs at least as well as any other possible strategy. It essentially mandates that a component "does its best." Even if the environment (or other components) acts in a way that makes satisfying the specification impossible, the dominant strategy ensures the component is not the cause of the failure. This shift allows the synthesis tool to justify separate component construction without requiring a global guarantee of success at every step.
Dependency Analysis and Incremental Synthesis
To implement this approach, the system must be decomposed into a specific order. The authors propose two methods for dependency analysis to determine which variables and components rely on others:
- Semantic Analysis: This is a mathematically rigorous check of how changes in one output variable necessitate changes in another to satisfy the specification. While highly accurate, it is computationally expensive to perform.
- Syntactic Analysis: This is a faster, conservative approximation. It examines the structure of the LTL formula's syntax tree, grouping variables based on their proximity to logical and temporal operators. The authors demonstrate that this "good enough" proxy provides significant speedups while remaining a safe overapproximation.
Once the dependency graph is established, the system is partitioned into strongly connected components and synthesized incrementally. The algorithm synthesizes a dominant strategy for foundational components first. When moving to the next layer, the synthesis tool treats the strategies of the previous components as known environmental behavior rather than unknown adversarial variables. This drastically reduces the search space for each subsequent component.
Experimental Evaluation
The authors implemented this incremental framework as a prototype extending BoSy, a state-of-the-art bounded synthesis tool. The evaluation utilized four scalable benchmarks: n-ary Latch, Generalized Buffer, a Sensor management system, and a Robot Fleet coordination task.
The results indicate a massive improvement in scalability over traditional monolithic synthesis:
- n-ary Latch: While standard BoSy timed out at just 5 bits, the incremental approach successfully scaled to 1104 bits in under an hour.
- Generalized Buffer: The incremental approach solved a 3-receiver instance in 66 seconds, whereas the standard tool timed out at 2 receivers.
- Robot Fleet: The system successfully coordinated 4 robots in 269 seconds, surpassing the 3-robot limit of the standard tool.
Conclusion and Future Work
By leveraging dependency-based decomposition and dominant strategies, this research provides a viable path toward scaling reactive synthesis to complex, multi-component designs. While the faster syntactic analysis can sometimes be overly conservative—as seen in the Sensors benchmark where it missed certain optimization opportunities—the overall framework remains highly effective.
Future work includes integrating this dependency-based framework into other synthesis paradigms beyond bounded synthesis, such as explicit approaches like Strix, to further enhance the practical applicability of automated software generation.
Summary updated