Given a set of interacting components with non-deterministic variable update and given safety requirements, the goal of priority synthesis is to restrict, by means of priorities, the set of possible interactions in such a way as to guarantee the given safety conditions for all possible runs. In distributed priority synthesis we are interested in obtaining local sets of priorities, which are deployed in terms of local component controllers sharing intended next moves between components in local neighborhoods only. These possible communication paths between local controllers are specified by means of a communication architecture. We formally define the problem of distributed priority synthesis in terms of a multi-player safety game between players for (angelically) selecting the next transition of the components and an environment for (demonically) updating uncontrollable variables; this problem is NP-complete. We propose several optimizations including a solution-space exploration based on a diagnosis method using a nested extension of the usual attractor computation in games together with a reduction to corresponding SAT problems. When diagnosis fails, the method proposes potential candidates to guide the exploration. These optimized algorithms for solving distributed priority synthesis problems have been integrated into our VissBIP framework. An experimental validation of this implementation is performed using a range of case studies including scheduling in multicore processors and modular robotics.
Distributed controller synthesis is undecidable @cite_3 even for reachability or simple safety conditions @cite_15 @. A number of decidable subproblems have been proposed either by restricting the communication structures between components, such as pipelined, or by restricting the set of properties under consideration @cite_14 @cite_19 @cite_18 @cite_1 ; these restrictions usually limit applicability to a wide range of problems @. Schewe and Finkbiner's @cite_5 bounded synthesis work on LTL specifications: when using automata-based methods, it requires that each process shall obtain the same information from the environment. The method is extended to encode locality constraints to work on arbitrary structures. Distributed priority synthesis, on one hand, its starting problem is a given distributed system, together with an additional safety requirement to ensure. On the other hand, it is also flexible enough to specify different communication architectures between the controllers such as master-slave in the multiprocessor scheduling example. To perform distributed execution, we have also explicitly indicate how such a strategy can be executed on concrete platforms.
@cite_18 @cite_14 @cite_1 @cite_3 @cite_19 @cite_5 @cite_15
1610578937 2964248107 1497341048 1783469492
We provide a uniform solution to the problem of synthesizing a finite-state distributed system. An instance of the synthesis problem consists of a system architecture and a temporal specification. The architecture is given as a directed graph, where the nodes represent processes (including the environment as a special process) that communicate synchronously through shared variables attached to the edges. The same variable may occur on multiple outgoing edges of a single node, allowing for the broadcast of data. A solution to the synthesis problem is a collection of finite-state programs for the processes in the architecture, such that the joint behavior of the programs satisfies the specification in an unrestricted environment. We define information forks, a comprehensive criterion that characterizes all architectures with an undecidable synthesis problem. The criterion is effective: for a given architecture with n processes and v variables, it can be determined in O(n sup 2 spl middot v) time whether the synthesis problem is decidable. We give a uniform synthesis algorithm for all decidable cases. Our algorithm works for all spl omega -regular tree specification languages, including the spl mu -calculus. The undecidability proof, on the other hand, uses only LTL or, alternatively, CTL as the specification language. Our results therefore hold for the entire range of specification languages from LTL CTL to the spl mu -calculus. The distributed synthesis problem is about constructing correct distributed systems, i.e., systems that satisfy a given specification. We consider a slightly more general problem of distributed control, where the goal is to restrict the behavior of a given distributed system in order to satisfy the specification. Our systems are finite state machines that communicate via rendez-vous (Zielonka automata). We show decidability of the synthesis problem for all omega-regular local specifications, under the restriction that the communication graph of the system is acyclic. This result extends a previous decidability result for a restricted form of local reachability specifications. The distributed synthesis problem [11] is known to be undecidable. Our purpose here is to study further this undecidability. For this, we consider distributed games [8], an infinite variant of Peterson and Reif multiplayer games with partial information [10], in which Pnueli and Rosner's distributed synthesis problem can be encoded and, when decidable [11,6,7], uniformly solved [8]. We first prove that even the simple problem of solving 2-process distributed game with reachability conditions is undecidable ( @math -complete). This decision problem, equivalent to two process distributed synthesis with fairly restricted FO-specification was left open [8]. We prove then that the safety case is @math -complete. More generally, we establish a correspondence between 2-process distributed game with Mostowski's weak parity conditions [9] and levels of the arithmetical hierarchy. finally, distributed games with general i¾?-regular infinitary conditions are shown to be highly undecidable ( @math -complete). The problem of synthesizing a finite-state distributed reactive system is considered. Given a distributed architecture A, which comprises several processors P sub 1 , . . ., P sub k and their interconnection scheme, and a propositional temporal specification phi , a solution to the synthesis problem consists of finite-state programs Pi sub 1 , . . ., Pi sub k (one for each processor), whose joint (synchronous) behavior maintains phi against all possible inputs from the environment. Such a solution is referred to as the realization of the specification phi over the architecture A. Specifically, it is shown that the problem of realizing a given propositional specification over a given architecture is undecidable, and it is nonelementarily decidable for the very restricted class of hierarchical architectures. An extensive characterization of architecture classes for which the realizability problem is elementarily decidable and of classes for which it is undecidable is given. >