Summary
This research introduces a framework for automatically generating "priorities"—stateless rules that decide which action to take when multiple are available—to ensure component-based systems remain safe and deadlock-free. By combining safety-game algorithms for fault localization with SAT solvers for conflict resolution, and employing novel abstraction techniques, the authors scale priority synthesis to systems significantly larger than previously possible.
The Challenge of Priority Design
In component-based design frameworks like BIP (Behavior, Interaction, Priority), complex systems are assembled from smaller, reusable modules. While individual components may be verified in isolation, their interactions often introduce "bad states," such as safety violations or deadlocks.
Engineers traditionally use priorities (e.g., "Action A has precedence over Action B") to restrict system behavior and avoid these states without adding new state variables. However, manually designing these rules for systems with thousands of states is an NP-complete problem. This research addresses the need for efficient, automated synthesis of priority rules for large-scale systems.
Methodology
The proposed synthesis pipeline consists of two primary stages: fault localization and complexity management.
Fault-Localization and Repair
The synthesis process begins by identifying "fault locations"—states where the system is at risk of entering a prohibited zone but can still be saved by prioritizing one action over another. This is achieved using a "safety game" algorithm that works backward from known bad states ($C_{risk}$).
Once potential fixes are identified, they are processed by a SAT solver. The solver generates a consistent set of priority rules that resolve all faults while ensuring no circular dependencies are created, which would lead to logical inconsistencies.
Scaling via Abstraction and Compositional Synthesis
To handle the state explosion inherent in massive systems, the authors introduce several scaling techniques:
- Alphabet Abstraction: Components irrelevant to a specific property are "hidden." The concept of $\sharp$-deadlock (sharp-deadlock) is introduced to ensure that if the abstracted system is deadlock-free, the original system remains safe.
- Compositional Synthesis with $L^*$ Learning: The $L^*$ algorithm is used to learn the assumptions components must make about each other, allowing for isolated synthesis of priorities.
- FORCE Heuristics: Variable-ordering techniques from circuit design optimize the Binary Decision Diagrams (BDDs) used in the synthesis engine.
Experimental Evaluation
The researchers evaluated their tool, VISSBIP, against standard benchmarks including the Dining Philosophers problem, Data Processing Units (DPU), and Automatic Traffic Control.
Key results showed significant performance gains. VISSBIP solved the 50-philosopher problem (100 components) in just 31 seconds—a task that previously stalled at 15 philosophers. The SAT-based repair step was highly efficient, typically accounting for less than 20% of execution time.
Conclusion
The framework successfully synthesizes "local" priorities that require components to know only their own state, a critical requirement for distributed hardware. While the current alphabet abstraction is conservative and may occasionally over-approximate, the approach represents a major step forward in the automated design of robust, distributed component-based systems.
Summary updated